文章目录
目录
- 前言
- 一、哈希冲突
- 二、map的结构
- 三、map的访问原理
- 四、map的赋值原理
- 五、map的删除
- 六、map的扩容
- 七、map的遍历
作为从java转来的go学长，我们当初常用的hashmap八股背的再熟悉不过了，那go的map是怎么实现的呢？
为此我前往不可视境界线，探索了B站世界，结合了几篇大佬们的博客文章以及源码，最后肝出本文，希望大家多多支持，邪王真眼是最强的！
首先，提到map就不得不提到哈希，也就不得不提到哈希冲突了，个人理解map本质上就是一种优化后的哈希表，为了方便检索，go和java皆是如此，并且两者还有一个共同特点，二者解决哈希冲突的方式都是使用拉链法，而非开放寻址法
but，why？
我认为，使用拉链法的好处
- 容量更大，不管是java还是go，使用拉链法都允许一个下标上容纳更多的节点
- 拉链法允许动态地调整桶中元素的数量，例如通过在达到一定条件时转换为红黑树或扩容，添加溢出桶等
- 在实现上，拉链法相对于开放寻址法来说更为简单直接。它不需要复杂的探测过程，只需在链表中顺序查找即可
go语言中的map其实就是一个指向hmap的指针，占用8个字节。所以map底层结构就是hmap ,hmap包含多个结构为bmap（桶）的bucket数组，当发生冲突的时候，会到正常桶里面的overflow指针所指向的溢出桶里面去找，Go语言中溢出桶也是一个动态数组形式，它是根据需要动态创建的。Go语言中处理冲突其实是采用了优化的拉链法，链表中每个节点存储的不是一个键值对，而是8个键值对
来看下map底层的代码
// A header for a Go map.
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中元素的个数，就是len（map）的值
- flags：记录map的一些状态
- B：计算map的桶数，就是2^B，比如B=3，那么桶数就是8
- buckets：指向桶数组bmap的指针
- oldbuckets：扩容时指向旧的桶数组，非扩容时为nil
- nevacuate：等于旧桶数组大小时迁移完成
- extra：指向溢出桶相关
下面再详细关注一下bmap：
type bmap struct {
topbits [8]uint8 // 记录了哈希值的高八位，在桶内检索时需要
keys [8]keytype
values [8]valuetype
overflow uintptr // 存储溢出桶，当8个kv都用完之后会把新写入的写到溢出桶，初始化时创建的溢出桶就存这里
}
再来关注一下这个tophash，我一开始没搞明白它是干嘛用的，怎么来的
这张图就很直观了，通过hash函数得到hash值，这个tophash就是蓝色的高8位，那红色的低8位是干嘛的呢，在定位是桶数组的哪个桶时，我们就通过低8位快速定位到了我们的数组下标
这里我认为go中map的访问逻辑要比java麻烦一些
1.判断map是否为空或者无数据，若为空或者无数据返回对应的空值
2. map写检测，如果正处于写状态，表示此时不能进行操作，报fatal error
3.计算出hash值和掩码
4.判断当前map是否处于扩容状态，如果在扩容执行下面步骤:
4.1根据状态位算判断当前桶是否被迁移
4.2如果迁移，在新桶中查找
4.3未被迁移，在旧桶中查找
4.4根据掩码找到的位置
ps：你是不是读到这里好奇掩码是什么？以下来自百度
5.依次遍历桶以及溢出桶来查找key
5.1遍历桶内的8个槽位
5.2比较该槽位的tophash和当前key的tophash是否相等
5.3相同，继续比较key是否相同，相同则直接返回对应value
5.4不相同，查看这个槽位的状态位是否为"后继空状态"（顾名思义，它是桶里最后一个槽位了后面都是空的，另外后面还会出现一种状态就是本槽位是空）
5.5是，key在以后的槽中也没有，这个key不存在，直接返回零值
5.6否，遍历下一个槽位
6. 当前桶没有找到，则遍历溢出桶，用同样的方式查找
我们平常使用map赋值时，有两点需要注意：
1.map做赋值操作前一定要初始化，否则就panic
2.map不支持并发读写，注意不是并发读，前面读的过程我们也发现了它没有修改状态，不是写状态就不会有问题
过程：
1. map写检测，如果正处于写状态，表示此时不;能进行读取，报fatal error
2.计算出hash值，将map置为写状态
3.判断桶数组是否为空，若为空，初始化桶数组
4.目标桶查找
1.根据hash值找到桶的位置
2.判断该当前是否处于扩容:
1.若正在扩容:迁移这个桶，并且还另外帮忙多迁移一个桶以及它的溢出桶
3.获取目标桶的指针，计算出tophash,开始后面的key查找过程
5. key查找
1.遍历桶和它的溢出桶的每个槽位，按下述方式查找
2.判断槽位的tophash和目标tophash
1.不相等
1.槽位tophash为空，标记这个位置为侯选位置
2.槽位tophash的标志位为'后继空状态"，说明这个key之前没有被插入过，插入 key/value
3. tophash标志位不为空，说明存储着其他key,说明当前槽的tophash不符合，继续 遍历下一个槽
2.相等
1.判断当前槽位的key与目标key是否相等
1.不相等，继续遍历下一-个槽位
2.相等，找到了目标key的位置，原来已存在键值对，则修改key对应的value, 然后执行收尾程
6. key插入
1.若map中既没有找到key,且根据这个key找到的桶及其这个桶的溢出桶中没有空的槽位了，要申请一个新的溢出桶，在新申请的桶里插入
2.否则在找到的位置插入
7.收尾程序
1.再次判断map的写状态
2.清除map的写状态
这里需要注意一点:申请一-个新的溢出桶的时候并不会一开始就创建一个 溢出桶，因为map在初始化的时候会提前创建好一些溢出桶存储在extra* mapextra字段,样当出现溢出现象时候,这些下溢出桶会优先被使用，只有预分配的溢出桶使用完了，才会新建溢出桶。
for {
b.tophash[i] = emptyRest
if i == 0 {
if b == bOrig {
break // beginning of initial bucket, we're done.
}
// Find previous bucket, continue at its last entry.
c := b
for b = bOrig; b.overflow(t) != c; b = b.overflow(t) {
}
i = bucketCnt - 1
} else {
i--
}
if b.tophash[i] != emptyOne {
break
}
}
map删除的过程总体和访问赋值差不多，主要不同点是，如果在找到了目标key,则把当前桶该槽位对应的key和value删除,将该槽位的tophash置为emptyOne，如果发现当前槽位后面没有元素,则将tophash设置为emptyRest,并循环向前检查前一个元素，若前一个元素也为空,槽位状态为emptyOne,则将前一个元素的tophash也设置为emptyRest。这样做的目的是将emptyRest状态尽可能地向前面的槽推进，这样做是为了增加效率，因为在查找的时候发现了emptyRest状态就不用继续往后找了，因为后面没有元素了。
先不去讨论go是如何设计，如果你是go语言的设计师，在如此设计的数据结构和赋值删除等逻辑的前提下，你认为什么时候应该扩容呢？
无非就两种情况：
- 元素数量太多，已经出现或者将要出现哈希冲突太频繁
- 元素的密度不够紧凑，被删除后剩余的空间太多需要重新整理空间
是的，能想到这两点，你也可以当go语言的设计师了，并且根据这两种情况，应该采取不同的扩容方式，即双倍扩容，等量扩容
go语言触发扩容的条件：
- 负载因子＞6.5
- 溢出桶数量过多
你是不是又想问什么是负载因子？
负载因子 = 哈希表中的元素数量 / 桶的数量
扩容函数：
func hashGrow(t *maptype, h *hmap) {
// If we've hit the load factor, get bigger.
// Otherwise, there are too many overflow buckets,
// so keep the same number of buckets and "grow" laterally.
bigger := uint8(1)
if !overLoadFactor(h.count+1, h.B) {
bigger = 0
h.flags |= sameSizeGrow
}
oldbuckets := h.buckets
newbuckets, nextOverflow := makeBucketArray(t, h.B+bigger, nil)
flags := h.flags &^ (iterator | oldIterator)
if h.flags&iterator != 0 {
flags |= oldIterator
}
// commit the grow (atomic wrt gc)
h.B += bigger
h.flags = flags
h.oldbuckets = oldbuckets
h.buckets = newbuckets
h.nevacuate = 0
h.noverflow = 0
if h.extra != nil && h.extra.overflow != nil {
// Promote current overflow buckets to the old generation.
if h.extra.oldoverflow != nil {
throw("oldoverflow is not nil")
}
h.extra.oldoverflow = h.extra.overflow
h.extra.overflow = nil
}
if nextOverflow != nil {
if h.extra == nil {
h.extra = new(mapextra)
}
h.extra.nextOverflow = nextOverflow
}
// the actual copying of the hash table data is done incrementally
// by growWork() and evacuate().
}
其实只需要记住，和java不同，go采用渐进式扩容，不会一次性迁移所有的桶，而是一次迁移一点，每次写入时都迁移两个桶
等量扩容的桶数组下标是对应的
但是双倍扩容桶可能在原位置，也可能在原位置+偏移量（偏移量就是原桶数组长度）
go中map的遍历是随机的，这是go设计者的初衷就是不想开发者写出依赖直接遍历的脆弱代码，想想go经常扩容什么的，位置并不固定，想要顺序遍历，常用的方式是写到slice中再排序
到此这篇关于go语言常用的map是怎么实现的文章就介绍到这了,更多相关go语言map原理内容请搜索风君子博客以前的文章或继续浏览下面的相关文章希望大家以后多多支持风君子博客！
您可能感兴趣的文章:
- Golang 语言map底层实现原理解析
- Golang map实践及实现原理解析
- Golang Map简介以及底层原理
- Golang map实现原理深入分析
- Golang map实现原理浅析