乐趣区

go-map实现

jiezi

golang map 的实现源码在文件 runtime/map.go 中，map 的底层数据结构是 hash 表。
hash 函数：通过指定的函数，将输入值重新生成得到一个散列值
hash 表：散列值会确定其键应该映射到哪一个桶。而一个好的哈希函数，应当尽量少的出现哈希冲突，以此保证操作哈希表的时间复杂度

接下来从下面三个方面讲解：

  • map 数据结构
  • map 查找实现
  • map 插入实现

1. map 的数据结构定义

type hmap struct {count     int //map 存储数据的个数，len(map)使用
    flags     uint8 //flags 会标识当前 map，比如 hashWriting= 4 第 4 位表示有 goroutine 正在往 map 写入
    B         uint8  // map 有 2^B 个 buckets
    hash0     uint32 // hash 算法的 seed

    buckets    unsafe.Pointer // 2^B 个 Buckets 的数组
    oldbuckets unsafe.Pointer // 正在扩容期间，oldbuckets 中有值，map 是增量扩容，不是一次性完成。扩容主要是插入和删除操作会触发
    ......
}

map bucket 的数据结构
一个 bmap 最多存储 8 个 key/value 对, 如果多于 8 个，那么会申请一个新的 bucket，并将它与之前的 bucket 链起来。
tophash 数组存储的 key hash 算法之后的高 8 位值

type bmap struct {
    // bucketCnt = 8
    tophash [bucketCnt]uint8
}

对于 map 的操作，主要用到的是 查找，插入
查找流程

  1. 根据 key hash 之后的值 kHash
  2. 根据 kHash 低八位计算确定 bucket 的内存地址
  3. 遍历该 bucket 的 tophash 数组，找到 tophash[i]等于 kHash 高 8 位的 i 值
  4. 找到 bucket 的第 i 个的 key 与所给的 key 相等。如果相等，则返回其对应的 value。
  5. 遍历完 bucket 没找到，在 overflow buckets 中按照上述方法继续寻找。

查找源码

func mapaccess1(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer {
    // 如果有 goroutine 正在写入 map，则不允许读。所以 map 是非线程安全的
    if h.flags&hashWriting != 0 {throw("concurrent map read and map write")
    }
    ......
    // 确定 key 所在的 bucket 内存地址
    m := bucketMask(h.B)
    b := (*bmap)(add(h.buckets, (hash&m)*uintptr(t.bucketsize)))
    // 如果 oldbuckets 里面有值，从 oldbuckets 取值
    if c := h.oldbuckets; c != nil {oldb := (*bmap)(add(c, (hash&m)*uintptr(t.bucketsize)))
        if !evacuated(oldb) {b = oldb}
    }
    // 获取 key hash 算法之后的高 8 位
    top := tophash(hash)
bucketloop:
    for ; b != nil; b = b.overflow(t) {//bucketCnt = 8，遍历 tophash 数组，tophash[i]等于 kHash 高 8 位的 i 值 并且 bucket 的第 i 个的 key 与所给的 key 相等的 value 值
        for i := uintptr(0); i < bucketCnt; i++ {if b.tophash[i] != top {continue}
            // 对比 bucket 的第 i 个的 key 与所给的 key 是否相等，相等就取对应的 value 值
            k := add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize))
            if alg.equal(key, k) {v := add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+i*uintptr(t.valuesize))
                return v
            }
        }
    }
    return unsafe.Pointer(&zeroVal[0])
}

插入流程
返回写入 value 值的内存地址
插入流程跟查找类似，

  1. 置位 flags hashWriting 位为 1
  2. 根据 key hash 之后的值 kHash
  3. 根据 kHash 低八位计算确定 bucket 的内存地址
  4. 判断是否正在扩容，若正在扩容中则先迁移再接着处理
  5. 遍历 bucket 和 overbucket 的 bmap，记录第一个空槽，并把该位置标识为可插入 tophash 位置，这里就是第一个可以插入数据的地方。如果找到匹配的 key 值 k，则返回该 k 对应的 value 值地址
  6. 如果 bucket 已经 full，则申请新的 bucket 作为 overbucket，插入 key/value 键值对。
  7. map 没有正在扩容 && 触发最大 LoadFactor && 有过多溢出桶 overflow buckets，则会触发扩容

map 插入的源码 mapassign，返回写入 value 值的地址

func mapassign(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer {
    .....
again:
    // 根据 hash 值，确定 bucket
    bucket := hash & bucketMask(h.B)
    if h.growing() {
        // 是否正在扩容，若正在扩容中则先迁移再接着处理
        growWork(t, h, bucket)
    }
    b := (*bmap)(unsafe.Pointer(uintptr(h.buckets) + bucket*uintptr(t.bucketsize)))
    top := tophash(hash)
bucketloop:
    for {
        // 遍历 bucket 的 bitmap
        for i := uintptr(0); i < bucketCnt; i++ {if b.tophash[i] != top {
                //tophash 第 i 位没有赋值，并且是空槽，则记录下来，这是可以插入新 key/value 值的地址
                if isEmpty(b.tophash[i]) && inserti == nil {inserti = &b.tophash[i]
                    insertk = add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize))
                    val = add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+i*uintptr(t.valuesize))
                }
                if b.tophash[i] == emptyRest {break bucketloop}
                continue
            }
            //tophash 第 i 位等于 key hash 值的高 8 位，k := add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize))
            //key 和 k 不匹配，继续遍历下一个 k
            if !alg.equal(key, k) {continue}
            // map 中已经存在 key，value 值
            val = add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+i*uintptr(t.valuesize))
            goto done
        }
        //bucket 不符合条件，开始遍历 overbucket
        ovf := b.overflow(t)
        b = ovf
    }

    //map 没有正在扩容 && 触发最大 LoadFactor && 有过多溢出桶 overflow buckets，则会触发扩容
    if !h.growing() && (overLoadFactor(h.count+1, h.B) || tooManyOverflowBuckets(h.noverflow, h.B)) {hashGrow(t, h)
        goto again // Growing the table invalidates everything, so try again
    }
退出移动版