map 原理

本文大部分内容摘抄自 Go Questions.

在计算机科学里，被称为相关数组、map、符号表或者字典，是由一组 <key, value> 对组成的抽象数据结构，并且同一个 key 只会出现一次。
有两个关键点：是由 key-value 对组成的；key 只会出现一次。

哈希查找表用一个哈希函数将 key 分配到不同的桶（bucket，也就是数组的不同 index）。这样，开销主要在哈希函数的计算以及数组的常数访问时间。在很多场景下，哈希查找表的性能很高。

哈希查找表一般会存在“碰撞”的问题，就是说不同的 key 被哈希到了同一个 bucket。一般的处理方法是链表法。链表法将一个 bucket 实现成一个链表，落在同一个 bucket 中的 key 都会插入这个链表。

map 实现原理

// A header for a Go map.
type hmap struct {
       // 元素个数，调用 len(map) 时，直接返回此值
    count     int
       // 如值为 1 表明有 goroutine 正在进行写操作(以阻止多 goroutine 同时操作 map)
       flags     uint8
       // buckets 的对数 log_2 
       B         uint8
       // ...
 
      // 指向 buckets 数组，大小为 2^B
      // 如果元素个数为0，就为 nil
    buckets    unsafe.Pointer
      // ...
}

B 在用 make 初始化 map 的时候确定：

func makemap(....) *hmap {
       // ...
    // 找到一个 B，使得 map 的装载因子在正常范围内
    B := uint8(0)
    for ; overLoadFactor(hint, B); B++ {
    }
       // ...
}

buckets 是一个指针，最终它指向的是一个结构体：

type bmap struct { 
    keys     [8]keytype
    values   [8]valuetype
    overflow uintptr
    // ...
}

bmap 就是我们常说的“桶”。每个 bucket 设计成最多只能放 8 个 key-value 对，如果有第 9 个 key-value 落入当前的 bucket，那就需要再构建一个 bucket ，通过 overflow 指针连接起来。

key 的定位

key 经过哈希计算后得到哈希值，共 64 个 bit 位，再用最后 B 个 bit 位计算它到底要落在哪个桶。

前面提到过 B，如果 B = 5，那么桶的数量，也就是 buckets 数组的长度是 2^5 = 32。假设最后 5 个 bit 为 01010 -> 10，就意味着落在 10 号桶里。

当两个不同的 key 落在同一个桶中，也就是发生了哈希冲突。冲突的解决手段是用链表法：在 bucket 中，从前往后找到第一个空位。这样，在查找某个 key 时，先找到对应的桶，再去遍历 bucket 中的 key。如果在 bucket 中没找到，并且 overflow 不为空，还要继续去 overflow bucket 中寻找(遍历所有的 bucket，这相当于是一个 bucket 链表)。

赋值、更新和删除

对 key 计算 hash 值，根据 hash 值按照 key 定位的流程，找到要操作的位置（可能是插入新 key，也可能是更新老 key），对相应位置进行赋值、更新或删除即可。

注意这些操作都会先检查 flags 标志，如果发现写标位是 1，直接 panic，因为这表明有其他 goroutine 同时在进行写操作。

遍历

遍历所有的 bucket 以及它后面挂的 overflow bucket，然后挨个遍历 bucket 中的所有 cell。每个 bucket 中包含 8 个 cell，从有 key 的 cell 中取出 key 和 value，这个过程就完成了。

上述为最简单的遍历过程，但因为扩容过程不是一个原子的操作，所以如果遍历的同时触发了扩容操作，那么在很长时间里，map 的状态都是处于一个中间态。此时遍历就会变得很复杂。

map 的遍历是无序的

map 在扩容时会使位置发生变化。

当我们在遍历 map 时，并不是固定地从 0 号 bucket 开始遍历，每次都是从一个随机值序号的 bucket 开始遍历，并且是从这个 bucket 的一个随机序号的 cell 开始遍历。这样，即使你是一个写死的 map，仅仅只是遍历它，也不太可能会返回一个固定序列的 key/value 对了。

扩容

使用哈希表的目的就是要快速查找到目标 key，最理想的情况是一个 bucket 只装一个 key，这样，就能达到 O(1) 的效率，最差情况是所有 key 都落在同一个 bucket 里，退化成了链表，各种操作的效率直接降为 O(n)。

扩容的时机：在向 map 插入新 key 的时候，会按如下 2 条规则检查是否进行扩容：

1. 装载因子超过阈值，表明很多 bucket 都快要装满了，查找效率和插入效率都变低了。源码里定义的阈值是 6.5
2. 较复杂，省略 ...

装载因子计算方式：

loadFactor := count / (2^B)

count 就是 map 的元素个数，2^B 表示 bucket 数量。
具体扩容采用“渐进”的方式使 buckets 数量扩大 2 倍，较复杂，省略 ...

key 的类型

可以是:
• 布尔值
• 数字: 整型（int/uint/int8/uint8/int16/uint16/int32/uint32/int64/uint64/byte/rune等）、浮点数（float32/float64）、复数类型（complex64/complex128）
• 字符串
• 指针
• 通道
• 接口类型
• 结构体(成员变量类型只能是支持的类型)
• 数组(具体类型只能是支持的类型)

但不能是：
• slice，元素可能存在自引用(如 []interface{} 切片元素为自己)；即使底层数组相同，len和cap也可能不同。
• map，value 可能是不可比较类型，如 slice
• function

key 类型只要能支持 == 和 != 操作符，即可以做为Key，当两个值 == 时，则认为是同一个 key。

注意

map 并不是一个线程安全的数据结构。同时读写一个 map 是未定义的行为，如果被检测到，会直接 panic。
在同一个协程内边遍历边删除，并不会检测到同时读写，理论上是可以这样做的，但不要这样做。
无法直接对 map 的 value 进行取址。
map 不是线程安全的，可以用 sync.Map