青梅梦呓

和世界交手的这许多年,你是否光彩依旧,兴致盎然

0%

理解Go语言的哈希表

哈希表是除了数组之外最常用的数据结构,几乎任何语言都有数组和哈希表这两个集合的实现,有些语言(比如Python) 将哈希表称之为字典,将数组称之为列表。但是它们是两种设计集合元素的思路,数组用于表示元素的序列,而哈希表示的是键值对之间映射关系,只是不同语言的叫法和实现稍微有些不同。Go语言中数组更常用到的是切片slice,哈希表则是map

设计原理

哈希表的常用不仅因为它 O(1) 的读写性能非常优秀,还因为它提供了键值之间的映射。想要实现一个性能优异的哈希表,需要注意两个关键点 —— 哈希函数和冲突解决方法。

哈希函数

哈希函数可以把给定的数据转换成固定长度的无规律数值。转换后的无规律数值可以作为 数据摘要应用于各种各样的场景;可以将哈希函数想像成搅拌机,可以总结出哈希函数的以下特点:

  1. 输出的哈希值数据长度不变,与输入数据的长度大小无关;
  2. 若输入的数据相同,不管计算多少次,输出的结果一定一致;
  3. 即使输入的数据相似, 但哪怕它们只有一比特的差别, 那么输出的哈希值也会 有很大的差异;
  4. 即使输入的两个数据完全不同,输出的哈希值也有可能是相同的(即哈希冲突);
  5. 不太可能从哈希值反向推算出原本的数据
  6. 求哈希值的计算要相对容易

5d965c890d5586146dda72be407a8ab0.png

哈希函数的选择在很大程度上能够决定哈希表的读写性能,在理想情况下,哈希函数应该能够将不同键映射到不同的索引上,这要求哈希函数输出范围大于输入范围,但是由于键的数量会远远大于映射的范围,所以在实际使用时,这个理想的结果是不可能实现的。

比较实际的方式是让哈希函数的结果能够尽可能的均匀分布,然后通过工程上的手段解决哈希冲突的问题,但是哈希的结果一定要尽可能均匀,结果不均匀的哈希函数会造成更多的冲突并导致更差的读写性能。

在一个使用结果较为均匀的哈希函数中,哈希的增删改查都需要 O(1) 的时间复杂度,但是非常不均匀的哈希函数会导致所有的操作都会占用最差 O(n) 的复杂度,所以在哈希表中使用好的哈希函数是至关重要的。

哈希冲突解决

在通常情况下,哈希函数输入的范围一定会远远大于输出的范围,所以在使用哈希表时一定会遇到冲突,哪怕我们使用了完美的哈希函数,当输入的键足够多最终也会造成冲突;然而我们的哈希函数往往都是不完美的,输出的范围是有限的,所以一定会发生哈希碰撞,这时就需要一些方法来解决哈希碰撞的问题,常见方法的就是开放寻址法和拉链法。

开放寻址法

开放寻址法的核心思想是对数组中的元素依次探测和比较以判断目标键值对是否存在于哈希表中,如果我们使用开放寻址法来实现哈希表,那么在支撑哈希表的数据结构就是数组,不过因为数组的长度有限。
我们将每个人的性别作为数 据进行存储,键为人名,值为对应的性别。当我们向当前哈希表写入新的数据时发生了冲突,就会将键值对写入到下一个不为空的位置.

开放寻址法首先计算出元素的直接哈希地址 H ( key ) ,如果该存储单元已被其他元素占用,则继续查看地址为 H ( key ) + d 2 的存储单元,如此重复直至找到某个存储单元为空时,将关键字为 key 的数据元素存放到该单元。

增量 d 可以有不同的取法,并根据其取法有不同的称呼:

  1. di = 1 , 2 , 3 , …… 线性探测再哈希;
  2. di = 1^2 ,- 1^2 , 2^2 ,- 2^2 , k^2, -k^2…… 二次探测再哈希;
  3. di = 伪随机序列 伪随机再散列;

开放寻址法中对性能影响最大的就是装载因子,它是数组中元素的数量与数组大小的比值,随着装载因子的增加,线性探测的平均用时就会逐渐增加,这会同时影响哈希表的读写性能,当装载率超过 70% 之后,哈希表的性能就会急剧下降,而一旦装载率达到 100%,整个哈希表就会完全失效,这时查找任意元素都需要遍历数组中全部的元素,所以在实现哈希表时一定要时刻关注装载因子的变化。

拉链法

拉链法是哈希表中最常见的实现方法,大多数的编程语言都用拉链法实现哈希表,它的实现比较开放地址法稍微复杂一些,但是平均查找的长度也比较短,各个用于存储节点的内存都是动态申请的,可以节省比较多的存储空间。

实现拉链法一般会使用数组加上链表,不过有一些语言会在拉链法的哈希中引入红黑树以优化性能,拉链法会使用链表数组作为哈希底层的数据结构,我们可以将它看成一个可以扩展的『二维数组』:

2a4b4cfd1e9be8f66cac6b14de3c2197.png

如上图所示,当需要将某个键值对写入哈希表中的时候,先对键经历一个哈希过程,就是搅拌机的搅拌过程,这个会帮我们选择一个桶,和开放地址法一样,选择桶的方式就是直接对哈希返回的结果取模:

1
index := hash("Ally") % array.len

选择了 3 号桶之后就可以遍历当前桶中的链表了,在遍历链表的过程中会遇到以下两种情况:

  1. 找到键相同的键值对 —— 更新键对应的值;
  2. 没有找到键相同的键值对 —— 在链表的末尾追加新键值对;

当读取数据的时候,先找到桶的标号,然后依次遍历桶中的链表(有些是红黑树),如果遍历到链表的末尾也没有找到期望的键,那就返回空。

在一个性能比较好的哈希表中,每一个桶中都应该有 01 个元素,有时会有 23 个,很少会超过这个数量,计算哈希、定位桶和遍历链表三个过程是哈希表读写操作的主要开销,使用拉链法实现的哈希也有装载因子这一概念:

装载因子 := 元素数量 / 桶数量

拉链法的装载因子越大,哈希的读写性能就越差,在一般情况下使用拉链法的哈希表装载因子都不会超过 1,当哈希表的装载因子较大时就会触发哈希的扩容,创建更多的桶来存储哈希中的元素,保证性能不会出现严重的下降。

Go语言哈希表

Go 语言运行时同时使用了多个数据结构组合表示哈希表,其中使用 hmap 结构体来表示哈希,看一下这个结构体内部的字段:

1
2
3
4
5
6
7
8
9
10
11
12
13
type hmap struct {
count int
flags uint8
B uint8
noverflow uint16
hash0 uint32

buckets unsafe.Pointer
oldbuckets unsafe.Pointer
nevacuate uintptr

extra *mapextra
}
  1. count 表示当前哈希表中的元素数量;
  2. B 表示当前哈希表持有的 buckets 数量,但是因为哈希表中桶的数量都 2 的倍数,所以该字段会存储对数,也就是 len(buckets) == 2^B
  3. hash0 是哈希的种子,它能为哈希函数的结果引入随机性,这个值在创建哈希表时确定,并在调用哈希函数时作为参数传入;
  4. oldbuckets 是哈希在扩容时用于保存之前 buckets 的字段,它的大小是当前 buckets 的一半;

ed2701bc8291c06642a6dcae3dc54ea9.png

如上图所示哈希表 hmap 的桶就是 bmap,每一个 bmap 都能存储 8 个键值对,当哈希表中存储的数据过多,单个桶无法装满时就会使用 extra.overflow 中桶存储溢出的数据。上述两种不同的桶在内存中是连续存储的,我们在这里将它们分别称为正常桶和溢出桶,上图中黄色的 bmap 就是正常桶,绿色的 bmap 是溢出桶,溢出桶是在 Go 语言还使用 C 语言实现时就使用的设计3,由于它能够减少扩容的频率所以一直使用至今。

bmap的定义在Go语言的源码中如下:

1
2
3
4
5
6
7
type bmap struct {
topbits [8]uint8
keys [8]keytype
values [8]valuetype
pad uintptr
overflow uintptr
}

这个topbits存储了键的哈希的高 8 位,通过比较不同键的哈希的高 8 位可以减少访问键值对次数以提高性能。

初始化

Go语言可以通过字面量或者map关键字在运行时来初始化哈希表,我们分开来说。

使用字面量

1
2
3
4
5
hash := map[string]string{
"name": "青梅",
"age": ”20",
"gender": "male"
}

在初始化哈希时需要声明键值对的类型,这种使用字面量初始化的方式最终都会通过cmd/compile/internal/gc/sinit.go文件中的maplit函数进行初始化,

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
func 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)
}
}

当哈希表中的元素数量少于或者等于 25 个时,编译器会直接调用 addMapEntries 将字面量初始化的结构体转换成以下的代码,将所有的键值对一次加入到哈希表中,这种方式像极了数组和切片的初始化方式,

1
2
3
4
hash := make(map[string]string, 3)
hash["name"] = “青梅”
hash["age"] = "20"
hash["gender"] = "male"

一旦超过25个,会在编译期间创建两个数组分别存储键和值的信息,这些键值对会通过一个如下所示的 for 循环加入目标的哈希:

1
2
3
4
5
6
hash := make(map[string]int, 26)
vstatk := []string{"A", "B", "C", ... , "Z"}
vstatv := []int{1, 2, 3, ... , 26}
for i := 0; i < len(vstak); i++ {
hash[vstatk[i]] = vstatv[i]
}

上面的两个切片还会被进一步展开初始化,在数组和切片系列文章已经分析过了,就不再赘述。不过可以看到,无论hash中的元素数目比25个多还是少,在哈希表的初始化都是使用的make关键字进行初始化的。

使用make关键字

使用 make 创建哈希,Go 语言编译器会在类型检查期间将它们转换成对 runtime.makemap 的调用,使用字面量来初始化哈希也只是语言提供的辅助工具,最后调用的都是 runtime.makemap

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
unc makemap(t *maptype, hint int, h *hmap) *hmap {
mem, overflow := math.MulUintptr(uintptr(hint), t.bucket.size)
if overflow || mem > maxAlloc {
hint = 0
}

// initialize Hmap
if h == nil {
h = new(hmap)
}
h.hash0 = fastrand()

// Find the size parameter B which will hold the requested # of elements.
// For hint < 0 overLoadFactor returns false since hint < bucketCnt.
B := uint8(0)
for overLoadFactor(hint, B) {
B++
}
h.B = B

// allocate initial hash table
// if B == 0, the buckets field is allocated lazily later (in mapassign)
// If hint is large zeroing this memory could take a while.
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
}

这个函数的执行过程会分成以下几个部分:

  1. 计算哈希占用的内存是否溢出或者超出能分配的最大值;
  2. 调用 fastrand 获取一个随机的哈希种子;
  3. 根据传入的 hint 计算出需要的最小需要的桶的数量;
  4. 使用 runtime.makeBucketArray 创建用于保存桶的数组;

makeBucketArray 函数会根据传入的 B 计算出的需要创建的桶数量在内存中分配一片连续的空间用于存储数据:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
func makeBucketArray(t *maptype, b uint8, dirtyalloc unsafe.Pointer) (buckets unsafe.Pointer, nextOverflow *bmap) {
base := bucketShift(b)
nbuckets := base
// For small b, overflow buckets are unlikely.
// Avoid the overhead of the calculation.
if b >= 4 {
// Add on the estimated number of overflow buckets
// required to insert the median number of elements
// used with this value of b.
nbuckets += bucketShift(b - 4)
sz := t.bucket.size * nbuckets
up := roundupsize(sz)
if up != sz {
nbuckets = up / t.bucket.size
}
}

...
}

当桶的数量小于 2^4 时,由于数据较少、使用溢出桶的可能性较低,这时就会省略创建的过程以减少额外开销;当桶的数量多于 2^4 时,就会额外创建 2^𝐵−4 个溢出桶,在正常情况下,正常桶和溢出桶在内存中的存储空间是连续的,只是被 hmap 中的不同字段引用,当溢出桶数量较多时会通过 runtime.newobject 创建新的溢出桶。

读写操作

1
2
3
4
5
val := hash[key]

for key, val := range hash {
// k, v
}

这两种方式虽然都能读取哈希表中的数据,但是使用的函数和底层的原理完全不同,前者需要知道哈希的键并且一次只能获取单个键对应的值,而后者可以遍历哈希中的全部键值对,访问数据时也不需要预先知道哈希的键。

Go语言还提供了一个内置的delete函数来删除哈希表中的元素

1
2
3
hash[key] = value
hash[key] = newValue
delete(hash, key)

根据键访问

在编译的类型检查期间,hash[key] 以及类似的操作都会被转换成对哈希的 OINDEXMAP 操作,中间代码生成阶段会在 cmd/compile/internal/gc/walk.go文件中的walkexpr函数中将这些 OINDEXMAP 操作转换成如下的代码:

1
2
v     := hash[key] // => v     := *mapaccess1(maptype, hash, &key)
v, ok := hash[key] // => v, ok := mapaccess2(maptype, hash, &key)
  1. 接受参数仅为一个时,会使用 runtime.mapaccess1,该函数仅会返回一个指向目标值的指针;
  2. 接受两个参数时,会使用 runtime.mapaccess2,除了返回目标值之外,它还会返回一个用于表示当前键对应的值是否存在的布尔值:

mapaccess1 函数会先通过哈希表设置的哈希函数、种子获取当前键对应的哈希,再通过 bucketMaskadd 函数拿到该键值对所在的桶序号和哈希最上面的 8 位数字。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
func 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 < bucketCnt; 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
}
}
}
return unsafe.Pointer(&zeroVal[0])
}

range访问

写入

当形如 hash[k] 的表达式出现在赋值符号左侧时,该表达式也会在编译期间转换成调用 runtime.mapassign 函数,该函数与 runtime.mapaccess1 比较相似,我们将该其分成几个部分分析,首先是函数会根据传入的键拿到对应的哈希和桶:

1
2
3
4
5
6
7
8
9
10
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 和键的哈希,如果找到了相同结果就会获取目标位置的地址并返回,其中inserti 表示目标元素的在桶中的索引,insertk 和 val 分别表示键值对的地址,获得目标地址之后会直接通过算术计算进行寻址获得键值对kval

扩容

删除