抽点时间阅读以下 golang 的 hmap，哈希表解决重头的方式一般有两种: 开放地址法和拉链法, 拉链法有个缺点就是不知道拉链链表的大小
下面先给出 hmap 的结构
type hmap struct {
count int // hmap 的大小(元素个数)
flags uint8
B uint8 //
noverflow uint16 // approximate number of overflow buckets; see incrnoverflow for details
hash0 uint32 // hash seed
buckets unsafe.Pointer // hmap 数组
oldbuckets unsafe.Pointer // 扩容时指向旧的 buckets 数组
nevacuate uintptr
extra *mapextra // optional fields
}
type mapextra struct {
// 如果一个 buckets 数组溢出了, 将溢出的数据做一个拉链, 放到 overflow 中
// 每一个 buckets 数组最多放 8 个数据, const 中有个常量
overflow *[]*bmap
oldoverflow *[]*bmap
// nextOverflow holds a pointer to a free overflow bucket.
nextOverflow *bmap
}
// A bucket for a Go map.
type bmap struct {
// tophash generally contains the top byte of the hash value
// for each key in this bucket. If tophash[0] < minTopHash,
// tophash[0] is a bucket evacuation state instead.
tophash [bucketCnt]uint8
// Followed by bucketCnt keys and then bucketCnt values.
// NOTE: packing all the keys together and then all the values together makes the
// code a bit more complicated than alternating key/value/key/value/... but it allows
// us to eliminate padding which would be needed for, e.g., map[int64]int8.
// Followed by an overflow pointer.
}
几个重要结构的含义:
hmap.B: 可以理解为 buckets 数组中有有 2^B 个 bucket
hmap.buckets: buckets 数组的指针, 每个 buckets 的大小是固定的, 一般为 8 个
mapextra.overflow: 假设 buckets 中的数据冲突非常严重, 超出了 8 个, buckets 指针就会指向 overflow 的 buckets 数组指针
bmap.tophash: 暂时没看明白, 占个坑位
查询数据
代码逻辑主要在 mapaccess1 中, 同时还会发现 有好几个 mapaccess 函数, 其实这几个函数的逻辑大致类似, 只是返回值略有不同, 可以对比一下.
记录一下主要逻辑和存在疑惑的一些点:
- 首先会通过一个通用的 hash 函数得到 hash 值, 然后使用
bucketMask这个函数得到一个 mask 值, 再通过这个 mask 值去确定这个 hash 值在 buckets 数组中的位置(偏移量), 进而得到目标 bucket, 上代码:
alg := t.key.alg // 这个应该是根据 map 中 key 的类型选择不同的 hash 函数
hash := alg.hash(key, uintptr(h.hash0))
m := bucketMask(h.B)
b := (*bmap)(add(h.buckets, (hash&m)*uintptr(t.bucketsize)))
// bucketShift returns 1<<b, optimized for code generation.
func bucketShift(b uint8) uintptr {
if sys.GoarchAmd64|sys.GoarchAmd64p32|sys.Goarch386 != 0 {
b &= sys.PtrSize*8 - 1 // help x86 archs remove shift overflow checks
}
return uintptr(1) << b
}
// bucketMask returns 1<<b - 1, optimized for code generation.
func bucketMask(b uint8) uintptr {
return bucketShift(b) - 1
}
使用 h.B 计算 mask, 应该是为了避免 hash 的值超出 buckets 数组的大小
这样计算之后, (hash&m)的最大值为 2^B - 1
- 计算 tophash 值
top := tophash(hash)
// tophash calculates the tophash value for hash.
func tophash(hash uintptr) uint8 {
top := uint8(hash >> (sys.PtrSize*8 - 8))
if top < minTopHash {
top += minTopHash
}
return top
}
这个应该是取 hash 值得最高 8 位, 使用 8 位 hash 值比较, 避免全量比较.
- 遍历 bucket
bucketloop:
// 如果有溢出
for ; b != nil; b = b.overflow(t) {
// 遍历一个 bucket
for i := uintptr(0); i < bucketCnt; i++ {
// 判断一下 tophash 是否相等
if b.tophash[i] != top {
// bucket 没有值
if b.tophash[i] == emptyRest {
break bucketloop
}
continue
}
k := add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize))
if t.indirectkey() {
k = *((*unsafe.Pointer)(k))
}
if alg.equal(key, k) {
v := add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+i*uintptr(t.valuesize))
if t.indirectvalue() {
v = *((*unsafe.Pointer)(v))
}
return v
}
}
}
先使用 tophash 的值比较是否相等, 然后在使用比较 key 值是否相等.
插入数据
直接上代码吧
if h.flags&hashWriting != 0 {
throw("concurrent map writes")
}
alg := t.key.alg
hash := alg.hash(key, uintptr(h.hash0))
// Set hashWriting after calling alg.hash, since alg.hash may panic,
// in which case we have not actually done a write.
h.flags ^= hashWriting
if h.buckets == nil {
h.buckets = newobject(t.bucket) // newarray(t.bucket, 1)
}
先判断是否是写状态, 如果有其他 goroutine 在写, 直接 panic
调用 hash 函数, 设置读标志位, 如果 buckets 为空, 则先创建一个
bucket := hash & bucketMask(h.B)
if h.growing() {
growWork(t, h, bucket)
}
b := (*bmap)(unsafe.Pointer(uintptr(h.buckets) + bucket*uintptr(t.bucketsize)))
top := tophash(hash)
计算 bucket mask
如果当前 map 正在扩容, 先执行一次扩容计划
计算偏移地址, 计算 tophash
for {
// 循环遍历一个 bucket
for i := uintptr(0); i < bucketCnt; i++ {
// 判断 tophash 是否相等
if b.tophash[i] != top {
if isEmpty(b.tophash[i]) && inserti == nil {
inserti = &b.tophash[i]
insertk = add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize))
val = add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+i*uintptr(t.valuesize))
}
if b.tophash[i] == emptyRest {
break bucketloop
}
continue
}
// 如果 tophash 相等
// 计算 key 的偏移量
k := add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize))
if t.indirectkey() {
k = *((*unsafe.Pointer)(k))
}
// 判断 key 是否相等
if !alg.equal(key, k) {
// 不相等, 冲突了, 继续 遍历
continue
}
// already have a mapping for key. Update it.
if t.needkeyupdate() {
typedmemmove(t.key, k, key)
}
val = add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+i*uintptr(t.valuesize))
goto done
}
// bucket 溢出桶
ovf := b.overflow(t)
if ovf == nil {
break
}
b = ovf
}
删除
有疑问加站长微信联系（非本文作者）
