在上一节中我们介绍了 数组和切片的实现原理，这一节会介绍 Golang 中的另一个集合元素 — 哈希，也就是 Map 的实现原理；哈希表是除了数组之外，最常见的数据结构，几乎所有的语言都会有数组和哈希表这两种集合元素，有的语言将数组实现成列表，有的语言将哈希表称作结构体或者字典，但是它们其实就是两种设计集合元素的思路，数组用于表示一个元素的序列，而哈希表示的是键值对之间映射关系，只是不同语言的叫法和实现稍微有些不同。
概述
哈希表 是一种古老的数据结构，在 1953 年就有人使用拉链法实现了哈希表，它能够根据键(Key)直接访问内存中的存储位置，也就是说我们能够直接通过键找到该键对应的一个值，哈希表名称的来源是因为它使用了哈希函数将一个键映射到一个桶中，这个桶中就可能包含该键对应的值。
哈希函数
哈希表的实现关键在于如何选择哈希函数，哈希函数的选择和在很大程度上能够决定哈希表的读写性能，在理想情况下，哈希函数应该能够将不同键映射到唯一的索引上，但是键集合的数量会远远大于映射的范围，不同的键经过哈希函数的处理应该会返回唯一的值，这要求哈希函数的输出范围大于输入范围，所以在实际使用时，这个理想状态是不可能实现的。
比较实际的方式是让哈希函数的结果能够均匀分布，这样虽然哈希会发生碰撞和冲突，但是我们只需要解决哈希碰撞的问题就可以在工程上去使用这种更实际的方案，结果不均匀的哈希函数会造成更多的冲并带来更差的性能。
在一个使用结果较为均匀的哈希函数中，哈希的增删改查都需要 O(1) 的时间复杂度，但是非常不均匀的哈希函数会导致所有的操作都会占用最差 O(n) 的复杂度，所以在哈希表中使用好的哈希函数是至关重要的。
冲突解决
就像我们之前所提到的，在通常情况下，哈希函数输入的范围一定会远远大于输出的范围，所以我们一定会在使用哈希表的过程中遇到冲突，如果有一个不会出现冲突的完美哈希函数，那么我们其实只需要将所有的值都存储在一个一维的数组中就可以了。
就像上面提到的，这种场景在现实中基本上是不会存在的，我们的哈希函数往往都是不完美的并且输出的范围也都是有限的，这也一定会发生哈希的碰撞，我们就需要使用一些方法解决哈希的碰撞问题，常见的就是开放寻址法和拉链法两种。
开放寻址法
开放寻址法 是一种在哈希表中解决哈希碰撞的方法，这种方法的核心思想是在一维数组对元素进行探测和比较以判断待查找的目标键是否存在于当前的哈希表中，如果我们使用开放寻址法来实现哈希表，那么在初始化哈希表时就会创建一个新的数组，如果当我们向当前『哈希表』写入新的数据时发生了冲突，就会将键值对写入到下一个不为空的位置：
上图展示了键 Key3 与已经存入『哈希表』中的两个键 Key1 和 Key2 发生冲突时，Key3 会被自动写入到 Key2 后面的空闲内存上，在这时我们再去读取 Key3 对应的值时就会先对键进行哈希并所索引到 Key1 上，对比了目标键与 Key1 发现不匹配就会读取后面的元素，直到内存为空或者找到目标元素。
当我们查找某个键对应的数据时，就会对哈希命中的内存进行线性探测，找到目标键值对或者空内存就意味着这一次查询操作的结束。
开放寻址法中对性能影响最大的就是装载因子，它是数组中元素的数量与数组大小的比值，随着装载因子的增加，线性探测的平均用时就会逐渐增加，这会同时影响哈希表的查找和插入性能，当装载率超过 70% 之后，哈希表的性能就会急剧下降，而一旦装载率达到 100%，整个哈希表就会完全失效，所以在实现哈希表时一定要时刻关注装载因子的变化。
拉链法
与开放地址法相比，拉链法是哈希表中最常见的实现方法，大多数的编程语言都是用拉链法实现哈希表，它的实现相对比较简单，平均查找的长度也比较短，而且各个用于存储节点的内存都是动态申请的，可以节省比较多的存储空间。
拉链法的实现其实就是使用数组加上链表组合起来实现哈希表，数组中的每一个元素其实都是一个链表，我们可以将它看成一个可以扩展的二维数组：
当我们需要将一个键值对加入一个哈希表时，键值对中的键都会先经过一个哈希函数，哈希函数返回的哈希会帮助我们『选择』一个桶，然后遍历当前桶中持有的链表，找到键相同的键值对执行更新操作或者遍历到链表的末尾追加一个新的键值对。
如果要通过某个键在哈希表中获取对应的值，就会经历如下的过程：
Key11 就是展示了一个键在哈希表中不存在的例子，当哈希表发现它命中 2 号桶时，它会依次遍历桶中的链表，解决遍历到链表的末尾也没有找到期望的键，所以该键对应的值就是空。
在一个性能比较好的哈希表中，每一个桶中都应该有 0 或者 1 个元素，有时会有 2~3 个元素，很少会发生遇到超过这个数量的情况，每一次读写哈希表的时间基本上都花在了定位桶和遍历链表这两个过程，有 1000 个桶的哈希表如果保存了 10000 个键值对，它的性能是保存 1000 个键值对的 1/10，但是仍然比一个链表的性能好 1000 倍。
初始化
我们既然已经介绍了常见哈希表的一些基本原理和实现方法，那么可以开始介绍文章正题，也就是 Go 语言中哈希表的实现原理，首先要讲的就是哈希在 Go 中的表示以及初始化哈希的两种方法 — 通过字面量和运行时。
结构体
hmaptype hmap struct {
count int
flags uint8
B uint8
noverflow uint16
hash0 uint32
buckets unsafe.Pointer
oldbuckets unsafe.Pointer
nevacuate uintptr
extra *mapextra
}
countBbucketslen(buckets) == 2^Bhash0oldbucketsbucketsbucketshmaphmapfunc hmap(t *types.Type) *types.Type {
bmap := bmap(t)
fields := []*types.Field{
makefield("count", types.Types[TINT]),
makefield("flags", types.Types[TUINT8]),
makefield("B", types.Types[TUINT8]),
makefield("noverflow", types.Types[TUINT16]),
makefield("hash0", types.Types[TUINT32]),
makefield("buckets", types.NewPtr(bmap)),
makefield("oldbuckets", types.NewPtr(bmap)),
makefield("nevacuate", types.Types[TUINTPTR]),
makefield("extra", types.Types[TUNSAFEPTR]),
}
hmap := types.New(TSTRUCT)
hmap.SetNoalg(true)
hmap.SetFields(fields)
dowidth(hmap)
t.MapType().Hmap = hmap
hmap.StructType().Map = t
return hmap
}
hmap字面量
如果我们在 Go 语言中使用字面量的方式初始化哈希表，与其他的语言非常类似，一般都会使用如下所示的格式：
hash := map[string]int{
"1": 2,
"3": 4,
"5": 6,
}
maplitmaplitfunc maplit(n *Node, m *Node, init *Nodes) {
a := nod(OMAKE, nil, nil)
a.Esc = n.Esc
a.List.Set2(typenod(n.Type), nodintconst(int64(n.List.Len())))
litas(m, a, init)
var stat, dyn []*Node
for _, r := range n.List.Slice() {
stat = append(stat, r)
}
if len(stat) > 25 {
// ...
} else {
addMapEntries(m, stat, init)
}
}
addMapEntrieshash := make(map[string]int, 3)
hash["1"] = 2
hash["3"] = 4
hash["5"] = 6
而如果哈希表中元素的数量超过了 25 个，就会在编译期间创建两个数组分别存储键和值的信息，这些键值对会通过一个如下所示的 for 循环加入目标的哈希：
hash := make(map[string]int, 26)
vstatk := []string{"1", "2", "3", ... ， "26"}
vstatv := []int{1, 2, 3, ... , 26}
for i := 0; i len(vstak); i++ {
hash[vstatk[i]] = vstatv[i]
}
[]运行时
makemakemakemapfunc makemap(t *maptype, hint int, h *hmap) *hmap {
mem, overflow := math.MulUintptr(uintptr(hint), t.bucket.size)
if overflow || mem > maxAlloc {
hint = 0
}
if h == nil {
h = new(hmap)
}
h.hash0 = fastrand()
B := uint8(0)
for overLoadFactor(hint, B) {
B++
}
h.B = B
if h.B != 0 {
var nextOverflow *bmap
h.buckets, nextOverflow = makeBucketArray(t, h.B, nil)
if nextOverflow != nil {
h.extra = new(mapextra)
h.extra.nextOverflow = nextOverflow
}
}
return h
}
fastrandhintmakeBucketArrayB2^(B-4)bmaptophashtype bmap struct {
tophash [bucketCnt]uint8
}
bmapfunc bmap(t *types.Type) *types.Type {
bucket := types.New(TSTRUCT)
keytype := t.Key()
valtype := t.Elem()
dowidth(keytype)
dowidth(valtype)
field := make([]*types.Field, 0, 5)
arr := types.NewArray(types.Types[TUINT8], BUCKETSIZE)
field = append(field, makefield("topbits", arr))
arr = types.NewArray(keytype, BUCKETSIZE)
keys := makefield("keys", arr)
field = append(field, keys)
arr = types.NewArray(valtype, BUCKETSIZE)
values := makefield("values", arr)
field = append(field, values)
if int(valtype.Align) > Widthptr || int(keytype.Align) > Widthptr {
field = append(field, makefield("pad", types.Types[TUINTPTR]))
}
otyp := types.NewPtr(bucket)
if !types.Haspointers(valtype) && !types.Haspointers(keytype) {
otyp = types.Types[TUINTPTR]
}
overflow := makefield("overflow", otyp)
field = append(field, overflow)
// ...
t.MapType().Bucket = bucket
bucket.StructType().Map = t
return bucket
}
这种做法是因为 Go 语言在执行哈希的操作时会直接操作内存空间，与此同时由于键值类型的不同占用的空间大小也不同，也就导致了类型和占用的内存不确定，所以没有办法在 Go 语言的源代码中进行声明。
bmaptype bmap struct {
topbits [8]uint8
keys [8]keytype
values [8]valuetype
pad uintptr
overflow uintptr
}
每一个哈希表中的桶最多只能存储 8 个元素，如果桶中存储的元素超过 8 个，那么这个哈希表的执行效率一定会急剧下降，不过在实际使用中如果一个哈希表存储的数据逐渐增多，我们会对哈希表进行扩容或者使用额外的桶存储溢出的数据，不会让单个桶中的数据超过 8 个：
溢出桶只是临时的解决方案，创建过多的溢出桶最终也会导致哈希的扩容。
Go 语言的运行时会为哈希表分配内存空间，用于存储哈希表中的键值对，无论是哈希的结构还是桶的结构都是在运行时初始化的，只是后者并在源代码中存在事实的结构，它是一个使用代码生成的『虚拟』结构体。
操作
哈希表作为一种数据结构，我们肯定需要研究它的操作，也就是不同读写操作的实现原理，当我们谈到哈希表的读时，一般都是通过下标和遍历两种方式读取数据结构中存储的数据：
_ = hash[key]
for k, v := range hash {
// k, v
}
rangedeletehash[key] = value
hash[key] = newValue
delete(hash, key)
我们会对这些不同的操作一一讨论并给出它们底层具体的实现原理，这些操作大多都是通过编译期间和运行时共同实现的，介绍的过程中可能会省略一些编译期间的相关知识，具体的可以阅读之前的章节 编译过程概述 了解编译的过程和原理。
访问
hash[key]OINDEXOINDEXMAPwalkexprOINDEXMAPv := hash[key] // => v := *mapaccess1(maptype, hash, &key)
v, ok := hash[key] // => v, ok := mapaccess2(maptype, hash, &key)
mapaccess1mapaccess2mapaccess1func mapaccess1(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer {
alg := t.key.alg
hash := alg.hash(key, uintptr(h.hash0))
m := bucketMask(h.B)
b := (*bmap)(add(h.buckets, (hash&m)*uintptr(t.bucketsize)))
top := tophash(hash)
bucketloop:
for ; b != nil; b = b.overflow(t) {
for i := uintptr(0); i if b.tophash[i] != top {
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
}
}
}
return unsafe.Pointer(&zeroVal[0])
}
bucketMaskaddtophashtophashtopbitsuint8tophashtopbitstophashmapaccess2mapaccess1func mapaccess2(t *maptype, h *hmap, key unsafe.Pointer) (unsafe.Pointer, bool) {
// ...
bucketloop:
for ; b != nil; b = b.overflow(t) {
for i := uintptr(0); i if b.tophash[i] != top {
if b.tophash[i] == emptyRest {
break bucketloop
}
continue
}
k := add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize))
// ...
if alg.equal(key, k) {
v := add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+i*uintptr(t.valuesize))
//...
return v, true
}
}
}
return unsafe.Pointer(&zeroVal[0]), false
}
v, ok := hash[k]v == nil上面的过程其实是在正常情况下，访问哈希表中元素时的表现，然而与数组一样，哈希表可能会在装载因子过高或者溢出桶过多时进行扩容，扩容时如何保证访问的性能是一个比较有意思的话题，我们在这里其实也省略了相关的代码，不过会在下面的扩容一节中会展开介绍。
写入
hash[k]mapassignfunc 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 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
}
hashGrowloadFactorNumloadFactDennewoverflowhmapnoverflownoverflow 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扩容
hashGrowsameSizeGrowfunc 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)
}
h.extra.nextOverflow = nextOverflow
}
}
makeBucketArrayoldbucketsbucketssameSizeGrowevacuateevacuatefunc evacuate(t *maptype, h *hmap, oldbucket uintptr) {
b := (*bmap)(add(h.oldbuckets, oldbucket*uintptr(t.bucketsize)))
newbit := h.noldbuckets()
if !evacuated(b) {
var xy [2]evacDst
x := &xy[0]
x.b = (*bmap)(add(h.buckets, oldbucket*uintptr(t.bucketsize)))
x.k = add(unsafe.Pointer(x.b), dataOffset)
x.v = add(x.k, bucketCnt*uintptr(t.keysize))
if !h.sameSizeGrow() {
y := &xy[1]
y.b = (*bmap)(add(h.buckets, (oldbucket+newbit)*uintptr(t.bucketsize)))
y.k = add(unsafe.Pointer(y.b), dataOffset)
y.v = add(y.k, bucketCnt*uintptr(t.keysize))
}
evacuateevacDstevacDstevacDst for ; b != nil; b = b.overflow(t) {
k := add(unsafe.Pointer(b), dataOffset)
v := add(k, bucketCnt*uintptr(t.keysize))
for i := 0; i 1, add(k, uintptr(t.keysize)), add(v, uintptr(t.valuesize)) {
top := b.tophash[i]
k2 := k
var useY uint8
if !h.sameSizeGrow() {
hash := t.key.alg.hash(k2, uintptr(h.hash0))
if hash&newbit != 0 {
useY = 1
}
}
b.tophash[i] = evacuatedX + useY
dst := &xy[useY]
if dst.i == bucketCnt {
dst.b = h.newoverflow(t, dst.b)
dst.i = 0
dst.k = add(unsafe.Pointer(dst.b), dataOffset)
dst.v = add(dst.k, bucketCnt*uintptr(t.keysize))
}
dst.b.tophash[dst.i&(bucketCnt-1)] = top
typedmemmove(t.key, dst.k, k)
typedmemmove(t.elem, dst.v, v)
dst.i++
dst.k = add(dst.k, uintptr(t.keysize))
dst.v = add(dst.v, uintptr(t.valuesize))
}
}
}
if oldbucket == h.nevacuate {
advanceEvacuationMark(h, t, newbit)
}
}
typedmemmoveadvanceEvacuationMarknevacuateevacuateoldbucketsoldbucketsevacuatefunc mapaccess1(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer {
// ...
alg := t.key.alg
hash := alg.hash(key, uintptr(h.hash0))
m := bucketMask(h.B)
b := (*bmap)(add(h.buckets, (hash&m)*uintptr(t.bucketsize)))
if c := h.oldbuckets; c != nil {
if !h.sameSizeGrow() {
m >>= 1
}
oldb := (*bmap)(add(c, (hash&m)*uintptr(t.bucketsize)))
if !evacuated(oldb) {
b = oldb
}
}
bucketloop:
// ...
}
evacuategrowWorkfunc 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)
if h.growing() {
growWork(t, h, bucket)
}
// ...
}
growWork删除
deletedeleteODELETEmapdeletemapdeletemapdelete_faststrmapdelete_fast32mapdelete_fast64func walkexpr(n *Node, init *Nodes) *Node {
switch n.Op {
case ODELETE:
init.AppendNodes(&n.Ninit)
map_ := n.List.First()
key := n.List.Second()
map_ = walkexpr(map_, init)
key = walkexpr(key, init)
t := map_.Type
fast := mapfast(t)
if fast == mapslow {
key = nod(OADDR, key, nil)
}
n = mkcall1(mapfndel(mapdelete[fast], t), nil, init, typename(t), map_, key)
}
}
mapdeletememclrHasPointersmemclrNoHeapPointersfunc mapdelete(t *maptype, h *hmap, key unsafe.Pointer) {
alg := t.key.alg
hash := alg.hash(key, uintptr(h.hash0))
bucket := hash & bucketMask(h.B)
if h.growing() {
growWork(t, h, bucket)
}
b := (*bmap)(add(h.buckets, bucket*uintptr(t.bucketsize)))
bOrig := b
top := tophash(hash)
search:
for ; b != nil; b = b.overflow(t) {
for i := uintptr(0); i if b.tophash[i] != top {
if b.tophash[i] == emptyRest {
break search
}
continue
}
k := add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize))
k2 := k
if !alg.equal(key, k2) {
continue
}
if t.indirectkey() {
*(*unsafe.Pointer)(k) = nil
} else if t.key.kind&kindNoPointers == 0 {
memclrHasPointers(k, t.key.size)
}
v := add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+i*uintptr(t.valuesize))
if t.indirectvalue() {
*(*unsafe.Pointer)(v) = nil
} else if t.elem.kind&kindNoPointers == 0 {
memclrHasPointers(v, t.elem.size)
} else {
memclrNoHeapPointers(v, t.elem.size)
}
b.tophash[i] = emptyOne
}
// ...
}
}
}
mapdeletedeleteODELETEmapdelete总结
Go 语言中使用拉链法来解决哈希碰撞的问题实现了哈希表，访问、写入和删除等操作都在编译期间被转换成了对应的运行时函数或者方法。
tophash随着键值对数量的增加，溢出桶的数量和哈希的装载因子也会逐渐升高，超过一定范围时就会触发扩容操作，扩容时会将桶的数量分配，元素再分配的过程也是在调用写操作时增量进行的，不会造成性能的瞬时巨大波动。
Reference
Hash table
Open addressing
Separate Chaining: Concept, Advantages & Disadvantages
推荐阅读
深度解密Go语言之map
喜欢本文的朋友，欢迎关注“Go语言中文网”：