满屏网站做多大尺寸,wordpress 改语言,免费seo关键词优化排名,大学网站建设管理办法信息化目录 一、前言二、结构1. hmap(map) 结构2. bmap(buckets) 结构 三、哈希冲突四、负载因子五、哈希函数六、扩容增量扩容等量扩容 一、前言
在现代编程语言中#xff0c;map 是一种非常重要的数据结构#xff0c;广泛用于存储和快速查找键值对。Go 语言中的 map 是一种高效且… 目录 一、前言二、结构1. hmap(map) 结构2. bmap(buckets) 结构 三、哈希冲突四、负载因子五、哈希函数六、扩容增量扩容等量扩容 一、前言
在现代编程语言中map 是一种非常重要的数据结构广泛用于存储和快速查找键值对。Go 语言中的 map 是一种高效且灵活的数据结构它不仅提供了基本的键值存储功能还在并发场景下具备了出色的性能表现
现在探讨 Go 语言中 map 的实现原理分析它的扩容策略、哈希计算方式等细节
二、结构
我对 map 的理解就是 一个指针指向一个数组 这个数组呢存储的是结构体 这个结构体里面呢有几个元素 也就是一个指向哈希桶数组的指针 一个哈希桶可以存储多个键值对
这张图现在可能不理解因为还没有了解 map 的结构没关系看了后面再有这张图会好理解很多
1. hmap(map) 结构
go 中的 map 就是 hmap 结构体源码在 runtime/map.go:hmap 中
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 compilers definition.count int // # live cells size of map. Must be first (used by len() builtin)flags uint8B uint8 // log_2 of # of buckets (can hold up to loadFactor * 2^B items)noverflow uint16 // approximate number of overflow buckets; see incrnoverflow for detailshash0 uint32 // hash seedbuckets unsafe.Pointer // array of 2^B Buckets. may be nil if count0.oldbuckets unsafe.Pointer // previous bucket array of half the size, non-nil only when growingnevacuate uintptr // progress counter for evacuation (buckets less than this have been evacuated)clearSeq uint64extra *mapextra // optional fields
}一些字段的解释有几个字段 只看干巴巴的文字解释没有具体用法不太好理解到这里理解count、B、buckets 就可以不理解的没必要死磕可以先跳过去用到的时候再来看不影响阅读 count表示 hamp 中的元素数量就是 len(map) flagshmap 的标志位用于表示 hmap 处于什么状态有以下几种可能。
const (iterator 1 // 迭代器正在使用桶oldIterator 2 // 迭代器正在使用旧桶hashWriting 4 // 一个协程正在写入hmapsameSizeGrow 8 // 正在等量扩容
)B map中的哈希桶的数量为1 B 2^B 2的B次方 这里 2^B 和 count 有一定关系但不相等可以理解为count代表的是所有桶中存储的所有键值对的个数而2^B仅仅代表哈希桶的数量而且一个哈希桶里面不只有一个键值对 noverflow map 中溢出桶的大致数量 hash0 哈希种子在 hmap 被创建时指定用于计算哈希值key buckets 指向哈希桶数组的指针 oldbuckets 存放 hmap 在扩容前哈希桶数组的指针 extra 存放着 hmap 中的溢出桶溢出桶指的是就是当前桶已经满了创建新的桶来存放元素新创建的桶就是溢出桶
2. bmap(buckets) 结构
hmap 中的 buckets 也就是桶切片指针go 中的 buckets 就是 bmap 结构体定义为
type bmap struct {tophash [abi.OldMapBucketCount]uint8
}bmap 中只有一个 tophash 字段其实还有很多注释这里都删掉了 tophash 存储的是每个键的哈希值的高 8 位。 当查找某个键时通过只比较高 8 位来过滤掉一些键避免了每次查找时都进行完整的哈希值比较由此它可以快速比较键值对以便在哈希表中进行查找。
实际上由于 map 可以存储各种类型的键值对不同的类型占用不同的内存空间所以需要在编译时根据类型来推导占用的内存空间并且 map 的 key 必须是可比较的所以也会判断 key 是否满足要求由此可以推断 bmap 中不止有这一个字段
所以实际上bmap的结构如下不过这些字段对我们是不可见的go 在实际操作中是通过移动 unsafe 指针来进行访问
type bmap struct {tophash [BUCKETSIZE]uint8keys [BUCKETSIZE]keyTypeelems [BUCKETSIZE]elemTypeoverflow *bucket
}其中的一些解释如下 tophash存放每一个键的高八位值对于一个 tophash 的元素而言有下面几种特殊的值
const (emptyRest 0 // 当前元素是空的并且该元素后面也没有可用的键值了emptyOne 1 // 当前元素是空的但是该元素后面有可用的键值。evacuatedX 2 // 扩容时出现只能出现在oldbuckets中表示当前元素被搬迁到了新哈希桶数组的上半区evacuatedY 3 // 扩容时出现只能出现在oldbuckets中表示当前元素被搬迁到了新哈希桶数组的下半区evacuatedEmpty 4 // 扩容时出现元素本身就是空的在搬迁时被标记minTopHash 5 // 对于一个正常的键值来说tophash的最小值
)只要是tophash[i]的值大于minTophash的值就说明对应下标存在正常的键值。
keys存储 key
elems存储 value
overflow指向溢出桶的指针 三、哈希冲突
哈希冲突 并不陌生在数据结构哈希表里面就有了哈希冲突这个定义 说白了就是有不止一个键 (k1, k2, …)计算出它们的哈希值相同这些键就是发生了冲突 我们使用拉链法处理冲突和数据结构中哈希桶处理方法一样。就是你有一个桶这个桶里原本已经有元素了但是又有其他的键映射到这个桶里面那就把这个新的元素和旧元素链起来我认为理解成把元素一个一个挂在哈希桶下面比较好理解 当然了这种处理方法是有缺陷的 数据量少的时候假设有 4 个哈希桶有 12 个元素那么平均就是一个桶里存储 3 个元素查找一个键计算出这个键对应的哈希值就知道了这个元素在哪个桶再遍历这个桶最坏就是要查找的键挂在桶的最下面那遍历三次就可以找到了。所以一个桶里面存储的数据少的时候时间复杂度就是常量级别的 但是当数据量很大很大的时候有 100亿 这时候如果有 4 个桶 一个桶里面平均存储 25亿 个元素再去查找元素再去遍历桶那就很慢很慢了 所以哈希桶下面可以挂元素但是这不是无限的规定不超过八个 如果超过八个了怎么办 那就会创建一个新的桶来存放这些键这个桶就叫 溢出桶。其实就是原来的桶放不下了元素溢出到这个桶来了创建完毕后原来的哈希桶会有一个指针指向这个溢出桶那原来的桶和溢出桶连起来就形成了一个 bmap 链表
超过八个创建溢出桶的情况
实际上溢出的桶是
如果哈希冲突很多很多溢出桶也会越来越多那么在读写哈希表时就需要遍历更多的溢出桶链表才能找到指定的位置所以性能就越差。为了改善这种情况应该增加buckets桶的数量也就是 扩容 那什么时候进行扩容呢总需要一个标准吧 所以引出了 负载因子 loadfactor
四、负载因子
负载因子 元素个数 ÷ 桶的个数意思就是 实际的元素个数 / 哈希桶总个数
loadfactor : len(elems) / len(buckets)负载因子越大说明实际有的元素个数越多也就是哈希冲突越大 负载因子越小说明实际有的元素比较少也就是说有更多的桶没有用到所以 hmap 的内存利用率低占用的内存就越大 扩容的条件
负载因子超过阈值 bucketCnt*13/16也就是6.5 bucketCnt 是每个哈希桶最多存储的键值对个数也就是 8 溢出桶数量过多
overLoadFactor 函数是 Go 语言中用于计算和检查 map 的负载因子的函数判断负载因子是否超过阈值
func overLoadFactor(count int, B uint8) bool {return count bucketCnt uintptr(count) loadFactorNum*(bucketShift(B)/loadFactorDen)
}这段代码返回一个 bool 值负载因子超过阈值返回 true否则返回false
根据这段代码也可以看出来在满足这两个条件下负载因子超过阈值 一是元素个数count大于桶内最多元素个数bucketCnt也就是语句 count bucketCnt
二是负载因子大于阈值也就是语句uintptr(count) loadFactorNum*(bucketShift(B)/loadFactorDen) 解释其中 loadFactorNum 和 loadFactorDen 都是一个常数bucketshift 是计算1 B并且已知loadFactorNum (bucketCnt * 13 / 16) * loadFactorDen 将 loadFactorNum 代入这个式子最后化简得到uintptr(count) / 1 B (bucketCnt * 13 / 16)
其中(bucketCnt * 13 / 16)值为 6.51 B就是哈希桶的数量count 是元素个数 五、哈希函数
f32hash 函数是 Go 语言中用于计算 float32 类型数据的哈希值的函数位于 runtime/alg.go 文件中作用是根据 float32 数据的内存内容计算一个哈希值。在计算哈希时它会根据浮点数的值处理 0、-0 和 NaN 等特殊情况。最终会返回一个基于内存的哈希值。
func f32hash(p unsafe.Pointer, h uintptr) uintptr {f : *(*float32)(p)switch {case f 0:return c1 * (c0 ^ h) // 0, -0case f ! f:return c1 * (c0 ^ h ^ uintptr(fastrand())) // any kind of NaNdefault:return memhash(p, h, 4)}
}各个部分解释 1.
p unsafe.Pointer 和 h uintptrp 是一个指向内存的指针它指向 float32 类型的数据 h 是一个哈希种子通常用于哈希计算的初始值可能来自于现有的计算或随机值 f : *(*float32)(p):这行代码将 unsafe.Pointer 转换为 float32 类型 switch 语句的三个分支 前面提到了它会根据浮点数的值处理 0、-0 和 NaN 等特殊情况最终会返回一个基于内存的哈希值。switch 语句就是做这个工作的
处理 0 和 -0
case f 0:return c1 * (c0 ^ h) // 0, -0f 0 会处理 float32 类型的 0 和 -0它们在内存中是相同的。为了确保它们产生不同的哈希值避免冲突这个条件会根据 h 和常数 c0、c1 计算哈希
处理 NaN
case f ! f:return c1 * (c0 ^ h ^ uintptr(fastrand())) // any kind of NaNf ! f 是一个典型的用来检测 NaNNot a Number非数字的技巧因为 NaN 是唯一一个不等于自身的浮点数。这个分支处理 NaN 值的情况并通过引入 fastrand()一个生成随机数的函数来增强哈希的随机性。
默认情况普通情况
default:return memhash(p, h, 4) // 普通情况计算基于内存的哈希值如果 f 既不是 0 也不是 NaN那么就会调用 memhash 函数来计算该 float32 值的哈希。memhash 通过读取 f 在内存中的实际内容来计算哈希值。
memhash 函数 memhash 函数通常用于基于内存内容来计算哈希值。它的计算是基于内存块的字节内容因此不同内存位置的相同数据可能会产生不同的哈希值。4 表示这里的内存块是 4 字节即 float32 类型的大小。
为什么要处理 0
在浮点数中0 和 -0 是不同的值但是它们在比较时是相等的。为了区分它们Go 可能会采用不同的哈希策略 这里使用 c1 * (c0 ^ h) 的方式对它们进行哈希计算防止它们在哈希表中发生冲突
为什么 map 哈希计算基于内存 Go 中的 map 哈希计算并不仅仅依赖于数据的类型还基于数据的内存布局。这是为了保证哈希计算的高效性和减少哈希冲突。通过直接操作内存地址和数据内容可以更加高效地计算哈希值减少对类型的依赖。尤其是在 map 中键的哈希值越唯一查找和插入操作的性能越高
为什么内存中的哈希值不能持久化 内存不一致 哈希值是根据数据在内存中的表示来计算的。由于 Go 的内存布局可能在不同的运行中不同例如由于编译器优化或操作系统调度等原因内存地址的分布在不同的运行时是不一致的。因此基于内存的哈希值不适合持久化因为它在每次程序执行时都会有所变化。 运行时依赖 map 中的哈希值依赖于数据在内存中的位置或布局这些信息只有在程序运行时才可用无法在磁盘上持久保存。因此每次程序运行时哈希值的计算都会重新基于内存进行而不能依赖于之前保存的哈希值。 在该文件中还有一个名为 typehash 的函数它是一个通用的哈希计算方法依据类型信息和数据本身来计算哈希值
func typehash(t *_type, p unsafe.Pointer, h uintptr) uintptr解释
t *_type : 这是类型信息指向存储类型信息的结构体 _type。_type 是 Go 内部用于表示类型的结构体包含了类型的详细信息如类型大小、种类、结构体字段等。
p unsafe.Pointer : 这是指向实际数据的指针。数据的类型会根据 t 来确定。
h uintptr : 这是哈希计算的种子用于初始化哈希计算。
typehash 函数通过对类型信息 ( t ) 和数据本身 ( p ) 进行处理返回一个最终的哈希值。由于不同类型的数据可能需要不同的哈希计算策略typehash 会根据类型的不同来调整计算方法
通用性和速度 typehash 相比于其他类型特定的哈希函数如 f32hash要慢一些因为它要处理不同类型的情况。比如它需要根据类型的结构、字段以及其他特征来计算哈希值因此它的计算会更复杂一些但却非常通用能处理各种类型的数据
reflect_typehash 函数 在 Go 中reflect_typehash 是一个使用 typehash 的辅助函数主要用于通过反射机制来获取对象的哈希值。
//go:linkname reflect_typehash reflect.typehash
func reflect_typehash(t *_type, p unsafe.Pointer, h uintptr) uintptr {return typehash(t, p, h)
}typehash 的实现会根据传入的数据类型来采取不同的计算策略。例如 基础类型如整数、浮点数直接对数据本身进行哈希计算。 结构体类型对结构体中的各个字段进行哈希计算并合并所有字段的哈希值。 数组、切片对数组或切片中的元素进行哈希计算。 接口类型由于接口在 Go 中由类型和数据两个部分组成typehash 需要同时考虑这两个部分来计算哈希值。
为什么 typehash 不用于 map 计算 map 在 Go 中是一个特殊的类型它具有高效的哈希计算过程。map 使用基于内存地址的哈希计算方法如 memhash来确保高效的哈希操作特别是在内存分布和性能优化方面。相比之下typehash 的计算方式更加通用但也更慢。对于 map 来说它并不需要处理如此复杂的类型因此采用了更加高效、类型特定的哈希方法 六、扩容
前面已经提到了扩容有两个条件
负载因子超过 6.5溢出桶的数量过多
判断负载因子是否超过阈值的函数是overLoadFactor前面负载因子部分已经提到过 判断溢出桶的数量是否过多的函数是runtime.tooManyOverflowBuckets代码如下
func tooManyOverflowBuckets(noverflow uint16, B uint8) bool {if B 15 {B 15}return noverflow uint16(1)(B15)
}解释
noverflow uint16 无符号 16 位整数表示当前哈希表中溢出桶的数量
B uint8无符号 8 位整数表示哈希表中哈希桶的数量的大小 1 B
返回值返回一个布尔值bool如果当前的溢出桶数量 noverflow 超过了预期的阈值返回 true否则返回 false
return noverflow uint16(1)(B15)判断当前的溢出桶数量是否超出阈值
uint16(1) (B 15)B 15通过 B 15将 B 限制在一个 4 位二进制数范围内即 0 到 15。这等同于取 B 的低 4 位。如果 B 的值大于 15这个操作会确保计算结果不会超出 2^15
判断是否需要扩容的代码如下
if !h.growing() (overLoadFactor(h.count1, h.B) || tooManyOverflowBuckets(h.noverflow, h.B)) {hashGrow(t, h)goto again // Growing the table invalidates everything, so try again
}!h.growing()检查哈希表是否没有处于扩容状态。如果 growing() 返回 false说明当前哈希表没有扩容 可以看到的就是这三个条件限制
当前不能正在扩容负载因子小于 6.5溢出桶数量不能过多
负责扩容的函数是runtime.hashGrow
func hashGrow(t *maptype, h *hmap)根据触发扩容的条件不同扩容的类型也不同分为两种
增量扩容等量扩容 增量扩容
当负载因子很大时哈希冲突比较严重就会形成很多溢出桶 这时候再去查找一个元素就要遍历更多的溢出桶链表导致 map 读写性能下降
为什么溢出桶过多会导致 map 读写性能下降呢 遍历的时间复杂度是O(n)哈希表查找的时间复杂度主要取决于哈希值的计算时间和遍历的时间若遍历的时间远小于计算哈希的时间查找的时间复杂度近似为O(1) 。但如果哈希冲突比较严重过多 key 都被分到同一个哈希桶溢出桶链表过长导致遍历时间增大就会导致查找的时间增大而增删改查都需要先进性查找操作因而导致性能下降
这种情况使用 增量扩容新增更多的哈希桶避免形成过长的溢出桶链表
增量扩容意味着 map 在扩容时并不是立即将所有元素迁移到新的桶中而是逐步进行迁移随着操作的进行逐渐完成迁移。这样做的好处是可以减少扩容过程中对性能的影响避免一次性扩容带来的性能瓶颈
增量扩容的核心机制 老桶数组oldbucketshmap 中的 oldBuckets 指向原来的哈希桶数组表示这是旧数据 创建新桶创建更大容量的哈希桶数组让 hmap 中的 buckets 指向新的哈希桶数组 元素迁移迁移的过程是增量的即在每次对 map 进行操作插入、删除等时都会将一些原本应该迁移的元素从 oldbuckets 迁移到新桶数组中。直到所有元素都完成迁移扩容过程才算完成。扩容完成后旧桶的内存被释放 增量迁移的实现这种增量迁移的方式通过一个标志 oldbuckets 来标识 map 是否正在进行扩容。如果 oldbuckets 不为 nil则说明扩容正在进行中。如果为 nil则说明扩容已经完成
等量扩容
前面提到过等量扩容的触发条件是溢出桶数量过多
假如 map 先是添加了大量的元素导致溢出桶增多然后又大量删除元素这样可能会导致数据分布不均匀也就是有的桶有很多元素有的桶元素很少甚至是空的那也有可能导致很多的溢出桶都是空的但是又占用了不少内存
这种情况使用 等量扩容创建一个同等容量的新 map重新分配一次哈希桶
所以所谓等量扩容实际上并不是扩大容量buckets 数量不变只是将所有元素二次分配使得数据分布更均匀
