Golang map的实现

本文是《Go专家编程》的阅读笔记

1. map的数据结构

Golang底层使用哈希表实现map，哈希表有多个节点，每个节点就一个bucket（桶），每个bucket可以存储最多8对key-value。

type hmap struct {
    count int // 哈希表中的元素个数
    ...
    B     int // 当前的负载因子
    ...
    buckets unsafe.Pointer // 桶数组指针
    oldbuckets unsafe.Pointer // 扩容前的桶
    ...
}

hmap.buckets的长度是2^B

2. bucket的数据结构

const (
    // Maximum number of key/elem pairs a bucket can hold.
    bucketCntBits = 3
    bucketCnt     = 1 << bucketCntBits // 8
)
type bmap struct {
    tophash [bucketCnt]uint8 // 存储哈希值的高8位
    // 以下两个属性是虚构的，在bmap结构中不存在
    data    byte[1] // key value数据：key/key/key.../value/value/value
    overflow *bmap // 溢出桶的地址
}

每个bucket最多存储bucketCnt=8 个键值对

• tophash是长度为8的uint8数组，哈希值低位相同的键存入当前bucket时会将哈希值的高位存储在该数组中，以方便后续匹配 。
• data存放的是key-value数据，存放的顺序是key/key/key…/value/value/value，这样存放能够节省字节对齐带来的空间浪费。
• overflow是溢出桶的地址，据此将溢出桶形成链表。

3. 哈希冲突

多个哈希值的低位相同命中同一个桶，桶中的键值对超过8个，只能再创建一个键值对存放溢出桶的地址，Golang就是通过这样的链地址法来解决哈希冲突的。

4. 负载因子

负载因子用于描述哈希冲突的情况：
负载因子=键数量/桶数量
哈希表需要将负载因子控制在合适的大小，超过其阀值需要进行rehash，也即键值对重新组织：

• 负载因子过小，空间利用率低。
• 负载因子过大，元素存取效率低。过大表示哈希冲突严重，溢出桶形成的链表很长，在链表中查询位置是较慢的。