深入理解Golang之Map

写在前面

Map的实现主要有两种方式：哈希表（hash table）和搜索树（search tree）。例如Java中的hashMap是基于哈希表实现，而C++中的Map是基于一种平衡搜索二叉树——红黑树而实现的。Go中map的基于哈希表（也被称为散列表）实现。

哈希函数

哈希函数（常被称为散列函数）是可以用于将任意大小的数据映射到固定大小值的函数，它是根据关键字设计的，有很多函数，主要原理就是根据数组的大小求模运算。
（关键字）%（数组的大小）
数组的大小一般设计为质数，因为需要均匀的散布

如何解决哈希冲突的问题？

1.链表地址法

写结构体的时候加入next指针

遇到冲突时，将数据写到next的位置

下面以一个简单的哈希函数 H(key) = key MOD 7（除数取余法）对一组元素 [50, 700, 76, 85, 92, 73,101] 进行映射，通过图示来理解链地址法处理Hash冲突的处理逻辑。

2.开放地址法

把其他下标的地址都对外开放
开放地址的方法：1.线性探测法2.平方探测（二次方探测）3.双哈希

开放地址—线性探测法

如果遇到冲突，就往下一个地址寻找空位，新位置=原始位置+i ( i是查找的次数 )

其中15，2，28，4进行模运算，都为2，遇到冲突，就会往下一个地址寻找空位
12，38进行模运算，都为12，遇到冲突，就会往下一个地址寻找空位

开放地址—平方探测法

如果遇到冲突，就往（原地址 + i ² ）的位置寻找空位，新位置=原始位置+ i ² ( i是查找的次数 )

开放地址—双哈希

要设置第二个哈希的函数，例如：hash2(key)=R-(key mod R)
R要取比数组尺寸小的指指数
例如R取7 hash2(关键字)=7-（关键字%7）
如果遇到冲突，新位置=原始位置+i*hash2(关键字)

哈希表满了怎么办？

再次哈希

• 当哈希表数据存储量超过70%，那么就自动新建一个新的哈希表
• 新表的尺寸是旧表的2倍以上，选择一个质数
• 把之前的数据再次通过哈希计算搬到新表里

Go Map实现

map数据结构

map中的数据被存放于一个数组中的，数组的元素是桶（bucket），每个桶至多包含8个键值对数据。哈希值低位（low-order bits）用于选择桶，哈希值高位（high-order bits）用于在一个独立的桶中区别出键。哈希值高低位示意图如下

Go语言中的map是也基于哈希表实现的，它解决哈希冲突的方式是链地址法，即通过使用数组+链表的数据结构来表达map

map的结构体为hmap

// A header for a Go map.
type hmap struct {
    count     int // 代表哈希表中的元素个数，调用len(map)时，返回的就是该字段值。
    flags     uint8 // 状态标志，下文常量中会解释四种状态位含义。
    B         uint8  // buckets（桶）的对数log_2（哈希表元素数量最大可达到装载因子*2^B）
    noverflow uint16 // 溢出桶的大概数量。
    hash0     uint32 // 哈希种子

    buckets    unsafe.Pointer // 指向buckets数组的指针，数组大小为2^B，如果元素个数为0，它为nil。
    oldbuckets unsafe.Pointer // 如果发生扩容，oldbuckets是指向老的buckets数组的指针，老的buckets数组大小是新的buckets的1/2。非扩容状态下，它为nil。
    nevacuate  uintptr        // 表示扩容进度，小于此地址的buckets代表已搬迁完成。

    extra *mapextra // 这个字段是为了优化GC扫描而设计的。当key和value均不包含指针，并且都可以inline时使用。extra是指向mapextra类型的指针。
1
2
3
4
5
6
7
8
9
10
11
12
13

bmap结构体（map的桶）

// A bucket for a Go map.
type bmap struct {
    // tophash包含此桶中每个键的哈希值最高字节（高8位）信息（也就是前面所述的high-order bits）。
    // 如果tophash[0] < minTopHash，tophash[0]则代表桶的搬迁（evacuation）状态。
    tophash [bucketCnt]uint8
}
1
2
3
4
5
6

在8个键值对数据后面有一个overflow指针，因为桶中最多只能装8个键值对，如果有多余的键值对落到了当前桶，那么就需要再构建一个桶（称为溢出桶），通过overflow指针链接起来。溢出桶的内存布局和常规桶相同，是为了减少扩容次数而引入的，当一个桶存满了还有可用的溢出桶时，就会在桶后面链一个溢出桶