HashMap

hashmap是日常开发中最常用的数据结构之一，由于其独特的性质，在许多场景其都能发挥作用，例如去重，快速判断存在性，甚至表示一个对象。而不同平台对于hashmap有着不同的实现，本文将分析Golang语言中的map实现原理。

Java

首先来回顾一下Java中的HashMap，在Java中，hashmap的底层实现为数组+红黑树。
数组的作用，主要是提供随机访问的能力，对于一个Key，通过计算这个key的hash值，再对数组长度取模，就能定位到数组的下标，从而实现随机访问。
而红黑树（链表），则是为了解决hash冲突，如果两个key经过定位后，是同一个下标，那么就产生了hash冲突，Java的解决方法是通过在下标位置拉一个链表的方式。当需要查找一个key时，先定位到数组下标，然后再遍历链表即可。而jdk1.8开始，当链表长度达到一定数量之后，会改为红黑树，提高查询性能。

.NET

而.NET Framework平台的Dictionary也类似(.NET CORE应该是采用了和Java类似的思路，有更好的性能，这里不赘述了)，同样采用了数组+“链表”的方式进行存储，只是.NET下的链表其实也是一个数组。.NET中，有一个buckets数组，其作用就是用来取模，并保存一个”指针“，指向这个bucket对应的value的第一个元素。
下面用一张图展示一下：

原本map中只有a,b两个key，此时它们并不冲突，此时buckets中的value 0,1,就分别代表了这a,b这两个键值对在entrys中的索引。此时，c被插入进来了，其hashcode与a是冲突的，所以这两个元素在buckets取模后，都对应到了0这个索引。而0此时已经被a占据了。此时就需要解决hash冲突。于是我们直接先将c放进entrys数组中，然后将buckets的value改为最新的c的索引，然后将c的next，赋值为a在entrys的索引。

完成之后，我们就可以试着找一下c和a：

• 对于c，首先通过hash以及取模，计算出应该找0这个位置的bucket，然后得到value是2，说明应该从entry的0位置去找，很显然entry[2]正好就是c
• 对于a，先进行同样的步骤，发现entry应该从2开始，但是entry[2]此时是c，并且c的next不为-1，那么就跳转到entry[c.next]的位置，也就是entry[0]。此时就能找到a。

golang map

在Go语言中，map本质上也是一个hash表，但是其底层实现与思路相对前两者有所不同。
首先看一下结构代码：

 type hmap struct {
    count     int    // 元素的个数
    B         uint8  // buckets 数组的长度就是 2^B 个
    noverflow  uint16 // 已使用溢出桶的数量
	
    buckets    unsafe.Pointer // 2^B个桶对应的数组指针
    oldbuckets unsafe.Pointer  // 发生扩容时，记录扩容前的buckets数组指针
	 nevacuate  uintptr // 指示扩容进度，小于此地址的 buckets 迁移完成
    extra *mapextra //用于记录溢出桶相关信息，例如已经使用的溢出桶，下一个溢出桶等
}

首先看看这个B，go中的map第一点的不同就是，其通过hashcode确定bucktes的时候，采用的是与运算的方式：对于一个hashcode，要确定其在一个长度为m的数组的下标位置，需要用hashcode&(m-1)。如果m为2的N次幂，那么m的二进制数中，只有处于N的这一位为1，其余位均为0。那么m-1的二进制数中，则有且仅有低于N的所有位数均为1。如果m不是2的N次幂，那么就可能出现永远有桶不会被取到(其低于N的二进制位永远为0，与运算后这一位也永远为0)。所以，golang中的buckets的长度，永远是2的N次幂，这里的B uint8，就是这个N的值。

这里的buckets是一个指针，直接指向了桶的数组，先看看桶的数据结构长啥样：

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

一个bmap可以装8个键值对，内存排列中，首先是每个键值对的hash值的高8位，然后是分别8个key，分别8个value。以及一个溢出桶的指针。溢出桶数据结构与普通桶子相同，它的作用，是当普通桶子满了，但是溢出桶还有空间时，就将键值对存放在溢出桶中。然而在实际使用中，当map的初始容量大于2^{4时，就认为溢出桶的使用概率比较大，就会预先分配2}(B-4)个溢出桶。并且，这些桶子无论普通桶还是溢出桶，在内存中都是连续分布的。只是前面的用作常规桶子，后面的2^(B-4)用作溢出桶。
而我们再看 extra *mapextra 这个字段：

type mapextra struct {
	// overflow[0] contains overflow buckets for hmap.buckets.
	// overflow[1] contains overflow buckets for hmap.oldbuckets.
	overflow [2]*[]*bmap

	// nextOverflow 包含空闲的 overflow bucket，这是预分配的 bucket
	nextOverflow *bmap
}

当某个bucket满了之后，其overflow字段，就会指向(*extra.nextOverflow)，而nextOverflow这个指针，则会指向下一个空闲的溢出桶。

扩容

前面讲了整体的一个内存结构，现在来看看，golang的map是如何实现扩容的。
不同于Java和.NET，golang采用了一种渐进式rehash的方式。在达到扩容条件时：不会一次性将所有的数据迁移到新的内存地址中。而是首先分配足够的一段连续的内存，用于新的bmap数组的存放。然后用一个oldbuckets记录旧的bmap数组的位置，而nevacuate 则表示已经完成了迁移的bmap数组编号。对map进行读写时，如果检测到正在进行扩容，就完成一部分bmap的迁移工作，直到迁移全部完成，则退出迁移状态。

而判定是否需要进行扩容，则可以根据键值对数量/2^B，这个值也就是负载因子。在Java中，hashmap负载因子为0.75，也就是达到容量75%会扩容。
而go语言稍有不同，负载因子是6.5.，达到之后，就会扩容2倍。

而前面我们提到的与运算，例如一个key的hashcode是XXXXX00，在原先容量为4的bmap数组中，与m-1：00000011进行与运算，可以得到这个key一定被分在0号桶。而扩容之后，
m-1变成了:00000111，此时决定这个key应该去哪个新桶的，就变成了它的第三位，如果第三位为0，则选择为0的新桶，否则选择编号为4的新桶。因为桶的容量为2的N次幂，所以对于每一个桶，其中的元素在扩容后都会有两种选择，这样，就能将原来的键值对，均匀的分布到这个新的容量为原来2倍的所有桶中了。（这里的算法实现思路和Java1.8是一样的哦）

同时，如果使用了较多的溢出桶，但是负载因子没有达到6.5的情况，就会采用另一种扩容方式：等量扩容
如果桶的总数小于2^15，那么当使用的溢出桶的数量，大于常规桶的数量的时候，就算是需要扩容了。
如果桶的总数大于2^{15，那么当溢出桶的数量大于2}15次方的时候就算是需要扩容了

等量扩容就是开辟一段新内存，然后将旧桶迁移到新桶，这样做有什么用呢？

首先需要看看什么场景会出现这种情况：使用了很多溢出桶。
如果有许多键值对被删除，那么就会有许多的空位，这在内存中不是紧密排列的，那么此时可以通过等量扩容，使得内存重新变得紧凑，并且减少溢出桶的使用。