golang key map 所有_golang之map详解 - 01基础数据结构

<blockquote> 大家在面试过程中经常会被问到hashmap的底层数据结构和算法过程。本文主要和大家探讨下go语言中的map对象的底层数据结构和算法，让大家能够理解map对象是一个什么样的存在？它为什么能够高效？ </blockquote>

大家都知道golang中Map由链式哈希表实现，底层是hash实现，数据结构为hash数组 桶 溢出的桶链表，每个桶存储最多8个key-value对

<blockquote> 链式哈希表从根本上说是由一组链表构成。每个链表都可以看做是一个“桶”，我们将所有的元素通过散列的方式放到具体的不同的桶中。插入元素时，首先将其键传入一个哈希函数（该过程称为哈希键），函数通过散列的方式告知元素属于哪个“桶”，然后在相应的链表头插入元素。 </blockquote> <h3>map的数据结构</h3> <blockquote> 为了彻底搞清楚map的数据结构，我从go的开源项目中找到了map的底层定义的代码如下 </blockquote>

代码地址如下:https://github.com/golang/go/blob/master/src/runtime/map.go

基础概念介绍

<ul><li>unsafe.Pointer 它表示任意类型且可寻址的指针值，可以在不同的指针类型之间进行转换 <ul><li>任何类型的指针值都可以转换为 Pointer</li><li>Pointer 可以转换为任何类型的指针值</li><li>uintptr 可以转换为 Pointer</li><li>Pointer 可以转换为 uintptr</li></ul></li><li>uintptr：uintptr 是 Go 的内置类型。返回无符号整数，可存储一个完整的地址。后续常用于指针运算</li><li>map存储的元素对计数，len()函数返回此值，所以map的len()时间复杂度是O(1)</li><li>记录几个特殊的位标记，如当前是否有别的线程正在写map、当前是否为相同大小的增长（扩容/缩容？）</li><li>hash桶buckets的数量为2^B个</li><li>noverflow 溢出的桶的数量的近似值</li><li>hash0 hash种子</li><li>buckets 指向2^B个桶组成的数组的指针，数据存在这里</li><li>oldbuckets 指向扩容前的旧buckets数组，只在map增长时有效</li><li>nevacuate 计数器，标示扩容后搬迁的进度</li><li>extra 保存溢出桶的链表和未使用的溢出桶数组的首地址</li></ul>

桶指针指向桶的首地址，可通过桶首地址及偏移量查询所有的桶，通过每个桶可查找到对应的键值。hmap.B=2， 而hmap.buckets长度是2^B为4. 元素经过哈希运算后会落到某个bucket中进行存储。查找过程类似。bucket很多时候被翻译为桶，所谓的哈希桶实际上就是bucket

<h3>bucket数据结构</h3> <blockquote> 更加源码译文可知：bucketCnt=8，一个桶只能存放8对k/v, 低8位用来寻找桶，高8位用来寻找元素 </blockquote> <ul><li>tophash存储桶内每个key的hash值的高字节</li><li>tophash[0] < minTopHash表示桶的疏散状态</li><li>当前版本bucketCnt的值是8，一个桶最多存储8个key-value对</li><li>特别注意： <ul><li>实际分配内存时会申请一个更大的内存空间A，A的前8字节为bmap</li><li>后面依次跟8个key、8个value、1个溢出指针</li><li>map的桶结构实际指的是内存空间A</li></ul></li></ul>

哈希值相同的键（准确的说是哈希值低位相同的键）存入当前bucket时会将哈希值的高位存储在该数组中，以方便后续匹配。

<h3>总体数据结构图</h3> <blockquote> map底层创建时，会初始化一个hmap结构体，同时分配一个足够大的内存空间A。其中A的前段用于hash数组，A的后段预留给溢出的桶。于是hmap.buckets指向hash数组，即A的首地址；hmap.extra.nextOverflow初始时指向内存A中的后段，即hash数组结尾的下一个桶，也即第1个预留的溢出桶。所以当hash冲突需要使用到新的溢出桶时，会优先使用上述预留的溢出桶，hmap.extra.nextOverflow依次往后偏移直到用完所有的溢出桶，才有可能会申请新的溢出桶空间。 </blockquote>

当需要分配一个溢出桶时，会优先从预留的溢出桶数组里取一个出来链接到链表后面，这时不需要再次申请内存。但当预留的桶被用完了，则需要申请新的内存给溢出桶。

<h3>参考资料</h3>

https://www.cnblogs.com/JoZSM/archive/2019/11/02/11784037.htmlhttps://www.jianshu.com/p/17f49e562f7bhttps://my.oschina.net/renhc/blog/2208417?nocache=1539143037904#comments