简介

源码涉及编译时和运行时,过于复杂,以后了解

哈希表是一个无序的 key/value 对的集合,key 都是不同的,通过给定的 key 可以在常数时间复杂度内检索、更新或删除对应的 value

map 是一个哈希表的引用,map 的类型可以写成 map[key]value,所有的 key 都是相同的类型,所有的 value 都是相同的类型,key 必须是支持 == 运算的数据类型,不建议使用浮点数作为 key。

不支持 == 操作的类型有: slicemapfunction 、包含不可比较类型的字段的结构体和任何元素类型为不可比较类型的数组,除此以外都支持 ==,例如: 布尔类型、整数类型、浮点类型、复数类型、指针类型、channel、struct、数组、interface、string

基本操作

map 中的元素并不是一个变量,因此不能对 map 的元素进行取址操作

_ = &ages["bob"] // compile error: cannot take address of map element

禁止对 map 元素取址的原因是 map 可能随着元素数量的增长而重新分配更大的内存空间,从而导致之前的地址无效

  • 使用内置的 make 函数创建 map 结构

通过 make 创建时可以指定容量

c := make(map[string]int)
c := make(map[string]int, 100)
  • 用 map 字面值的语法创建 map,可以在创建的时候指定初始的 key/value
b := map[string]int{
    "haozibi": 1,
    "tom":     2,
}
  • 使用 map 字面值创建空的 map 结构
d := map[string]int{}
  • 添加和访问

向 map 存数据前必须先创建 map

// https://play.golang.org/p/IXm8nL2zCVT
func main() {
	a := make(map[string]int)

	a["tom"] = 1

	// 可以返回两个值,第二值为布尔类型,用于报告元素是否真的存在
	b, ok := a["bob"]
	fmt.Println(b, ok)

	fmt.Println("tom", a["tom"])
	fmt.Println("bob:", a["bob"])

	a["bob"] = a["bob"] + 1

	b, ok = a["bob"]
	fmt.Println(b, ok)

	fmt.Println("bob:", a["bob"])
}

// output:
// 0 false
// tom 1
// bob: 0
// 1 true
// bob: 1

即使元素不在 map 中也没有关系,如果查找失败将返回 value 类型对应的零值

  • 删除元素
a := make(map[string]int)
a["tom"] = 1
delete(a, "tom")
  • 遍历 map

使用 range 遍历 map 中全部的 key/value,迭代顺序是随机的(有意而为之)

func main() {
	a := make(map[string]int)

	a["alice"] = 1
	a["bob"] = 2
	a["tom"] = 3

	for k, v := range a {
		fmt.Println(k, v)
	}
}

如果需要按顺序遍历 key/value 对,必须显式对 key 进行排序

// https://play.golang.org/p/KIjUERxQIEK
func main() {
	ages := make(map[string]int)

	ages["alice"] = 1
	ages["bob"] = 2
	ages["tom"] = 3

	var names []string

	for v := range ages {
		names = append(names, v)
	}

	sort.Strings(names)

	for _, name := range names {
		fmt.Println(name, ages[name])
	}
}

哈希表

  • 散列函数: 若关键字为 k,则其值存放在 f(k) 的存储位置上,不需要比较便可直接取得所查记录,称对应关系 f 为散列函数。
  • 冲突: 如果不同关键字得到同一散列地址,即 k1 != k2 但是 f(k1) == f(k2)
  • 散列表(哈希表): 根据散列函数 f(k) 和处理冲突的方法将一组关键字映射到一个有限的连续的地址集(区间)上,并以关键字在地址集中的“像”作为记录在表中的存储位置,这种表即为散列表。映射过程称为散列造表或散列,所得到的存储位置称散列地址
  • 均匀散列函数: 若对于关键字集合中的任一关键字,经散列函数映射到地址集合中任何一个地址的概率是相等,这样使关键字经过散列函数等到一个“随机地址”,从而减少冲突

哈希表的实现关键在于选择哈希函数,哈希函数的选择能够决定哈希表的读写性能。理想情况下哈希函数可以将不同键映射到唯一的索引上,比较实际的方式是让哈希函数的结果能够均匀分布,不均匀的分布会造成更多的冲突并且带来更差的性能,使用结果均匀的哈希函数,哈希的增删改查都需要 O(1) 的时间复杂度,不均匀会导致操作最差 O(n) 的时间复杂度。

为了解决哈希的碰撞问题,常见解决方式为“开放寻址法”和“拉链法”

开放寻址法

开放寻址法是一种在哈希表中解决哈希碰撞的方法,核心思想为:在一维数组对元素进行探测和比较以判断待查找的*目标键*是否存在于当前的哈希表中。在初始化哈希表时就会创建一个新的数组,如果我们向当前哈希表写入数据发生冲突,就会将键值对写入到下一个不为空的位置。

橙色方块表示已有数据,黄色方块表示空闲

x 经过哈希函数计算落在标号 7 的位置,但是 7 的位置已经存在数据,则 x 尝试写在 7 后面的位置即 8 号位,如果可写入则直接写入,如果不可以写入则继续尝试写入 8 号位后面的位置即 9 号位,直至可以写入

例如:

  • 写: key3 与已经存入哈希表中的两个键 key1、key2 发生冲突,key3 会被自动写入到 key2 后面的空闲内存上
  • 读: 读取 key3,先对键进行哈希并索引到 key1 上,对比目标键与 key1 不匹配就会读取后面的元素,知道内存为空或者找到目标元素

开放寻址法对性能影响最大的就是装载因子,它是数组中元素数量与数组大小的比值,装载因子越大,说明空闲位置越少,冲突越多,散列表的性能会下降。随着装载因子的增加,线性探测的平均用时就会逐渐增加,这就会影响哈希表的查找和插入性能,如果装载因子超过 0.7,哈希表的性能就会急剧下降,而一旦装载因子达到 1,整个哈希表就完全失效

拉链法

拉链法是哈希表中最常见的实现方式,相对比较简单,平均查找的长度也短,存储节点的内存都是动态申请的。实际就是数组加上链表组合起来实现哈希表,数组中每一个元素其实都是一个链表

  • 写: 增加一对键值对,键值对中的键会经过哈希函数,返回的哈希决定去的的桶位置,然后遍历这个桶中持有的链表,如果存在相同键则更新值,如果不存在键则在链表末尾追加一对新的键值对
  • 读: 和写入操作一致

查找时间收到链表长度的影响,如果链表很长,实际上查找效率也不高。可以把链表变成红黑树

源码

以 Go tag 1.13 为例

源码位置: /src/runtime/map.go

map 使用哈希表作为底层实现,哈希表通过“拉链法”处理冲突,一个哈希表里可以有多个哈希表节点即 bucket(相当于拉链法中的链表),而每个 bucket 就保存了 map 中的一个或一组 key/value

map 结构定义如下

// https://github.com/golang/go/blob/6bbfea923e5b1450cba7b2082ba2e73b85ab82cc/src/runtime/map.go#L113
type hmap struct {
	count     int
	flags     uint8
	B         uint8
	noverflow uint16
	hash0     uint32

	buckets    unsafe.Pointer
	oldbuckets unsafe.Pointer
	nevacuate  uintptr

	extra *mapextra
}
  • count: 当前哈希表元素的数量,即 len() 返回的值,
  • B: 当前哈希表持有的 bucket 数量,因为哈希表扩容是以 2 的倍数进行的,所以这里使用对数存储,可以理解为 Count(bucket) == 2^B
  • hash0: 哈希种子,当调用哈希函数时作为参数传进去,为哈希函数引入一定的随机性
  • buckets: bucket 数组指针,数组大小为 2^B
  • oldbuckets: 哈希在扩容的时候保存之前 bucket 的字段,大小为当前 bucket 的一半

如图为拥有 4 个 bucket 的 map,其中 B 为 2,而 bucket 的长度为 2^B 为 4,元素会经过运算会落在其中某个 bucket 中

bucket 的数据结构

// Maximum number of key/value pairs a bucket can hold.
bucketCntBits = 3
bucketCnt     = 1 << bucketCntBits // 0b1000 => 8

// https://github.com/golang/go/blob/61a5d114c2ede53b78bd0b02f95f7d5130526ac0/src/runtime/map.go#L147
type bmap struct {
	tophash [bucketCnt]uint8
}

哈希表的类型其实都存储在每一个桶中,tophash 字段包含此存储桶每个键的高位哈希值。bmap 还有一些隐藏结构,是在编译期间“动态”创建的。由于键值类型的不同占用空间大小也不同,导致类型和占用内存不确定,所以没有办法在 Go 源代码中进行声明

可以把 bmap 抽象为

type bmap struct {
    tophash [8]uint8 // 存储哈希值的高8位
    data    byte[1]  // key value数据:key/key/key/.../value/value/value...
    overflow *bmap   // 溢出bucket的地址
}
  • tophash: 长度为 8 的数组,哈希值相同的键(准确说是哈希值低位相同的键)存入当前 bucket 时会将哈希值的高位存储在该数组中,用于之后的匹配
  • data: 存放的是 key/value 数据,存放顺序是 key/key/key/key/value/value/value/value,是为了节省字节对齐带来的空间浪费
  • overflow: 指向向下一个 bucket,把冲突的键连接起来

这里的 bucket 就是”拉链法“里的链表,只是把链表做了聚合,每 8 个组合成一个 bucket

负载因子 = 键数量/bucket 数量

  • 负载因子过小,说明空间利用率低
  • 负载因子过大,说明冲突严重,存取效率低

哈希表需要将负载因子控制在合适的大小,超过其阀值需要进行 rehash,不同哈希表的实现对负载因子容忍程度不同,Go 在负载因子达到 6.5 时才会触发 rehash。

扩容

当新元素增加到 map 时,都会检查是否需要扩容,以空间换时间,触发扩容的条件

  • 负载因子 > 6.5 时,平均每个 bucket 存储的键值对达到 6.5 个
  • overflow 数量 > 2^15 即 overflow 数量达到了 32768 时

常用的扩容方法

  • 增量搬迁: 当负载因子过大时,就新建一个 bucket,新的 bucket 长度(即链表的长度)是原来的 2 倍,然后将 bucket 数据搬迁到新的 bucket,采用逐步搬迁策略,即每次访问 map 时都会触发一次搬迁,每次搬迁 2 个键值对,避免 map 存储过多 key/value 一次搬迁会造成比较大的延时
  • 等量扩容: bucket 数量不变,重新做一次类似增量扩容的搬迁工作,把松散的键值对重新排列一次,使 bucket 使用效率变高。在极端情况下,键值对正好集中在以下部分的 bucket,会造成 overflow 的 bucket 数量增多,但负载因子又不高,从而无法执行增量搬迁。

参考链接