hash冲突

哈希查找表一般会存在“碰撞”的问题，就是说不同的 key 被哈希到了同一个 bucket。一般有两种应对方法：链表法和开放地址法。链表法将一个 bucket 实现成一个链表，落在同一个 bucket 中的 key 都会插入这个链表。开放地址法则是碰撞发生后，通过一定的规律，在数组的后面挑选“空位”，用来放置新的 key。

go使用的是链表法来解决hash冲突。

map内存模型

// A header for a Go map.
type hmap struct {
    // 元素个数，调用 len(map) 时，直接返回此值
    count     int
    flags     uint8
    // buckets 的对数 log_2
    B         uint8
    // overflow 的 bucket 近似数
    noverflow uint16
    // 计算 key 的哈希的时候会传入哈希函数
    hash0     uint32
    // 指向 buckets 数组，大小为 2^B
    // 如果元素个数为0，就为 nil
    buckets    unsafe.Pointer
    // 扩容的时候，buckets 长度会是 oldbuckets 的两倍
    oldbuckets unsafe.Pointer
    // 指示扩容进度，小于此地址的 buckets 迁移完成
    nevacuate  uintptr
    extra *mapextra // optional fields
}

B就是buckets数组的长度的对数，即有2^B个桶。

bucket桶的运行时数据结构为：

type bmap struct {
    topbits  [8]uint8
    keys     [8]keytype
    values   [8]valuetype
    pad      uintptr
    overflow uintptr
}

bmap 就是我们常说的“桶”，桶里面会最多装 8 个 key，这些 key 之所以会落入同一个桶，是因为它们经过哈希计算后，哈希结果是“一类”的。在桶内，又会根据 key 计算出来的 hash 值的高 8 位来决定 key 到底落入桶内的哪个位置（一个桶内最多有8个位置）。 我们可以看到桶里面有个数组是存放各key的hash值的高8位，key是放一起，value又是放一起。 key和value为什么要分开？ 源码里说明这样的好处是在某些情况下可以省略掉 padding 字段，节省内存空间。 map[int64]int8 如果按照 key/value/key/value/… 这样的模式存储，那在每一个 key/value 对之后都要额外 padding 7 个字节；而将所有的 key，value 分别绑定到一起，这种形式 key/key/…/value/value/…，则只需要在最后添加 padding。

使用map

使用map很简单，利用make内建函数，通过汇编语言可以看到，实际上底层调用的是 makemap 函数，主要做的工作就是初始化 hmap 结构体的各种字段，例如计算 B 的大小，设置哈希种子 hash0 等等。

注意，这个函数返回的结果：*hmap，它是一个指针，所以map看起来像是引用。

key定位过程

key 经过哈希计算后得到哈希值，共 64 个 bit 位（64位机，32位机就不讨论了，现在主流都是64位机），计算它到底要落在哪个桶时，只会用到最后 B 个 bit 位。还记得前面提到过的 B 吗？如果 B = 5，那么桶的数量，也就是 buckets 数组的长度是 2^5 = 32。

例如，现在有一个 key 经过哈希函数计算后，得到的哈希结果是：

10010111 | 000011110110110010001111001010100010010110010101010 │ 01010

用最后的 5 个 bit 位，也就是 01010，值为 10，也就是 10 号桶。这个操作实际上就是取余操作，但是取余开销太大，所以代码实现上用的位操作代替。

再用哈希值的高 8 位，找到此 key 在 bucket 中的位置，这是在寻找已有的 key。最开始桶内还没有 key，新加入的 key 会找到第一个空位，放入。

当两个不同的 key 落在同一个桶中，也就是发生了哈希冲突。冲突的解决手段是用链表法：在 bucket 中，从前往后找到第一个空位。这样，在查找某个 key 时，先找到对应的桶，再去遍历 bucket 中的 key。

如果在 bucket 中没找到，并且 overflow 不为空，还要继续去 overflow bucket 中寻找，直到找到或是所有的 key 槽位都找遍了，包括所有的 overflow bucket。

总结：对key进行hash运算取到值，低位也是就hash的右边（具体几位看B）来确定是在哪个桶中，高位也就是hash的左边8位来确定key在桶中的位置。

map的初始化

1. 根据传入的 bucket 类型，获取其类型能够申请的最大容量大小。并对其长度 make(map[k]v, hint) 进行边界值检验
2. 初始化 hmap
3. 初始化哈希因子
4. 根据传入的 hint，计算一个可以放下 hint 个元素的桶 B 的最小值
5. 分配并初始化 hash table。如果 B 为 0 将在后续懒惰分配桶，大于 0 则会马上进行分配
6. 返回初始化完毕的 hmap

当hint<8时，最少一个bucket就可以了，否则，至少需要两个bucket，就需要立刻分配hash table。

扩容

在向 map 插入新 key 的时候，会进行条件检测，符合条件就会触发扩容。

扩容的方式

• 溢出桶太多，相同容量扩容
• 达到加载因子，2倍容量扩容

除了满足两个条件之一外，还要满足“不在扩容中”。

if (不是正在扩容 && (元素个数/bucket数超过某个值 || 太多overflow bucket)) { 进行扩容 }

啥意思呢？第一种出现的情况是：因为map不断的put和delete，出现了很多空格，这些空格会导致bmap很长，但是中间有很多空的地方，扫描时间变长。所以第一种扩容实际是一种整理，将数据整理到前面一起。第二种呢：就是真的不够用了，扩容两倍。

2倍扩容

理想中每个bucket里面只放一个元素，这样最快，但是空间太大。go采用链表解决冲突，但是，如果所有的key都在一个bucket里面，那就退化成了链表，因此需要衡量。

装载因子就是衡量标准， loadFactor := count / (2^B) 当loadFactor为6.5的时候就要扩容。

相同容量扩容

所谓的相同容量扩容，说白了就是不增加bucket的数量，只是整理现在的数据分布。

相同容量扩容的原因是overflow 的 bucket 数量过多： 当 B 小于 15，如果 overflow 的 bucket 数量超过 2^B ；当 B >= 15，如果 overflow 的 bucket 数量超过 2^15 。

其实就是map元素本身不多（达不到加载因子的条件），但是有的bucket的溢出桶overflow太多，这样就造成效率低下。

这样的场景好理解：先添加一些元素，对前面的bucket元素删除，这样就造成大量的bucket不满，整理后可以提高效率。

扩容流程

等量扩容流程

其实元素没那么多，但是 overflow bucket 数特别多，说明很多 bucket 都没装满。解决办法就是开辟一个新 bucket 空间，将老 bucket 中的元素移动到新 bucket，使得同一个 bucket 中的 key 排列地更紧密。

2倍的扩容流程

元素太多，而 bucket 数量太少，很简单：将 B 加 1，bucket 最大数量（2^B）直接变成原来 bucket 数量的 2 倍。于是，就有新老 bucket 了。注意，这时候元素都在老 bucket 里，还没迁移到新的 bucket 来。而且，新 bucket 只是最大数量变为原来最大数量（2^B）的 2 倍（2^B * 2）。

2倍扩容流程，原来的一个bucket会裂变成两个bucket，理由很简单，多看了一位，该位0或1。

不管哪种方式，确定扩容的数量后，扩容本身是慢慢的过程。真正搬迁 buckets 的动作在 growWork() 函数中，而调用 growWork() 函数的动作是在 mapassign 和 mapdelete 函数中。**也就是插入或修改、删除 key 的时候，都会尝试进行搬迁 buckets 的工作。**先检查 oldbuckets 是否搬迁完毕，具体来说就是检查 oldbuckets 是否为 nil。

put

1. hash表如果正在扩容，并且这次要操作的bucket还没搬到新hash表中，那么先进行搬迁（扩容细节下面细说）。

2. 在buck中寻找key，同时记录下第一个空位置，如果找不到，那么就在空位置中插入数据；如果找到了，那么就更新对应的value；

3. 找不到key就看下需不需要扩容，需要扩容并且没有正在扩容，那么就进行扩容，然后回到第一步。

4. 找不到key，不需要扩容，但是没有空slot，那么就分配一个overflow bucket挂在链表结尾，用新bucket的第一个slot放存放数据。

向map插入数据，第一步还是先找bucket，对key取hash，低位找桶，再遍历桶中的数据，如果已经满了就新增一个溢出桶挂上去，如果不满就插入即可。

有一个细节注意，只有进行完了这个搬迁操作后，我们才能放心地在新 bucket 里定位 key 要安置的地址，再进行之后的操作。 找到桶后，应该先看下该桶对应的原始桶是否已经迁移完毕，如果还没迁移完毕，就应该先迁移，然后插入之前再看是否需要扩容（不用担心迁移过程中又要扩容，前面有条件），不需要的话再插。

get

1. 先定位出bucket，如果正在扩容，并且这个bucket还没搬到新的hash表中，那么就从老的hash表中查找。

2. 在bucket中进行顺序查找，使用高八位进行快速过滤，高八位相等，再比较key是否相等，找到就返回value。如果当前bucket找不到，就往下找overflow bucket，都没有就返回零值。

这里我们可以看到，访问的时候，并不进行扩容的数据搬迁。

delete

1. 如果正在扩容，并且操作的bucket还没搬迁完，那么搬迁bucket。

2. 找出对应的key，如果key、value是包含指针的那么会清理指针指向的内存，否则不会回收内存。

其他

• bucket中key为何不直接和value放一起？ 之所以把所有k1k2放一起而不是k1v1是因为key和value的数据类型内存大小可能差距很大，比如map[int64]int8，考虑到字节对齐，kv存在一起会浪费很多空间。

• map遍历为何无序？ map里的数据如果不进行操作，每次遍历应该是一样的，但是扩容以后就会变化。为了统一记忆，所有遍历都是无序。 实现方案就是每次遍历随机指定bucket和bucket中的key offset，这样遍历的位置就是随机的了。

• map是否线程安全？ 不是的，对同一map进行写，会抛异常。

• map的key限制 map的key不能是切片、map、函数。可以为interface{},但是运行时还是不能放这三种；key可以为数组，同样数组元素也不能为这三种。总之，key一定可以是“可比较”类型即可以使用==判断，nil==nil是不合法的，所以map不支持key为nil。另外 map的key占用空间越小，hash的速度越快，操作起来也是更快，尽量别用自定义类型

• 历史版本 在Go 1.6之前， 内置的map类型是部分goroutine安全的，并发的读没有问题，并发的写可能有问题。自go 1.6之后，并发地读写map会报错。牵涉到并发，应该用sync.map

• map桶的数量是2^N，为何一定要是2的指数次幂？ 在定位桶即tab的index时，一般是取余，hashCode % length,但是取余是复杂的操作，当length为2^N时，hashCode % length == hashCode & (length - 1)，这样就转为了更快的与运算。

总结

map的赋值（增和改）会造成扩容。 map扩容和迁移是分开的，迁移是渐进的，map的增，删，改都会进行迁移操作，查找并不能进行数据的搬迁。