map

简介

golang的map主要是基于hash-bucket实现

demoMap:=make(int,len)

type hmap struct {
	// Note: the format of the hmap is also encoded in cmd/compile/internal/reflectdata/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
	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
}

其中:
count: 当前map中元素的个数
B: 当前map中bucket的个数
buckets: mapa当前bucket指针
oldbuckets： 旧桶指针，存在于桶扩容期间

扩容

渐进式扩容

装载因子=元素数量/桶数量 即 len(buckets)=2^B

当装载因子大于等于6.5时，会触发扩容，扩容后的桶数量为原来的2倍

每个桶bmap可存储8个元素，桶会记录下一个桶和extra桶，

溢出桶用于降低扩容频率

• 装载因子大于6.5

• 使用太多溢出表

翻倍扩容：负载因子 >6.5
等量扩容：负载因子未超标但溢出桶太多。主要出现在大量删除后，桶中元素过少，但溢出桶过多

存储

将key进行哈希计算，

Hash(key)=hash ----> [0,m-1]

• 取模法: hash%m

• 与运算: hash&(m-1) m必须是2的幂，否则会出现一些桶始终无法选中