哈希表

// src/runtime/map.go
type hmap struct {
    // 哈希表中的元素数量 
	count     int        
	// 状态标识，主要是 goroutine 写入和扩容机制的相关状态控制。并发读写的判断条件之一就是该值
	flags     uint8
	// 哈希表持有的 buckets 数量，但是因为哈希表中桶的数量都 2 的倍数，
	// 所以该字段会存储对数，也就是 len(buckets) == 2^B
	B         uint8
	// 溢出桶的数量
	noverflow uint16     
    // 哈希种子，它能为哈希函数的结果引入随机性，这个值在创建哈希表时确定，并在调用哈希函数时作为参数传入
	hash0     uint32
    // 指向 buckets 数组，长度为 2^B
	buckets   unsafe.Pointer  
    // 哈希在扩容时用于保存之前 buckets 的字段
	// 等量扩容的时候，buckets 长度和 oldbuckets 相等
	// 双倍扩容的时候，buckets 长度是 oldbuckets 的两倍
	oldbuckets unsafe.Pointer
	// 迁移进度，小于此地址的 buckets 是已迁移完成的
	nevacuate  uintptr         
	extra *mapextra
}

type mapextra struct {
    // hmap.buckets （当前）溢出桶的指针地址
	overflow    *[]*bmap
	// 为 hmap.oldbuckets （旧）溢出桶的指针地址
	oldoverflow *[]*bmap
    // 为空闲溢出桶的指针地址
	nextOverflow *bmap     
}

type bmap struct {
	tophash [bucketCnt]uint8
}

// 编译时，编译器会推导键值对占用内存空间的大小，然后修改 bmap 的结构
type bmap struct {
	topbits  [8]uint8
	keys     [8]keytype
	values   [8]valuetype
	pad      uintptr
	overflow uintptr
}

hash := map[string]int{
	"1": 2,
	"3": 4,
	"5": 6,
}
hash2 := make(map[string]int, 3)

func makemap(t *maptype, hint int, h *hmap) *hmap {
	// ...
	// initialize Hmap
	if h == nil {
		h = new(hmap)
	}
	// 获取一个随机的哈希种子
	h.hash0 = fastrand()
	
	// 根据传入的 hint 计算出需要的最小需要的桶的数量
	B := uint8(0)
	for overLoadFactor(hint, B) {
		B++
	}
	h.B = B

	// 初始化 hash table
	// 如果 B 等于 0，那么 buckets 就会在赋值的时候再分配
	// 如果 hint 长度比较大，分配内存会花费长一点
	if h.B != 0 {
		var nextOverflow *bmap
		// makeBucketArray 根据传入的 B 计算出的需要创建的桶数量
		// 并在内存中分配一片连续的空间用于存储数据
		h.buckets, nextOverflow = makeBucketArray(t, h.B, nil)
		if nextOverflow != nil {
			h.extra = new(mapextra)
			h.extra.nextOverflow = nextOverflow
		}
	}

	return h
}

v := hash[key]
v, ok := hash[key]

// src/runtime/map.go#L434 mapaccess1
for i := uintptr(0); i < bucketCnt; i++ {
	// 先比较 tophash，如果不相等，就直接进入下次循环
    if b.tophash[i] != top {
        if b.tophash[i] == emptyRest {
            break bucketloop
        }
        continue
    }
	// ...
	// 再比较桶内的 key 和传入的 key，如果相等，再获取目标值的指针
    if t.Key.Equal(key, k) {
		// ...
    }
}

delete(hashmap, key)

func mapdelete(t *maptype, h *hmap, key unsafe.Pointer)

// 对 key 清零
if t.indirectkey {
	*(*unsafe.Pointer)(k) = nil
} else {
	typedmemclr(t.key, k)
}

// 对 value 清零
if t.indirectvalue {
	*(*unsafe.Pointer)(v) = nil
} else {
	typedmemclr(t.elem, v)
}

func mapassign(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer {
// src/runtime/map.go mapassign
// If we hit the max load factor or we have too many overflow buckets,
// and we're not already in the middle of growing, start growing.
    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
    }
}

func hashGrow(t *maptype, h *hmap) {
	bigger := uint8(1)
	// 溢出桶过多触发的扩容是等量扩容，bigger 设置为 0
	if !overLoadFactor(h.count+1, h.B) {
		bigger = 0
		h.flags |= sameSizeGrow
	}
    // 将原有的 buckets 挂到 oldbuckets 上
	oldbuckets := h.buckets
	// 申请新的 buckets
	newbuckets, nextOverflow := makeBucketArray(t, h.B+bigger, nil)

	flags := h.flags &^ (iterator | oldIterator)
	if h.flags&iterator != 0 {
		flags |= oldIterator
	}
    // 如果是等量扩容，bigger 为 0，B 不变
	h.B += bigger
	h.flags = flags
	// 原有的 buckets 挂到 map 的 oldbuckets 上
	h.oldbuckets = oldbuckets
	// 新申请的 buckets 挂到 buckets 上
	h.buckets = newbuckets
	// 设置迁移进度为 0
	h.nevacuate = 0
	// 溢出桶数量为 0
	h.noverflow = 0
	// ...
}

func mapassign(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer {
    // ... 
again:
	bucket := hash & bucketMask(h.B)
    if h.growing() {
		// 真正的迁移在 growWork 中
        growWork(t, h, bucket)
	}	
	// ...
}

func mapdelete(t *maptype, h *hmap, key unsafe.Pointer) {
    // ... 
	bucket := hash & bucketMask(h.B)
	if h.growing() {
		// 真正的迁移在 growWork 中
		growWork(t, h, bucket)
	}
    // ... 
}

func (h *hmap) growing() bool {
	// oldbuckets 不为空，说明还没有迁移完成
	return h.oldbuckets != nil
}

func growWork(t *maptype, h *hmap, bucket uintptr) {
	// 迁移
	evacuate(t, h, bucket&h.oldbucketmask())

	// 还没有迁移完成，额外再迁移一个 bucket，加快迁移进度
	if h.growing() {
		evacuate(t, h, h.nevacuate)
	}
}

b := (*bmap)(add(h.oldbuckets, oldbucket*uintptr(t.bucketsize)))
newbit := h.noldbuckets()
// 判断旧桶是否已经被迁移了
if !evacuated(b) {
	// 旧桶没有被搬迁
	// do...  // 做转移操作
	// 遍历所有的 bucket，包括 overflow buckets
	// b 是老的 bucket 地址
	for ; b != nil; b = b.overflow(t) {
		// ...
	}
	// ...
}

package main

import "fmt"

func main() {
	m := make(map[string]int)

	fmt.Println(&m["foo"])
}

// 检测写标志
if h.flags&hashWriting == 0 {
	throw("concurrent map writes")
}

// 设置写标志
h.flags |= hashWriting