[go]map

map的实现细节

//初始化: 最重要的肯定就是确定一开始要有多少个桶，初始化哈希种子等等

func makemap_small() *hmap {
    h := new(hmap)
    h.hash0 = fastrand()
    return h
}

// makemap implements Go map creation for make(map[k]v, hint).
func makemap(t *maptype, hint int, h *hmap) *hmap {
    .....

    // initialize Hmap
    if h == nil {
        h = (*hmap)(newobject(t.hmap))
    }
    h.hash0 = fastrand()

    // find size parameter which will hold the requested # of elements
    B := uint8(0)
    for overLoadFactor(hint, B) {
        B++
    }
    h.B = B
    
    ......
    return h
}

• 存储逻辑结构
  

• map数据结构

// A header for a Go map.
type hmap struct {
    count      int            // len()返回的map的大小 即有多少kv对
    flags      uint8
    B          uint8          // 表示hash table总共有2^B个buckets 
    hash0      uint32         // hash seed
    buckets    unsafe.Pointer // 按照low hash值可查找的连续分配的数组，初始时为16个Buckets. 当bucket(桶为0时)为nil
    oldbuckets unsafe.Pointer
    nevacuate  uintptr
    overflow   *[2]*[]*bmap //溢出链 当初始buckets都满了之后会使用overflow
}

// A bucket for a Go map.

type bmap struct {
    tophash [bucketCnt]uint8
    keys     [8]keytype    // 第二个是8个key、8个value
    values   [8]valuetype  
    pad      uintptr
    overflow uintptr      // 第三个是溢出时，下一个溢出桶的地址
}
// 注意: key、value、overflow字段都不显示定义，而是通过maptype计算偏移获取的。

注: 
    之所以把所有k1k2放一起而不是k1v1是因为key和value的数据类型内存大小可能差距很大，
    比如map[int64]int8，考虑到字节对齐，kv存在一起会浪费很多空间。

GET

1. 计算出key的hash

2. 用最后的“B”位来确定在哪个桶（“B”就是前面说的那个，B为4，就有16个桶，0101用十进制表示为5，所以在5号桶）

3. 根据key的前8位快速确定是在哪个格子（额外说明一下，在bmap中存放了每个key对应的tophash，是key的前8位）

4. 最终还是需要比对key完整的hash是否匹配，如果匹配则获取对应value

5. 如果都没有找到，就去下一个overflow找

PUT

1. 通过key的后“B”位确定是哪一个桶

2. 通过key的前8位快速确定是否已经存在

3. 最终确定存放位置，如果8个格子已经满了，没地方放了，那么就重新创建一个bmap作为溢出桶连接在overflow

[go]map

原文：https://www.cnblogs.com/iiiiiher/p/12190108.html