Golang 哈希表详解

哈希表介绍

​ 一个映射，也成为关联数组，其实是一个由唯一键组成的集合，而每个键必然关联一个特定的值。这种键到值的关联关系称为映射，若在键到值的关联使用hash计算，就是哈希表，映射至少支持三个操作：

• Add (Key,Value)

• Remove(key)

• value = LookUp (key)

Map的本质

map的底层结构

Golang的map使用溢出桶(链地址法)解决hash冲突

Map结构

type hmap struct {count int // 代表map中元素的数量flags uint8 // 代表当前map的状态B uint8 // 2^B表示当前map中桶的数量noverflow uint16 // map中溢出桶的数量hash0     uint32 // 是哈希的种子，它能为哈希函数的结果引入随机性，这个值在创建哈希表时确定，并在调用哈希函数时作为参数传入buckets unsafe.Pointer // 指向map对应的桶数组的指针oldbuckets unsafe.Pointer // 存储未转移完毕的旧桶，扩容时非空nevacuate uintptr// 扩容时使用，用于标记当前旧桶中小于 nevacuate 的数据都已经转移到了新桶中extra *mapextra // 存储map中的溢出桶
}

桶结构

type bmap struct {// bucketCnt=8tophash [bucketCnt]uint8
}

溢出桶

type mapextra struct {overflow    *[]*bmap // buckets 的溢出桶oldoverflow *[]*bmap // oldbukets 的溢出桶nextOverflow *bmap // 指向下一个溢出桶
}

Map源码

创建

创建map

当使用make创建map时，只有指定的元素个数大于8时，或者使用字面量创建时元素个数>8时才会调用runtime.makemap函数进行map的创建。否则，将调用makemap_small函数创建hmap结构，但此时不会分配桶，而是在赋值(runtime.mapassign)操作时分配桶。

m := make(map[int8]int8, 9)
m1 := map[int8]int8{1: 1, 2: 2,3: 3, 4: 4,5: 5, 6: 6,7: 7, 8: 8,9: 9,}

创建流程

func makemap(t *maptype, hint int, h *hmap) *hmap {// 计算内存分配量时，使用最均匀的情况下的散列分布// hint：触发makemap函数时，传入的第二个参数，若为9,则9个元素可能会分布到不同的9个桶中// t.bucket.size：每个桶占用的字节，其大小等于key*8+value*8+tophash(固定8字节)+overflow指针大小(根据机器字大小4或8字节)// 该步骤主要计算内存溢出的可能性，若可能溢出，将hint置零mem, overflow := math.MulUintptr(uintptr(hint), t.bucket.size)if overflow || mem > maxAlloc {hint = 0}// 初始化hmap结构体if h == nil {h = new(hmap)}// 取得hash种子，hash种子的计算参与存放在当前m中  h.hash0 = fastrand()// 计算出需要的桶的个数B := uint8(0)// 根据hint个元素，循环计算出需要的桶数量// 因为后续涉及到真正的内存分配，所以这里按照最近凑的散列分布，即hint/8来控制桶的数量for overLoadFactor(hint, B) {B++}h.B = B// 开始为桶分配内存if h.B != 0 {var nextOverflow *bmap// makemap函数中的桶分配由makeBucketArray函数来实现// 主要任务：1.分配桶大小 2.若需要预分配溢出桶，则分配h.buckets, nextOverflow = makeBucketArray(t, h.B, nil)if nextOverflow != nil { // 若分配了溢出桶// 将预分配的溢出桶赋值给hmaph.extra = new(mapextra)h.extra.nextOverflow = nextOverflow}}return h
}

桶分配及溢出桶预分配

func makeBucketArray(t *maptype, b uint8, dirtyalloc unsafe.Pointer) (buckets unsafe.Pointer, nextOverflow *bmap) {// 需要分配的桶数量base := bucketShift(b)nbuckets := base// 如果桶的数量>b^4可能需要溢出桶if b >= 4 {// 在桶的数量上加上预估溢出桶数量nbuckets += bucketShift(b - 4)// 计算出桶需要的内存空间sz := t.bucket.size * nbuckets// 因为go将内存划分为不同的大小进行管理，所以这里内存管理器会返回up字节的内存大小，up>=szup := roundupsize(sz)if up != sz {// 计算出分配的内存可以容纳多少个桶nbuckets = up / t.bucket.size}}// 当hash表所有键值被删除或该hash表被回收时dirtyalloc!=nilif dirtyalloc == nil {// 分配bucket数组buckets = newarray(t.bucket, int(nbuckets))} else {// 执行hash内存回收操作buckets = dirtyallocsize := t.bucket.size * nbuckets// 判断bucket是否存在指针对象if t.bucket.ptrdata != 0 {// 清楚包含指针类型元素占用的空间memclrHasPointers(buckets, size)} else {// 清楚非指针类型元素占用的空间memclrNoHeapPointers(buckets, size)}}// 判断是否需要分配溢出桶if base != nbuckets { // 计算出溢出桶数组的指针地址nextOverflow = (*bmap)(add(buckets, base*uintptr(t.bucketsize)))// 计算出最后一个溢出桶的内存地址last := (*bmap)(add(buckets, (nbuckets-1)*uintptr(t.bucketsize)))// 将最后一个溢出桶的溢出指针设置为溢出桶数组的首地址，相当于将溢出桶数组首尾相连，从而避免内存泄漏问题last.setoverflow(t, (*bmap)(buckets))}return buckets, nextOverflow
}

赋值/更新

func mapassign(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer {if h == nil {panic(plainError("assignment to entry in nil map"))}// 因为map是并发不安全的，因此在并发读写的情况下会出现警告if h.flags&hashWriting != 0 {throw("concurrent map writes")}// 通过key和hash种子生成hash值hash := t.hasher(key, uintptr(h.hash0))// 将当前map标记为正在写h.flags ^= hashWriting// 当map中的所有键值对都被删除，内存可能被回收，因此这里重新分配一个bucketif h.buckets == nil {h.buckets = newobject(t.bucket) // newarray(t.bucket, 1)}again:// 通过hash和桶个数进行与运算，得出桶的位置bucket := hash & bucketMask(h.B)// 判断当前map是否处于扩容状态，执行一个桶的搬迁if h.growing() {// 执行一次扩容操作growWork(t, h, bucket)}// 根据map中桶的首地址计算出目标桶的地址b := (*bmap)(add(h.buckets, bucket*uintptr(t.bucketsize)))// 返回hash的高8位top := tophash(hash)var inserti *uint8var insertk unsafe.Pointervar elem unsafe.Pointer
bucketloop:for {for i := uintptr(0); i < bucketCnt; i++ {// 如果第i个tophash 与 key计算出的tophash不同if b.tophash[i] != top {// 判断tophash[i]是否为空，且inserti是否为空，当此条件为true时，标识，当前tophash为第一个遇到的空tophashif isEmpty(b.tophash[i]) && inserti == nil {// 记录当前tophash的内存地址inserti = &b.tophash[i]// 记录当前tophash对应的key的内存地址insertk = add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize))// 记录当前tophash对应的value的内存地址elem = add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+i*uintptr(t.elemsize))}// 若当前tophash 为emptyRest，表示后面的tophash都为空，而第一个空tophash已经被记录，此时则跳出循环if b.tophash[i] == emptyRest {break bucketloop}// 继续循环continue}// 运行至此处表示找到和当前key相同的tophashk := add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize))if t.indirectkey() {k = *((*unsafe.Pointer)(k))}// 如果key不相同 遍历下一个tophashif !t.key.equal(key, k) {continue}// already have a mapping for key. Update it.// 走到此处就可以确定当前为更新操作了// tophash 相同 且key也相同时更新该key的值if t.needkeyupdate() {typedmemmove(t.key, k, key)}// 的value内存所在的地址elem = add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+i*uintptr(t.elemsize))goto done}// 当前桶遍历完，尝试获取溢出桶，若溢出桶不为空，则遍历溢出桶ovf := b.overflow(t)if ovf == nil {break}b = ovf}// 判断是否需要扩容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)elem = add(insertk, bucketCnt*uintptr(t.keysize))}// 若key为指针类型，分配新内存，将insertK指向新分配的内存if t.indirectkey() {kmem := newobject(t.key)*(*unsafe.Pointer)(insertk) = kmeminsertk = kmem}// 若value为指针类型，分配新内存，将elem指向新分配的内存if t.indirectelem() {vmem := newobject(t.elem)*(*unsafe.Pointer)(elem) = vmem}typedmemmove(t.key, insertk, key)*inserti = toph.count++done:if h.flags&hashWriting == 0 {throw("concurrent map writes")}// 清除标记h.flags &^= hashWritingif t.indirectelem() {elem = *((*unsafe.Pointer)(elem))}return elem
}

取值

map取值的函数有两个，runtime.mapaccess1、runtime.mapaccess2区别在于后者返回两个参数v,bool，用以判断map中是否存在相应的key。

func mapaccess1(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer {if msanenabled && h != nil {msanread(key, t.key.size)}// map为空或者元素个数为0 返回元素类型的零值if h == nil || h.count == 0 {if t.hashMightPanic() {t.hasher(key, 0) // see issue 23734}return unsafe.Pointer(&zeroVal[0])}if h.flags&hashWriting != 0 {throw("concurrent map read and map write")}// 根据key 和hash种子计算出key的对应hashhash := t.hasher(key, uintptr(h.hash0))// 当前hash拥有的桶的个数m := bucketMask(h.B)// 获取 hash&m 计算出桶的位置b := (*bmap)(add(h.buckets, (hash&m)*uintptr(t.bucketsize)))// 判断是否处于扩容，即 h.oldbuckets 不为nilif c := h.oldbuckets; c != nil {if !h.sameSizeGrow() {// There used to be half as many buckets; mask down one more power of two.m >>= 1}// 取出旧桶oldb := (*bmap)(add(c, (hash&m)*uintptr(t.bucketsize)))// 若该旧桶尚未迁移if !evacuated(oldb) {b = oldb}}// 计算出tophash 也就是hash的高八位top := tophash(hash)// 开始通过tophash遍历 桶+溢出桶
bucketloop:for ; b != nil; b = b.overflow(t) {for i := uintptr(0); i < bucketCnt; i++ {// 依次判断tophashif b.tophash[i] != top {// 表示后续tophash都为空，退出循环，取值失败if b.tophash[i] == emptyRest {break bucketloop}continue}// 取出map中tophash对应的key值k := add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize))if t.indirectkey() {k = *((*unsafe.Pointer)(k))}// 对比取值的k与tophash对应的key是否相同if t.key.equal(key, k) {// 找到key对应value值e := add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+i*uintptr(t.elemsize))// 若间接引用，需要进行解引用if t.indirectelem() {e = *((*unsafe.Pointer)(e))}return e}}}return unsafe.Pointer(&zeroVal[0])
}

删除

func mapdelete(t *maptype, h *hmap, key unsafe.Pointer) {// 确保没有并发操作mapif h.flags&hashWriting != 0 {throw("concurrent map writes")}// 计算hash值hash := t.hasher(key, uintptr(h.hash0))// 标记当前map处于写状态h.flags ^= hashWriting// 计算出该hash可能存放在哪个桶中bucket := hash & bucketMask(h.B)// 若map处于扩容状态if h.growing() {// 执行一次扩容任务growWork(t, h, bucket)}// 找到桶的地址b := (*bmap)(add(h.buckets, bucket*uintptr(t.bucketsize)))bOrig := b// 计算出tophashtop := tophash(hash)
search:// 遍历桶+溢出桶for ; b != nil; b = b.overflow(t) {for i := uintptr(0); i < bucketCnt; i++ {// 依次对比桶中的tophashif b.tophash[i] != top {// 若桶中tophash为emptyRest，桶中后续空间不存在keyif b.tophash[i] == emptyRest {// 没找到，退出break search}continue}// 计算key的地址k := add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize))k2 := kif t.indirectkey() {k2 = *((*unsafe.Pointer)(k2))}// 若当前key与想要删除的key不同，继续遍历if !t.key.equal(key, k2) {continue}// 清除keyif t.indirectkey() {// 间接引用*(*unsafe.Pointer)(k) = nil} else if t.key.ptrdata != 0 {memclrHasPointers(k, t.key.size)}// 计算value地址e := add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+i*uintptr(t.elemsize))// 清除vlaueif t.indirectelem() {// 间接引用*(*unsafe.Pointer)(e) = nil} else if t.elem.ptrdata != 0 {// 指针memclrHasPointers(e, t.elem.size)} else {// 非指针memclrNoHeapPointers(e, t.elem.size)}// 将该tophash设为emptyOneb.tophash[i] = emptyOne// 当前为最后一个桶或者桶中tophash都为emptyRest，跳出循环if i == bucketCnt-1 {if b.overflow(t) != nil && b.overflow(t).tophash[0] != emptyRest {goto notLast}} else {if b.tophash[i+1] != emptyRest {goto notLast}}// 向上查找，将tophash为emptyOne的tophash标记为emptyRestfor {b.tophash[i] = emptyRestif i == 0 {if b == bOrig {break // beginning of initial bucket, we're done.}// Find previous bucket, continue at its last entry.c := bfor b = bOrig; b.overflow(t) != c; b = b.overflow(t) {}i = bucketCnt - 1} else {i--}if b.tophash[i] != emptyOne {break}}notLast:h.count--// 若map中元素被清空if h.count == 0 {// 重置hash算法h.hash0 = fastrand()}break search}}if h.flags&hashWriting == 0 {throw("concurrent map writes")}h.flags &^= hashWriting
}

Map 扩容

扩容模式判断

map扩容由赋值操作runtime.mapassign触发。

map扩容分两种：

• 翻倍扩容：大多数桶都处于满负载状态

  元素数量达到map负载因子6.5：count/buckets>6.5

  func overLoadFactor(count int, B uint8) bool {return count > bucketCnt && uintptr(count) > loadFactorNum*(bucketShift(B)/loadFactorDen)
  }
  

• 等量扩容：溢出桶过多，元素过少

  h.B<=15，溢出桶>=2^B

  h.B>15，溢出桶>=2^15

  func tooManyOverflowBuckets(noverflow uint16, B uint8) bool {if B > 15 {B = 15}return noverflow >= uint16(1)<<(B&15)
  }
  

扩容前的准备

并没有直接进行扩容，而是遵循写时复制原则，只有在对数据操作时才进行扩容。

func hashGrow(t *maptype, h *hmap) {bigger := uint8(1)// 溢出桶太多，保持哈希表大小不变if !overLoadFactor(h.count+1, h.B) {bigger = 0h.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}// 设置Bh.B += biggerh.flags = flagsh.oldbuckets = oldbucketsh.buckets = newbucketsh.nevacuate = 0h.noverflow = 0if h.extra != nil && h.extra.overflow != nil {if h.extra.oldoverflow != nil {throw("oldoverflow is not nil")}// 将当前溢出桶设置为旧的溢出桶h.extra.oldoverflow = h.extra.overflowh.extra.overflow = nil}if nextOverflow != nil {if h.extra == nil {h.extra = new(mapextra)}h.extra.nextOverflow = nextOverflow}
}

执行扩容

具体的扩容操作被分散在对map的操作中(赋值、取值、删除)，这样做的好处是避免了，一次性完成桶搬迁所产生的性能抖动问题。

执行扩容任务

func growWork(t *maptype, h *hmap, bucket uintptr) {// 搬迁命中的桶evacuate(t, h, bucket&h.oldbucketmask())// 若搬迁任务没有完成，在游标处再搬迁一个桶if h.growing() {evacuate(t, h, h.nevacuate)}
}

扩容具体实现

新桶数量-1&旧桶位置=旧桶在新桶中的位置

并发安全

通过源码可以观察到Go并没有为map进行并发保护，若并发操作map会触发painc。

sync.map提供并发安全的map。

func main() {m := make(map[int]int)go func() {for i := 0; i < 1000; i++ {m[i] = i + 1}}()go func() {for i := 0; i < 1000; i++ {fmt.Println(m[i])}}()time.Sleep(3 * time.Second)
}

红酒品牌