德州企业网站建设要素,wordpress redis,承德信息网络有限公司,微信订阅号做微网站参考#xff1a;
解剖Go语言map底层实现Go语言核心手册-3.字典
一、Go Map底层结构#xff1a;
Go map的底层实现是一个哈希表#xff08;数组 链表#xff09;#xff0c;使用拉链法消除哈希冲突#xff0c;因此实现map的过程实际上就是实现哈希表的过程。
先来看下…参考
解剖Go语言map底层实现Go语言核心手册-3.字典
一、Go Map底层结构
Go map的底层实现是一个哈希表数组 链表使用拉链法消除哈希冲突因此实现map的过程实际上就是实现哈希表的过程。
先来看下go map底层的具体结构
type hmap struct {count int // 元素个数调用len(map)返回这个值B uint8 // bucket数量是2^B, 最多可以放 loadFactor * 2^B 个元素再多就要扩容了hash0 uint32 // hash seedbuckets unsafe.Pointer // 指向bucket数组的指针存储key val大小2^B oldbuckets unsafe.Pointer // 扩容时buckets 长度是 oldbuckets 的两倍// ...
}
type bmap struct {topbits [8]uint8 // 高位哈希值数组keys [8]keytype // 存储key的数组values [8]valuetype // 存储val的数组overflow uintptr // 指向当前bucket的溢出桶// 为缓解当存在多个key计算后的哈希值低8位相同的个数大于一个bucket所能存放的数目8个时且这个map还没达到扩容条件时做的一种存储设计。
}在这个哈希表中主要涉及到的结构体有两个一个是 hmap(a header for a go map)一个是 bmapa bucket for a go map
对于 hmap我们只需要关注其中的 buckets它是一个指向 bmap结构体类型数组的指针。 而对于其中的 bmap 高位哈希值 topbits数组记录的是当前bucket中key相关的 “索引”指向扩容bucket的指针 overflow每个 bmap类型的 bucket 最多只能放 8个k-v键值对。如果碰巧有key的哈希值一样的新数据存入当前bucket那就需要再构建一个新的溢出桶 bucket并通过overflow指针连接起来使得bucket形成一个链表结构。存储key/value的数组 keys、values
二、key-value是如何存放的
当前bucket桶中的 key-value 的值的存放是有其特点的bucket桶中所有的key存放到 keys数组中而所有的value存放到 values数组中。 这么做的原因也很简单可以在key和value的长度不同时消除padding内存对齐带来的空间浪费。具体如图所示
三、根据key 查找/新增 数据
对传来的key进行哈希运算得到唯一哈希值并将该哈希值分为高位和低位如图所示 蓝色为高位红色为低位。 低位用于寻找当前key属于哪个bucket而高位用于寻找对应bucket中的具体key。
而之前 bmap中的高位哈希值数组字段 topbits存的就是当前bucket桶中不同key-value键值对中对应key的高位哈希值这样便于根据key查找数据。
新增的过程与查找过程类似也是填充桶的过程。
四、删除map中的数据
针对map中的key-value数据
如果是指针类型数据则将其原有引用去除利用go GC来清理内存如果是值类型数据则直接清理对应内存空间
最后将该key-value记录对应的 【bmap中高位哈希值数组 topbits】中的key相关 “索引” 置空。
五、map的扩容
当go map中每个bucket桶存储的平均元素个数大于加载因子 loadFactor 6.5判断扩容的条件时map底层就会创建一个容量大小是原来2倍的新buckets数组并将 oldbuckets指针指向原来的旧buckets数组。然后对旧buckets数组中的元素key重新哈希rehash得到新的哈希值根据新的哈希值的高位和低位来放入扩容后的新buckets数组中。 加载因子越小↓说明空间利用率低因此 “产生冲突的机会” 低 加载因子越大↑说明空间利用率高但是 “产生冲突的机会” 也高了。 不过需要注意的是
并不是立刻把 oldbuckets指针所指向的旧bucket数组中的元素一次性转移到新的bucket数组当中而是当只有访问到具体某个key所在的bucket时才会将该bucket中的旧数据逐步迁移到新bucket中。一直到旧数据完全迁移完才会删除 oldbuckets的指向使得旧buckets空间得到释放。如下图所示 这里迁移完并不会直接删除旧bucket中的数据而是把原来旧数据的引用去掉利用GC逐步清除内存。
六、map的等量扩容缩容
map中数据较少但 overflow 指向的溢出桶bucket数量过多时会导致溢出桶中的记录存储很稀疏排列不紧凑大量空间被浪费。这时就需要进行等量扩容/缩容一般出现在之前数据被大量删除的场景下。
其实就是重新整理一下数据使溢出桶中的数据重新紧凑的放在普通bucket桶中避免不必要的空间浪费。
