go语言map底层及扩容机制原理详解(上)

底层数据结构-哈希表

go语言map的底层数据结构是哈希表：通过哈希表来存储键值对，通过hash函数把键值对散列到一个个桶(bucket)中。

什么是哈希表？

• 在顺序结构以及平衡树中，元素与其的存储位置之间没有对应关系，因此查找一个元素时，必须进行多次比较。所以顺序查找的时间复杂度为O(N)，而平衡树中则为树的高度O(log2N)。
• 为了减少搜素时元素比较的次数，是否有一种方法可以不经过任何比较，通过元素的存储位置与它的关键码以O(1)的时间复杂度直接找到该元素呢？
• 哈希表就是通过某种函数(hash)来使元素的存储位置和其元素值之间建立一一映射的关系，那么就可以通过这种关系快速找到该元素。(数组就是一种简单的哈希表)

如何处理哈希冲突？

• 当两个或多个健具有相同的哈希值，即为出现了哈希冲突，它们会被存放在同一个桶中。go采用拉链法来解决哈希冲突的问题，即在同一个桶内部通过链接(链表)存储所有冲突的键值对。
• 不过拉链法在当哈希冲突出现的次数相当频繁时，会将常数级的时间复杂度上升甚至到线性级。加载因子的出现就是为了避免过多的哈希冲突导致哈希表的退化。

无序性

• 由于go语言的map是通过哈希表来实现的，由于哈希函数的特性，是无法依据一定的顺序来存储的。因此go的map是无序的。

map的扩容机制

在哈希表中，当元素达到一定的数量(超过加载因子设定的比例)，为了保持操作的效率，需要对哈希表进行扩容。扩容通常需要创建一个更大的哈希表，并将现有元素重新映射到新表中。

底层实现

type hmap struct {
	count     int    // 元素的个数
	B         uint8  // buckets 数组的长度就是 2^B 个
	overflow uint16 // 溢出桶的数量
 
	buckets    unsafe.Pointer // 2^B个桶对应的数组指针
	oldbuckets unsafe.Pointer  // 发生扩容时，记录扩容前的buckets数组指针
 
	extra *mapextra //用于保存溢出桶的地址
}

type mapextra struct {
	overflow    *[]*bmap
	oldoverflow *[]*bmap
 
	nextOverflow *bmap
}

type bmap struct {
	tophash [bucketCnt]uint8
}
 
//在编译期间会产生新的结构体
type bmap struct {
    tophash [8]uint8 //存储哈希值的高8位
    data    byte[1]  //key value数据:key/key/key/.../value/value/value...
    overflow *bmap   //溢出bucket的地址
}

在go的map实现中，它的底层结构体是hmap，hmap里维护着若干个bucket数组 (即桶数组)。每个桶中保存了8个键值对，如果8个满了，又来了一个kv到了这个桶中，会使用overflow连接下一个桶，即桶溢出。

• 对于哈希冲突：当两个不同的key落到了同一个桶中就是发生了哈希冲突，则会采用拉链法，从前往后找一个空位进行插入。如果桶满了，当前桶就会连接到下一个溢出桶。

扩容基本步骤

1. 触发扩容：
   • 当向map中添加新元素时，如果元素数量超过了当前哈希表容量和加载因子的乘积，就会触发扩容。加载因子是一个决定性能与内存使用之间的阈值，防止哈希表的退化。
2. 分配新表
   • go在运行是会创建一个新的哈希表，其容量为原来的两倍。这样做可以减少再次扩容的可能，并提供足够的空间来避免过多的哈希冲突。
3. 数据迁移
   • 将旧哈希表中的现有元素迁移到新表中。每个元素的哈希中将根据新表的大小容量重新计算，来确定它们在新表的位置。
   • 当map非常大的情况下，每次迁移所有的元素，会出现长时间的暂停。在go1.8版本之后，这个步骤是渐进式的：每次向map`添加新元素或查找时，都会迁移一小部分元素，避免长时间的暂停。
4. 更新引用
   • 当所有元素都迁移到新的哈希表中后，原来的哈希表将会被丢弃，map的内部引用将指向新表。

总结

1. 要提供合适的初始容量。
   由于每次扩容时，需要重新计算所有元素的哈希值并将它们分配到新的桶中，这是一个相当花时间的操作。因此，如果我们事先知道map大约会存储多少数据，可以实现在创建map时通过提供合适的初始容量来减少扩容次数，从而提高map的性能:
   myMap := make(map[string]int, initialCapacity)