golang中的map
2019-06-28 本文已影响0人
XITEHIP
在golang中map是经常用到的数据结构。在这篇中我会从基础、算法、源码角度去分析map中的设计思想。
1 基础部分
1.1 声明
var m map[string]string
此时 m == nil
1.2 创建
-
make
m := make(map[string]int)
-
字面量
ages := map[string]int{
"xitehip":18
"zuan":2
}
//或者
ages := make(map[string]int)
ages["xitehip"] = 18
1.3 key 类型范围
- key是引用类型
- key不可以是：slice、map 、 func 。因为这3个类型是不可比较类型。
1.4 增删改查
// 新增
m["name"] = "xitehip"
// 删除，key不存在则什么也不干，不会报错。
delete(m, "xitehip")
// 更新
m["name"] = "zuan"
// 查询，key不存在返回value类型的零值
i := m["name"]
i, ok := m["name"]
_, ok := m["name"]
1.5 类型、长度、比较
- 引用类型
- 长度用len(map)获取
- 和slice，func一样不可以用==来比较
1.6 遍历
- for range遍历。
- 无序。
1.7 函数传参
- 引用类型传参，传递的是地址的拷贝，扩容时也不会改变这个地址。
2 算法
- 哈希算法：将任意长度的二进制值串映射为固定长度的二进制值串。
- 哈希表：其实就是对数组支持下标随机访问的运用，结合哈希算法就能够得到一张哈希表。
- map中用的是hash table来查找数据的，再根据链表去解决hash冲突问题。
- 冲突解决：有开放寻址法和链表法，由于golang是用的链表法，所以下面解释一下。
- 链表法：每个桶中从存放的具体的值变成了指针，其指向了一个链表，主要目的是解决不同key哈希出来的值相同的问题，这样就可以通过hash值找到桶的位置，然后根据key的值遍历得到具体的值。
- 时间复杂度：由于哈希表具体存在链表上，所以插入的时间复杂度为o(1),删除更新需要遍历链表，所以是o(n)。
- golang中使用的hash算法根据硬件选择，如果cpu支持aes，那么使用aes hash，否则使用memhash。用位运算避免mod的时对cpu多次的计算。
3 底层源码
3.1 map查找过程
见下图1
图1
按照图片箭头上标注的数字顺序解释：
- 将key9=xitehip传递给hash函数。
- hash函数hash之后生成一个无符号的64位整数，然后转换成64位二进制数。
- 取后5位（00011）转换成整数3然后去hmap中的buckets的指针找到[]bmap，然后根据下标3定位到具体的bmap地址（len([]bmap=32)）。
- 然后根据[3]bmp中的地址找到具体bmap数据。
- 根据刚才的hash之后得到的64位二进制数的前8位（1100100）转换得到的整数200，然后根据200去遍历里面8个tophash，看是否有等于200的，发现没有。
- 根据bmap1中的overflow指针找到下一个也就是bmap2，然后同操作5进行遍历，发现tophash中有200表明匹配成功，因为200是1号位所以去key的1号位查找是否等于xitehip，确认是相等，然后就可以确定val的值在val的1号位就是我们找的val(其中等于18）。
3.2 map的插入更新删除（不包括扩容情况）
- 删除和更新都要县查找到对应的key
- 更新如果没有找到就在空位置插入数据也即是插入，如果找到了就更新对应的val
- 删除如果没有找到则什么也不做，如果找到了则将对应的key和val清空，但是不释放内存。
3.3 扩容
参见下边参考文章
