哈希表的原理是将多个k-v键值对散列的存储在buckets中,buckets可以理解为一个连续的数组,所以给定一个key/value键值对,我们要将其存储到合适的位置需要经过两步骤:
- 计算hash值:
hash = hashFunc(key) - 计算索引位置:
index = hash % len(buckets)
哈希冲突#
解决哈希碰撞一般有两种方式;拉链法和开放寻址法
拉链法#

开放寻址法#

Map#

type hmap struct {
count int // 当前存储的键值对数量
flags uint8 // 标志位,用于记录 map 的状态(如是否正在扩容等)
B uint8 // 桶数组的大小是 2^B,决定了桶的数量
noverflow uint16 // 记录溢出桶的数量
hash0 uint32 // 哈希种子,防止哈希冲突攻击
buckets unsafe.Pointer // 指向主桶数组的指针
oldbuckets unsafe.Pointer // 扩容时,指向旧桶数组
nevacuate uintptr // 记录扩容的进度,表示已经迁移的桶的索引
extra *mapextra // 存储溢出桶和其他额外信息
}
type bmap struct {
topbits [8]uint8
keys [8]keytype
values [8]valuetype
overflow uintptr
}
// go 1.20 ~
type bmap struct {
// bucketCnt = 8
tophash [bucketCnt]uint8 // 存储每个键的哈希值的高 8 位
// 不再直接存储 keys 和 values
// 键和值存储在外部的独立区域
overflow *bmap
}
查找流程 hash = hash(“name”) bucketIndex = hash % bucketCount 先比较 tophash 如果匹配再比较 key
扩容
- 平均每个 bucket ≈ 6.5 个元素
- 如果溢出桶过多,也会扩容 负载因子已经超过 6.5: 双倍扩容 溢出桶的数量过多:等量扩容(一般认为溢出桶数量接近正常桶数量时)
