本文首发于个人博客,排版更清楚:
golang 语言提供了 built-in 的 map 类型,提供 hash table 的功能。完成的特性主要有:增删查改。
定义初始化及使用注意
==
map 类型是引用类型,所以直接声明的变量0值是 nil,它并不指向一个初试化的 map,使用时要注意。
read nil, got zero. write nil, panic!
此外,由于 map 的 key 不存在时,默认为0值,利用这个特性也能做一些判断。
遍历 map 的顺序是随机的,如果要俺固定顺序遍历元素,可以考虑放入 slice 中。
多线程安全
sync.RWMutex
底层实现
map = hashMap,本质是 array + list,效率极低:计算 hash 过程,查找过程
Hmap 两个 bucket 用于热扩容,不如 Java 8 的 Array + 红黑树高效,平均深度是 6.5
Hmap bucketsize 为 buckets 内 node 的数量,上限为 2 ^ B
每个bucket中存放最多8个key/value对, 如果多于8个,那么会申请一个新的bucket,并将它与之前的bucket链起来。
将hash值的低位当作Hmap结构体中buckets数组的index,找到key所在的bucket。
将hash的高8位存储在了bucket的tophash中,先比对高 8 bit,再比对 key 是否相等。
map[int64]int8