go map

Created

2024-10-28 13:23:19

Updated

2024-10-28 13:23:23

Caution

源码方面看的是不支持泛型的版本. 未完待续…

1 图书馆与map

Diagram
map 图书馆对应
桶 一个个分类不同的书架
哈希算法 你根据书名进行判断的判断方法,知道是哪个分类, 放到哪个书架上
哈希冲突 多本书,根据书名进行判断,都在同一个分类书架上,就依次放到书架上的空余位置即可
如果该书架满了,则需要新的同分类名的书架,将书放到这个新的书架上.
读取数据 你根据书名进行判断,知道是哪个分类书架,然后到该书架上
从左到右比对过去,比对书名(ISBN),找到并拿走
写入数据 你根据书名进行判断,知道是哪个分类书架,然后到该书架上
从左到右比对过去,比对书名(ISBN),如果有,则更换书,没有就放入最右边空余位置
装载因子
(元素个数/桶数量<=6.5)		 很显然书架上的书越多,你找书就越慢,
如果每个书架上都只有一个本书, 那么你一定非常快就找到了.

2 源码分析

2.1 数据结构

func main() {
    a := make(map[int]string, 10)
    fmt.Println(a)
}
Tip

go tool compile -S main.go 查看汇编代码可以看到 runtime.makemap
容量小的话,可以看到runtime.makemap_small

func makemap(t *maptype, hint int, h *hmap) *hmap {
    mem, overflow := math.MulUintptr(uintptr(hint), t.bucket.size)
    if overflow || mem > maxAlloc {
        hint = 0
    }
    if h == nil {
        h = new(hmap)
    }
    h.hash0 = fastrand()
    B := uint8(0)
    for overLoadFactor(hint, B) {
        B++
    }
    h.B = B

    if h.B != 0 {
        var nextOverflow *bmap
        h.buckets, nextOverflow = makeBucketArray(t, h.B, nil)
        if nextOverflow != nil {
            h.extra = new(mapextra)
            h.extra.nextOverflow = nextOverflow
        }
    }
    return h
}
src/runtime/map.go
type hmap struct {
    // map 中的元素个数，必须放在 struct 的第一个位置，
    // 因为内置的 len 函数会通过unsafe.Pointer会从这里读取
    count     int
    flags     uint8
    // bucket的数量是2^B, 最多可以放 loadFactor * 2^B 个元素，再多就要 hashGrow 了
    // 装载因子 loadFactor= 元素个数/桶数量<=6.5
    B         uint8
    //overflow 的 bucket 近似数
    noverflow uint16
    hash0     uint32 // hash seed
    //2^B 大小的数组指针，如果 count == 0 的话，可能是 nil
    buckets    unsafe.Pointer
    // 扩容的时候，buckets 长度会是 oldbuckets 的两倍,只有在 growing 时候为空。
    oldbuckets unsafe.Pointer
    // 指示扩容进度，小于此地址的 buckets 迁移完成
    nevacuate  uintptr // progress counter for evacuation (buckets less than this have been evacuated)
    // 当 key 和 value 都可以 inline 的时候，就会用这个字段
    extra *mapextra // optional fields
}
src/runtime/map.go
type bmap struct {
    // 存储了键的哈希的高 8 位
    tophash [bucketCnt]uint8
}

上面这个数据结构并不是 golang runtime 时的结构，在编译时候编译器会给它动态创建一个新的结构
因为哈希表中可能存储不同类型的键值对，而且 Go 语言也不支持泛型，所以键值对占据的内存空间大小只能在编译时进行推导

// 每个 bucket 里面最多存储 8 个 key
type bmap struct {
    topbits  [8]uint8 //key 计算出来的 hash 值的高 8 位
    keys     [8]keytype
    values   [8]valuetype
    pad      uintptr
    overflow uintptr
}
Diagram
  • 为什么 桶内的key和value 要这样设计? 我们以 map[int64]int8 为例来说明
    • 如果按照 key/value/key/value/… 这样的模式存储，由于内存对齐,在每一个 key/value 之后都要额外需要7个字节
    • int64 8个字节 int8一个字节, 剩下的7个字节就浪费了. 因为接下来的key 8个字节你放不下
    • 而将所有的 key，value 分别绑定到一起，这种形式 key/key/…/value/value/…，则只需要在最后添加 pad
  • 每个 bucket 设计成最多只能放 8 个 key-value 对，如果有第 9 个 key-value 落入当前的 bucket，那就需要再构建一个 bucket ，通过 overflow 指针连接起来

2.2 B值的计算

2.2.1 源码解析

这里我们创建10个容量的map
func main() {
    a := make(map[int]string, 10)
    fmt.Println(a)
}
B := uint8(0)
// hint 就是 10
// 如果当前元素/桶数 超过了装载因子6.5 则说明桶数不够,需要增加,B++
for overLoadFactor(hint, B) {
    B++
}
// 判断是否超过了装载因子
func overLoadFactor(count int, B uint8) bool {
    // bucketCntBits = 3
    // bucketCnt     = 1 << bucketCntBits  //1 左移3位 = 8
    // 得出 bucketCnt = 8
    // loadFactorNum = 13
    // loadFactorDen = 2
    // count>bucketCnt 如果容量> 一个桶能放的元素数
    // 且 第一次循环, B=0, 10>13*(1/2) 一个桶最多6.5 ,我们装载因为是6.5,超过了,说明需要扩容桶
    // 则第二循环, B=1, bucketShift(B)= 1<<1=2 , 10>13*(2/2) 不城里,退出循环了, 结果是B=1
    return count > bucketCnt && uintptr(count) > loadFactorNum*(bucketShift(B)/loadFactorDen)
}
func bucketShift(b uint8) uintptr {
    // Masking the shift amount allows overflow checks to be elided.
    return uintptr(1) << (b & (8*8 - 1))
}

2.2.2 代码验证

package main
import (
    "fmt"
    "unsafe"
)
type MapStruct struct {
    count int
    flags uint8
    B     uint8
    noverflow  uint16
    hash0      uint32
    buckets    uintptr //unsafe.Pointer
    oldbuckets unsafe.Pointer
    nevacuate  uintptr
    extra      uintptr
}
func main() {
    m := make(map[int32]int32, 10)
    // m 实际是个指针, 指向了真正的hmap
    m[1] = 22
    m[2] = 33
    fmt.Println(len(m)) //2
    hmapReal := *(**MapStruct)(unsafe.Pointer(&m))
    fmt.Println(hmapReal.count, hmapReal.B) // 2 1
    bks := hmapReal.buckets
    for i := 0; i < (1 << hmapReal.B); i++ {
        // bmap的size=88
        kbase := bks + uintptr(i*88)
        for j := 0; j < 8; j++ {
            fmt.Println("key=", *(*int32)((unsafe.Pointer)(kbase + uintptr(8+j*4))))
            fmt.Println("val=", *(*int32)((unsafe.Pointer)(kbase + uintptr(8+8*4+j*4))))
        }

    }
}

2.3 访问

2.3.1 for range 为啥是随机的

package main

import (
    "fmt"
)
func main() {
    m := make(map[int32]int32, 10)
    m[1] = 22
    m[2] = 33
    m[3] = 44
    m[4] = 55
    m[5] = 66
    for k, v := range m {
        fmt.Println(k, v)
    }
}

查看汇编 可以看到 写入map 的相关函数runtime.mapassign_fast32
range 的相关函数 runtime.mapiterinit

mapiterinit()
func mapiterinit(t *maptype, h *hmap, it *hiter) {
    ...
    ...
    // decide where to start
    r := uintptr(fastrand())
    if h.B > 31-bucketCntBits {
        r += uintptr(fastrand()) << 31
    }
    it.startBucket = r & bucketMask(h.B)
    it.offset = uint8(r >> h.B & (bucketCnt - 1))

    // iterator state
    it.bucket = it.startBucket
}

2.4 扩容

2.4.1 为什么需要扩容

桶里key 多起来了,8个满了, 再overflow 整个几个. 你查询起来就慢了. 需要遍历桶里的元素, 这就是有装载因子的判断

2.4.2 渐进式扩容

Back to top