编程语言go语言重难点
Source
Edit
History

undefined

哈希表

两个关键点：哈希函数和哈希冲突。解决哈希冲突的常见方法有开放寻址法、拉链法

1. 开发寻址法

底层数据结构是数组，依次探测和比较数组中的元素以判断目标键值对是否存在于哈希表中；如果发生冲突，就会将键值对写入写一个索引不为空的位置。

装载因子：数组中元素数量与数组大小的比值。当装载率超过 70% 之后，哈希表的性能就会急剧下降，而一旦装载率达到 100%，整个哈希表就会完全失效。

2. 拉链法

数组+链表。如果发生冲突，则在链表末尾追加新的键值对即可。

装载因子：元素数量 / 桶数量。一般情况下，使用拉链法的哈希表装载因子不会超过 1。当哈希表的装载因子较大时会触发哈希表扩容，创建更多桶来存储哈希表中的元素。

一、底层结构

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
// A header for a Go map.
type hmap struct {
	// Note: the format of the hmap is also encoded in cmd/compile/internal/gc/reflect.go.
	// Make sure this stays in sync with the compiler's definition.
	count     int // # live cells == size of map.  Must be first (used by len() builtin)
	flags     uint8
	B         uint8  // log_2 of # of buckets (can hold up to loadFactor * 2^B items)
	noverflow uint16 // approximate number of overflow buckets; see incrnoverflow for details
	hash0     uint32 // hash seed

	buckets    unsafe.Pointer // array of 2^B Buckets. may be nil if count==0.
	oldbuckets unsafe.Pointer // previous bucket array of half the size, non-nil only when growing
	nevacuate  uintptr        // progress counter for evacuation (buckets less than this have been evacuated)

	extra *mapextra // optional fields
}

type mapextra struct {
	overflow    *[]*bmap
	oldoverflow *[]*bmap
	nextOverflow *bmap
}
  • count 表示当前哈希表中的元素数量
  • B 表示当前哈希表持有的 buckets 数量。因为哈希表中桶的数量都是 2 的倍数，所以该字段会存储对数，即 len(buckets) == 2^B
  • hash0 时哈希表的种子，他能为哈希函数的结果引入随机性，这个值在创建哈希表时确定，并在调用哈希函数时作为参数传入
  • buckets 是指针，指向 []bmap 结构，每个 bmap 可以存储 8 个键值对。
  • oldbuckets 是哈希表在扩容时用于保存之前 buckets 的字段，它的大小是当前 buckets 的一半
  • noverflow 是溢出桶的计数
s
  • extra.nextOverflow 表示溢出桶，当哈希表中存储的数据过多，单个桶已经装满时会存储溢出的数据（图中有误，应该是 nextOverflow 指向蓝色的溢出桶）
  • buckets 指向的正常桶和 extra.nextOverflow 指向的溢出桶在内存汇中是连续的

如上，黄色的 runtime.bmap 是正常桶，绿色的 runtime.bmap 是溢出桶。这两种桶在内存中是连续的

1
2
3
type bmap struct {
	tophash [bucketCnt]uint8  
}

如上是编译期间的 bamp，tophash 字段存储了键的哈希的高 8 位，通过比较不同键的哈希的高 8 位可以减少访问键值对次数以提高性能。

在运行期间，运行时会重建 bmap 结构，如下：

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

总结，Go 语言的 map 底层主要是由 bmap 数组构成，而 bmap 结构是一个结构体，这个结构体中会最多存储 8 个键值对。溢出的元素存储在 extra.nextOverflow 的 bmap 结构中。随着哈希表存储的数据逐渐增多，会对哈希表扩容或者使用额外的桶存储溢出的数据，不会让单个桶中的数据超过 8 个。其中溢出桶也只是临时方案，创建过多溢出桶最终也会导致哈希表扩容。

二、访问

1
2
v := hash[key] 
v, ok := hash[key]

访问一个 map 时，有如上两种操作。

  • 会先通过哈希表设置的哈希函数、种子获取当前键对应的哈希，再拿到该键值对所在的桶序号和哈希的高8位数字。
  • 接下来会依次遍历正常桶和溢出桶中的数据，先比较哈希的高 8 位和桶中存储的 tophash，后比较传入的值和桶中的值以加速数据的读写。用于选择桶序号的是哈希的最低几位，而用于加速访问的是哈希的高 8 位，这种设计能够降低同一个桶中有大量相等 tophash 的概率以免影响性能。
  • 每一个桶都是一整块内存空间，当发现桶中的 tophash 与传入键的 tophash 匹配之后，我们会通过指针和偏移量获取哈希表中存储的键 keys[0] 并与 key 比较，如果两者相同，就会获取目标值的指针 values[0] 并返回。
  • 哈希表可能会在装载因子过高或者溢出桶过多时进行扩容。哈希表扩容并不是原子操作，在扩容时谈访问操作

三、写入

  • 首先会根据传入的键拿到对应的哈希和桶
  • 然后通过遍历比较桶中存储的 tophash 和键的哈希。如果找到了相同结果，就会返回目标位置的地址。获得目标地址后会通过算术计算寻址获得键值对 k 和 val 。这个过程会依次遍历正常桶和溢出桶中存储的数据，整个过程会分别判断 tophash 是否相等、key 是否相等。
  • 如果当前桶已满，哈希表会创建新桶或者使用 hmap 预先在 noverflow 中创建好的桶来保存数据，新创建的桶不仅会追加到已有桶的末尾，还会增加哈希表的 noverflow 计数。
  • 如果当前键值对在哈希表中不存在，哈希表会为新键值对规划存储的内存地址，通过 runtime.typedmemmove 将键移动到对应的内存空间中，并返回键对应值的地址。如果当前键值在哈希表中存在，就会直接返回目标区域的内存地址。拿到地址后将值插入即可

四、扩容

触发扩容哈希表扩容的情况：

  • 装载因子超过 6.5
  • 哈希表使用了太多溢出桶

哈希表在存储元素过多时会触发扩容操作，每次都会将桶的数量翻倍，扩容过程不是原子的，而是通过运行时增量触发的。在扩容期间访问哈希表时会使用旧桶，向哈希表写入数据时会触发旧桶元素的分流，也就是会分流到新创建的桶中。

除这种正常的扩容外，为了解决大量写入、删除造成的内存泄露问题（当我们持续向哈希中插入数据并将他们全部删除时，如果哈希表中的数据量没有超过阈值，就会不断积累溢出桶造成缓慢的内存泄露），哈希表会在出现较多溢出桶时整理哈希表的内存来减少空间占用（复用已有的哈希扩容解决该问题，一旦哈希中出现了过多溢出桶，他会创建新桶保存数据，垃圾回收后清理老的溢出桶并释放内存）。