go语言常用的map是怎么实现的(原理)详解
<div id="navCategory"><h5 class="catalogue">目录</h5><ul class="first_class_ul"><li><a href="#_label0">前言</a></li><li><a href="#_label1">一、哈希冲突</a></li><li><a href="#_label2">二、map的结构</a></li><li><a href="#_label3">三、map的访问原理</a></li><li><a href="#_label4">四、map的赋值原理</a></li><li><a href="#_label5">五、map的删除</a></li><li><a href="#_label6">六、map的扩容</a></li><li><a href="#_label7">七、map的遍历</a></li></ul></div><p class="maodian"><a name="_label0"></a></p><h2>前言</h2><p>作为从java转来的go学长，我们当初常用的hashmap八股背的再熟悉不过了，那go的map是怎么实现的呢？</p>
<p>为此我前往不可视境界线，探索了B站世界，结合了几篇大佬们的博客文章以及源码，最后肝出本文，希望大家多多支持，邪王真眼是最强的！</p>
<p class="maodian"><a name="_label1"></a></p><h2>一、哈希冲突</h2>
<p>首先，提到map就不得不提到哈希，也就不得不提到哈希冲突了，个人理解<strong>map本质上就是一种优化后的哈希表，为了方便检索</strong>，go和java皆是如此，并且两者还有一个共同特点，二者解决哈希冲突的方式都是使用<strong>拉链法</strong>，而非<strong>开放寻址法</strong></p>
<p><strong>but，why？</strong></p>
<p>我认为，使用拉链法的好处</p>
<ol><li>容量更大，不管是java还是go，使用拉链法都允许一个下标上容纳更多的节点</li><li>拉链法允许动态地调整桶中元素的数量，例如通过在达到一定条件时转换为红黑树或扩容，添加溢出桶等</li><li>在实现上，拉链法相对于开放寻址法来说更为简单直接。它不需要复杂的探测过程，只需在链表中顺序查找即可</li></ol>
<p class="maodian"><a name="_label2"></a></p><h2>二、map的结构</h2>
<p>go语言中的map其实就是一个指向hmap的指针，占用8个字节。所以map底层结构就是<strong>hmap </strong>,hmap包含多个结构为<strong>bmap（桶）</strong>的bucket数组，当发生冲突的时候，会到正常桶里面的overflow指针所指向的<strong>溢出桶</strong>里面去找，Go语言中溢出桶也是一个动态数组形式，它是根据需要动态创建的。Go语言中处理冲突其实是采用了优化的拉链法，链表中每个节点存储的不是一个键值对，而是8个键值对</p>
<p style="text-align:center"><img alt="" src="https://img.jbzj.com/file_images/article/202601/2026010709004263.jpg" /></p>
<p>来看下map底层的代码</p>
<div class="jb51code"><pre class="brush:go;">// 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
nevacuateuintptr // progress counter for evacuation (buckets less than this have been evacuated)
extra *mapextra // optional fields
}</pre></div>
<p>我们不需要关注所有的字段，只需要记住这几个：</p>
<ul><li>count：map中元素的个数，就是len（map）的值</li><li>flags：记录map的一些状态</li><li>B：计算map的桶数，就是2^B，比如B=3，那么桶数就是8</li><li>buckets：指向桶数组bmap的指针</li><li>oldbuckets：扩容时指向旧的桶数组，非扩容时为nil</li><li>nevacuate：等于旧桶数组大小时迁移完成</li><li>extra：指向溢出桶相关</li></ul>
<p>下面再详细关注一下bmap：</p>
<div class="jb51code"><pre class="brush:go;">type bmap struct {
topbitsuint8 // 记录了哈希值的高八位，在桶内检索时需要
keys keytype
values valuetype
overflow uintptr // 存储溢出桶，当8个kv都用完之后会把新写入的写到溢出桶，初始化时创建的溢出桶就存这里
}</pre></div>
<p>再来关注一下这个tophash，我一开始没搞明白它是干嘛用的，怎么来的</p>
<p style="text-align:center"><img alt="" src="https://img.jbzj.com/file_images/article/202601/2026010709004218.png" /></p>
<p>这张图就很直观了，通过hash函数得到hash值，这个tophash就是蓝色的高8位，那红色的低8位是干嘛的呢，在定位是桶数组的哪个桶时，我们就通过低8位快速定位到了我们的数组下标</p>
<p class="maodian"><a name="_label3"></a></p><h2>三、map的访问原理</h2>
<p>这里我认为go中map的访问逻辑要比java麻烦一些</p>
<p>1.判断map是否为空或者无数据，若为空或者无数据返回对应的空值</p>
<p>2. map写检测，如果正处于写状态，表示此时不能进行操作，报fatal error</p>
<p>3.计算出hash值和掩码</p>
<p>4.判断当前map是否处于扩容状态，如果在扩容执行下面步骤:</p>
<p> 4.1根据状态位算判断当前桶是否被迁移</p>
<p> 4.2如果迁移，在新桶中查找</p>
<p> 4.3未被迁移，在旧桶中查找</p>
<p> 4.4根据掩码找到的位置</p>
<p>ps：你是不是读到这里好奇掩码是什么？以下来自百度</p>
<p style="text-align:center"><img alt="" src="https://img.jbzj.com/file_images/article/202601/2026010709004243.png" /></p>
<p>5.依次遍历桶以及溢出桶来查找key</p>
<p> 5.1遍历桶内的8个槽位</p>
<p> 5.2比较该槽位的tophash和当前key的tophash是否相等</p>
<p> 5.3相同，继续比较key是否相同，相同则直接返回对应value</p>
<p> 5.4不相同，查看这个槽位的状态位是否为"后继空状态"（顾名思义，它是桶里最后一个槽位了后面都是空的，另外后面还会出现一种状态就是本槽位是空）</p>
<p> 5.5是，key在以后的槽中也没有，这个key不存在，直接返回零值</p>
<p> 5.6否，遍历下一个槽位</p>
<p>6. 当前桶没有找到，则遍历溢出桶，用同样的方式查找</p>
<p class="maodian"><a name="_label4"></a></p><h2>四、map的赋值原理</h2>
<p>我们平常使用map赋值时，有两点需要注意：</p>
<p>1.map做赋值操作前一定要初始化，否则就panic</p>
<p>2.map不支持<strong>并发读写，</strong>注意不是并发读，前面读的过程我们也发现了它没有修改状态，不是写状态就不会有问题</p>
<p><strong>过程：</strong></p>
<p>1. map写检测，如果正处于写状态，表示此时不;能进行读取，报fatal error</p>
<p>2.计算出hash值，将map置为写状态</p>
<p>3.判断桶数组是否为空，若为空，初始化桶数组</p>
<p>4.目标桶查找</p>
<p> 1.根据hash值找到桶的位置</p>
<p> 2.判断该当前是否处于扩容:</p>
<p> 1.若正在扩容:迁移这个桶，并且还另外帮忙多迁移一个桶以及它的溢出桶</p>
<p> 3.获取目标桶的指针，计算出tophash,开始后面的key查找过程</p>
<p>5. key查找</p>
<p> 1.遍历桶和它的溢出桶的每个槽位，按下述方式查找</p>
<p> 2.判断槽位的tophash和目标tophash</p>
<p> 1.不相等</p>
<p> 1.槽位tophash为空，标记这个位置为侯选位置</p>
<p> 2.槽位tophash的标志位为'后继空状态"，说明这个key之前没有被插入过，插入 key/value</p>
<p> 3. tophash标志位不为空，说明存储着其他key,说明当前槽的tophash不符合，继续 遍历下一个槽</p>
<p> 2.相等</p>
<p> 1.判断当前槽位的key与目标key是否相等</p>
<p> 1.不相等，继续遍历下一-个槽位</p>
<p> 2.相等，找到了目标key的位置，原来已存在键值对，则修改key对应的value, 然后执行收尾程</p>
<p>6. key插入</p>
<p> 1.若map中既没有找到key,且根据这个key找到的桶及其这个桶的溢出桶中没有空的槽位了，要申请一个新的溢出桶，在新申请的桶里插入</p>
<p> 2.否则在找到的位置插入</p>
<p>7.收尾程序</p>
<p> 1.再次判断map的写状态</p>
<p> 2.清除map的写状态</p>
<p>这里需要注意一点:申请一-个新的溢出桶的时候并不会一开始就创建一个 溢出桶，因为map在初始化的时候会提前创建好一些溢出桶存储在<strong>extra* mapextra</strong>字段,样当出现溢出现象时候,这些下溢出桶会优先被使用，只有预分配的溢出桶使用完了，才会新建溢出桶。</p>
<p class="maodian"><a name="_label5"></a></p><h2>五、map的删除</h2>
<div class="jb51code"><pre class="brush:go;">for {
b.tophash = 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 != emptyOne {
break
}
}</pre></div>
<p>map删除的过程总体和访问赋值差不多，主要不同点是，如果在找到了目标key,则把当前桶该槽位对应的key和value删除,将该槽位的tophash置为emptyOne，如果发现当前槽位后面没有元素,则将tophash设置为emptyRest,并循环向前检查前一个元素，若前一个元素也为空,槽位状态为emptyOne,则将前一个元素的tophash也设置为emptyRest。这样做的目的是将emptyRest状态尽可能地向前面的槽推进，这样做是为了增加效率，因为在查找的时候发现了emptyRest状态就不用继续往后找了，因为后面没有元素了。</p>
<p class="maodian"><a name="_label6"></a></p><h2>六、map的扩容</h2>
<p>先不去讨论go是如何设计，如果你是go语言的设计师，在如此设计的数据结构和赋值删除等逻辑的前提下，你认为什么时候应该扩容呢？</p>
<p>无非就两种情况：</p>
<ol><li>元素数量太多，已经出现或者将要出现哈希冲突太频繁</li><li>元素的密度不够紧凑，被删除后剩余的空间太多需要重新整理空间</li></ol>
<p>是的，能想到这两点，你也可以当go语言的设计师了，并且根据这两种情况，应该采取不同的扩容方式，即双倍扩容，等量扩容</p>
<p>go语言触发扩容的条件：</p>
<ol><li>负载因子＞6.5</li><li>溢出桶数量过多</li></ol>
<p>你是不是又想问什么是负载因子？</p>
<div class="jb51code"><pre class="brush:go;">负载因子 = 哈希表中的元素数量 / 桶的数量</pre></div>
<p>扩容函数：</p>
<div class="jb51code"><pre class="brush:go;">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().
}</pre></div>
<p>其实只需要记住，和java不同，go采用渐进式扩容，不会一次性迁移所有的桶，而是一次迁移一点，每次写入时都迁移两个桶</p>
<p>等量扩容的桶数组下标是对应的</p>
<p style="text-align:center"><img alt="" src="https://img.jbzj.com/file_images/article/202601/2026010709004249.png" /></p>
<p>但是双倍扩容桶可能在原位置，也可能在原位置+偏移量（偏移量就是原桶数组长度）</p>
<p style="text-align:center"><img alt="" src="https://img.jbzj.com/file_images/article/202601/2026010709004247.png" /></p>
<p class="maodian"><a name="_label7"></a></p><h2>七、map的遍历</h2>
<p>go中map的遍历是随机的，这是go设计者的初衷就是不想开发者写出依赖直接遍历的脆弱代码，想想go经常扩容什么的，位置并不固定，想要顺序遍历，常用的方式是写到slice中再排序</p>
頁:
[1]