/...
return v, true
}
}
}
return unsafe.Pointer(&zeroVal[0]), false
}
使用 v, ok := hash[k]
的形式访问哈希表中元素时,我们能够通过这个布尔值更准确地知道当 v == nil
时,该空指针到底是哈希中存储的元素还是表示该键对应的元素不存在,所以在访问哈希时,作者更推荐使用这一种方式先判断元素是否存在。
上面的过程其实是在正常情况下,访问哈希表中元素时的表现,然而与数组一样,哈希表可能会在装载因子过高或者溢出桶过多时进行扩容,扩容时如何保证访问的性能是一个比较有意思的话题,我们在这里其实也省略了相关的代码,不过会在下面的扩容一节中会展开介绍。
写入
当形如 hash[k]
的表达式出现在赋值符号左侧时,与读取时一样会在编译的 类型检查 和 中间代码生成 期间被转换成调用 mapassign
函数调用,我们可以将该函数分成几个部分介绍,首先是函数会根据传入的键拿到对应的哈希和桶:
func mapassign(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer {
alg := t.key.alg
hash := alg.hash(key, uintptr(h.hash0))
h.flags ^= hashWriting
again:
bucket := hash & bucketMask(h.B)
b := (*bmap)(unsafe.Pointer(uintptr(h.buckets) + bucket*uintptr(t.bucketsize)))
top := tophash(hash)
然后通过遍历比较桶中存储的 tophash
和键的哈希,如果找到了相同结果就会获取目标位置的地址并返回,无论是查找键还是值都会直接通过算术计算进行寻址:
var inserti *uint8
var insertk unsafe.Pointer
var val unsafe.Pointer
bucketloop:
for {
for i := uintptr(0); i < bucketCnt; i++ {
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
}
k := add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize))
if t.indirectkey() {
k = *((*unsafe.Pointer)(k))
}
if !alg.equal(key, k) {
continue
}
val = add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+i*uintptr(t.valuesize))
goto done
}
ovf := b.overflow(t)
if ovf == nil {
break
}
b = ovf
}
当前的哈希表没有处于扩容状态并且装载因子已经超过了 6.5 或者存在了太多溢出的桶时,就会调用 hashGrow
对当前的哈希表进行扩容。
装载因子是同时由 loadFactorNum
和 loadFactDen
两个参数决定的,前者在 Go 源代码中的定义是 13 后者是 2,所以装载因子就是 6.5。
如果当前的桶已经满了,就会调用 newoverflow
创建一个新的桶或者使用 hmap
预先在 noverflow
中创建好的桶来保存数据,新创建桶的指针会被追加到已有桶中,与此同时,溢出桶的创建会增加哈希表的 noverflow
计数器。
if !h.growing() && (overLoadFactor(h.count+1, h.B) || tooManyOverflowBuckets(h.noverflow, h.B)) {
hashGrow(t, h)
goto again
}
if inserti == nil {
newb := h.newoverflow(t, b)
inserti = &newb.tophash[0]
insertk = add(unsafe.Pointer(newb), dataOffset)
val = add(insertk, bucketCnt*uintptr(t.keysize))
}
if t.indirectkey() {
kmem := newobject(t.key)
*(*unsafe.Pointer)(insertk) = kmem
insertk = kmem
}
if t.indirectvalue() {
vmem := newobject(t.elem)
*(*unsafe.Pointer)(val) = vmem
}
typedmemmove(t.key, insertk, key)
*inserti = top
h.count++
done:
return val
}
如果哈希表存储的键值是指针类型,其实就会为当前的键值对分别申请一块新的内存空间,并在插入的位置通过 eypedmemmove
将键移动到申请的内存空间,最后返回键对应值的地址。
扩容
扩容过程的入口其实就是 hashGrow
函数,这个函数的主要作用就是对哈希表进行扩容,扩容的方式分成两种,如果这次扩容是溢出的桶太多导致的,那么这次扩容就是 sameSizeGrow
:
func hashGrow(t *maptype, h *hmap) {
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
}
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 {
h.extra.oldoverflow = h.extra.overflow
h.extra.overflow = nil
}
if nextOverflow != nil {
if h.extra == nil {
h.extra = new(mapextra)
}