资料来源：
- https://github.com/WuPeiqi/go_course
- 源码 /src/runtime/map
- Golang map源码详解_风神韵-CSDN博客_go map 源码
map的基本结构
图源[1]
图源[3]
其中hmap的源码[2]
// A header for a Go map.
type hmap struct {
// Note: the format of the hmap is also encoded in cmd/compile/internal/gc/reflect.go.
// Make sure this stays in sync with the compiler's definition.
// 键值对个数
count int // # live cells == size of map. Must be first (used by len() builtin)
flags uint8
// 桶的个数为2的B次方
B uint8 // log_2 of # of buckets (can hold up to loadFactor * 2^B items)
noverflow uint16 // approximate number of overflow buckets; see incrnoverflow for details
// 哈希因子
hash0 uint32 // hash seed
// 桶
buckets unsafe.Pointer // array of 2^B Buckets. may be nil if count==0.
oldbuckets unsafe.Pointer // previous bucket array of half the size, non-nil only when growing
nevacuate uintptr // progress counter for evacuation (buckets less than this have been evacuated)
extra *mapextra // optional fields
}每一个桶总共能存放8个key和8个value
// A bucket for a Go map.
type bmap struct {
// tophash generally contains the top byte of the hash value
// for each key in this bucket. If tophash[0] < minTopHash,
// tophash[0] is a bucket evacuation state instead.
tophash [bucketCnt]uint8
// Followed by bucketCnt keys and then bucketCnt elems.
// NOTE: packing all the keys together and then all the elems together makes the
// code a bit more complicated than alternating key/elem/key/elem/... but it allows
// us to eliminate padding which would be needed for, e.g., map[int64]int8.
// Followed by an overflow pointer.
}
map的初始化
以make(map[string]string,10)为例
-
第一步：创建一个hmap结构体对象。
-
第二步：生成一个哈希因子hash0 并赋值到hmap对象中（用于后续为key创建哈希值）。
-
第三步：根据hint=10，并根据算法规则来创建 B，当前B应该为1。
-
第四步：根据B去创建去创建桶（bmap对象）并存放在buckets数组中，当前bmap的数量应为2
- 当B<4时，根据B创建桶的个数的规则为：$2^B$（标准桶）
- 当B>=4时，根据B创建桶的个数的规则为：$2^B$ + $2^{B-4}$（标准桶+溢出桶）
注意：每个bmap中可以存储8个键值对，当不够存储时需要使用溢出桶，并将当前bmap中的overflow字段指向溢出桶的位置。
map的写入数据
- 第一步：结合哈希因子和键生成哈希值
011011100011111110111011011 - 第二步：获取哈希值的后B位，并根据后B为的值来决定将此键值对存放到那个桶中（bmap）
将哈希值和桶掩码（B个为1的二进制）进行 & 运算，最终得到哈希值的后B位的值。假设当B为1时，其结果为 0 ：
哈希值：011011100011111110111011010
桶掩码：000000000000000000000000001
结果： 000000000000000000000000000 = 0通过示例你会发现，找桶的原则实际上是根据后B为的位运算计算出 索引位置，然后再去buckets数组中根据索引找到目标桶（bmap)
- 第三步：在上一步确定桶之后，接下来就在桶中写入数据
获取哈希值的tophash（即：哈希值的`高8位`），将tophash、key、value分别写入到桶中的三个数组中。
如果桶已满，则通过overflow找到溢出桶，并在溢出桶中继续写入。注意：以后在桶中查找数据时，会基于tophash来找（tophash相同则再去比较key）。
- 第四步：hmap的个数count++（map中的元素个数+1）
源码如下 v := map[key]
// mapaccess1 returns a pointer to h[key]. Never returns nil, instead
// it will return a reference to the zero object for the elem type if
// the key is not in the map.
// NOTE: The returned pointer may keep the whole map live, so don't
// hold onto it for very long.
func mapaccess1(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer {
if raceenabled && h != nil {
callerpc := getcallerpc()
pc := funcPC(mapaccess1)
racereadpc(unsafe.Pointer(h), callerpc, pc)
raceReadObjectPC(t.key, key, callerpc, pc)
}
if msanenabled && h != nil {
msanread(key, t.key.size)
}
if h == nil || h.count == 0 {
if t.hashMightPanic() {
t.hasher(key, 0) // see issue 23734
}
return unsafe.Pointer(&zeroVal[0])
}
// 判断是否正在写入数据
if h.flags&hashWriting != 0 {
throw("concurrent map read and map write")
}
// 计算哈希值
hash := t.hasher(key, uintptr(h.hash0))
// 计算在哪个桶
m := bucketMask(h.B)
b := (*bmap)(add(h.buckets, (hash&m)*uintptr(t.bucketsize)))
if c := h.oldbuckets; c != nil {
if !h.sameSizeGrow() {
// There used to be half as many buckets; mask down one more power of two.
m >>= 1
}
oldb := (*bmap)(add(c, (hash&m)*uintptr(t.bucketsize)))
if !evacuated(oldb) {
b = oldb
}
}
top := tophash(hash)
bucketloop:
for ; b != nil; b = b.overflow(t) {
for i := uintptr(0); i < bucketCnt; i++ {
if b.tophash[i] != top {
if b.tophash[i] == emptyRest {
break bucketloop
}
continue
}
k := add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize))
if t.indirectkey() {
k = *((*unsafe.Pointer)(k))
}
if t.key.equal(key, k) {
e := add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+i*uintptr(t.elemsize))
if t.indirectelem() {
e = *((*unsafe.Pointer)(e))
}
return e
}
}
}
return unsafe.Pointer(&zeroVal[0])
}map的读取数据
- 第一步：结合哈希引子和键生成哈希值
- 第二步：获取哈希值的后B位，以此决定存放在哪个桶中（也是与桶掩码做&运算）
- 第三步：确定桶之后，再根据key的哈希值计算出tophash（高8位），根据tophash和key去桶中查找数据。