In-depth understanding of Golang's Map

写在前面

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

哈希函数

哈希函数（常被称为散列函数）是可以用于将任意大小的数据映射到固定大小值的函数,It is designed based on keywords,有很多函数,The main principle is to find the modulo operation according to the size of the array.
（关键字）%（数组的大小）
数组的大小一般设计为质数,因为需要均匀的散布

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

1.链表地址法

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

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

Below is a simple hash function H(key) = key MOD 7（除数取余法）对一组元素 [50, 700, 76, 85, 92, 73,101] 进行映射,Understand the chain address method processing through the diagramHashConflict handling logic.

2.开放地址法

All other subscripted addresses are open to the public
开放地址的方法：1.线性探测法2.平方探测（二次方探测）3.双哈希

开放地址—线性探测法

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

其中15,2,28,4进行模运算,都为2,遇到冲突,It will look for a vacancy at the next address
12,38进行模运算,都为12,遇到冲突,It will look for a vacancy at the next address

开放地址—平方探测法

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

开放地址—双哈希

The function to set the second hash to,例如：hash2(key)=R-(key mod R)
RTo take the index smaller than the size of the array
例如R取7 hash2(关键字)=7-（关键字%7）
如果遇到冲突,新位置=原始位置+i*hash2(关键字)

哈希表满了怎么办？

再次哈希

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

Go Map实现

map数据结构

mapThe data in is stored in an array,The elements of the array are buckets（bucket）,Each bucket contains at most 8个键值对数据.Hash value low（low-order bits）for selecting buckets,Hash value high（high-order bits）Used to distinguish keys in a separate bucket.The schematic diagram of the high and low levels of the hash value is as follows

Go语言中的mapIt is also implemented based on a hash table,The way it resolves hash collisions is the chain address method,i.e. by using an array+A linked list data structure to expressmap

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类型的指针.

bmap结构体（map的桶）

// A bucket for a Go map.
type bmap struct {
    
    // tophashContains the highest byte of the hash value for each key in this bucket（高8位）信息（也就是前面所述的high-order bits）.
    // 如果tophash[0] < minTopHash,tophash[0]It represents the relocation of the barrel（evacuation）状态.
    tophash [bucketCnt]uint8
}

在8个键值对数据后面有一个overflow指针,因为桶中最多只能装8个键值对,如果有多余的键值对落到了当前桶,那么就需要再构建一个桶（称为溢出桶）,通过overflow指针链接起来.The memory layout of overflow buckets is the same as regular buckets,It was introduced to reduce the number of expansions,When a bucket is full and there are overflow buckets available,就会在桶后面链一个溢出桶