转载

Hashmap

基本语法

定义hashmap变量

由于go语言是一个强类型的语言，因此hashmap也是有类型的，具体体现在key和value都必须指定类型，比如声明一个key为string，value也是string的map，

需要这样做

var m map[string]string // 声明一个hashmap，还不能直接使用，必须使用make来初始化
m = make(map[string]string) // 初始化一个map
m = make(map[string]string, 3) // 初始化一个map并附带一个可选的初始bucket（非准确值，只是有提示意义）

m := map[string]string{} // 声明并初始化

m := make(map[string]string) // 使用make来初始化

大部分类型都能做key，某些类型是不能的，共同的特点是： 不能使用== 来比较，包括: slice, map, function

get,set,delete

m := map[string]int
m["a"] = 1

fmt.Println(m["a"]) // 输出 1

// 如果访问一个不存在的key，返回类型默认值
fmt.Println(m["b"]) // 输出0

// 测试key是否存在
v, ok := m["b"]
if ok {
    ...
}

// 删除一个key
delete(m, "a")

迭代器

// 只迭代key
for k := range m {
    ...
}

// 同时迭代key-value
for k, v := range m {
    ...
}

在迭代的过程中是可以对map进行删除和更新操作的，规则如下：

迭代是无序的，跟插入是的顺序无关
迭代的过程中删除一个key，无论遍历还是没有遍历过都不会再遍历到
迭代的过程中添加一个key，不确定是否能遍历到
未初始化的map也可以迭代

其他

map的value是不可取地址的，意味着 &m["a"]这样的语法是非法的
len可以获取当前map的kv个数

内部结构

hashmap结构

golang的map是hash结构的，意味着平均访问时间是O(1)的。同传统的hashmap一样，由一个个bucket组成:

// A header for a Go map.
type hmap struct {
 // Note: the format of the Hmap is encoded in ../../cmd/internal/gc/reflect.go and
 // ../reflect/type.go.  Don't change this structure without also changing that code!
 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)
 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)

 // If both key and value do not contain pointers and are inline, then we mark bucket
 // type as containing no pointers. This avoids scanning such maps.
 // However, bmap.overflow is a pointer. In order to keep overflow buckets
 // alive, we store pointers to all overflow buckets in hmap.overflow.
 // Overflow is used only if key and value do not contain pointers.
 // overflow[0] contains overflow buckets for hmap.buckets.
 // overflow[1] contains overflow buckets for hmap.oldbuckets.
 // The first indirection allows us to reduce static size of hmap.
 // The second indirection allows to store a pointer to the slice in hiter.
 overflow *[2]*[]*bmap
}

bucket内部

// A bucket for a Go map.
type bmap struct {
 tophash [bucketCnt]uint8
 // Followed by bucketCnt keys and then bucketCnt values.
 // NOTE: packing all the keys together and then all the values together makes the
 // code a bit more complicated than alternating key/value/key/value/... but it allows
 // us to eliminate padding which would be needed for, e.g., map[int64]int8.
 // Followed by an overflow pointer.
}

根据一个key得到value

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

*maptype为map的类型信息，是编译器在编译期静态生成的，里面包含了map的一些元信息，比如key和value的类型信息等等
*hmap为map的header，即map的引用
key是一个通用的指针，代表了key的引用
返回值为一个指针，指向对应的value引用

hash计算找到bucket

那我们怎么访问到对应的bucket呢，我们需要得到对应key的hash值

alg := t.key.alg
hash := alg.hash(key, uintptr(h.hash0))
m := uintptr(1)<<h.B - 1
b := (*bmap)(add(h.buckets, (hash&m)*uintptr(t.bucketsize)))

根据tophash和key定位到具体的bucket

tophash可以快速试错，如果tophash不相等直接跳过
tophash相等的话，根据key的比较来判断是否相等，如果相等则找到
如果当前bucket都试玩还没有找到，则调到下一个bucket

扩容

loadFactor	%overflow	bytes/entry	hitprobe	missprobe
4.00	2.13	20.77	3.00	4.00
4.50	4.05	17.30	3.25	4.50
5.00	6.85	14.77	3.50	5.00
5.50	10.55	12.94	3.75	5.50
6.00	15.27	11.67	4.00	6.00
6.50	20.90	10.79	4.25	6.50
7.00	27.14	10.15	4.50	7.00
7.50	34.03	9.73	4.75	7.50
8.00	41.10	9.40	5.00	8.00