基本语法
定义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组成:
hashmap内部结构
// 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内部
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值
bucket的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 |
各个参数的意思：
- %overflow 溢出率，平均一个bucket有多少个kv的时候会溢出
- bytes/entry 平均存一个kv需要额外存储多少字节的数据
- hitprobe 找到一个存在的key平均需要找几下
- missprobe 找到一个不存在的key平均需要找几下
目前采用的是这一行:
| 6.50 | 20.90 | 10.79 | 4.25 | 6.50 |
迁移
迁移
