当前位置：首页 > article >正文

09 go语言（golang） - 数据类型：哈希表（map）及原理(一)

article 2024/11/1 10:20:36

哈希表（map）

在Go语言中，map 是一种内置的数据结构，用于存储键值对。它类似于其他语言中的字典或哈希表。

特性

键值对存储：
- map 使用哈希表实现，可以通过键快速查找对应的值。
动态大小：
- 可以根据需要动态增加或删除元素。
键的类型要求：
- 键必须是可比较的类型，如字符串、数字等，不能使用切片、函数等不可比较类型作为键。

创建和初始化

使用 make 函数创建
使用字面量创建并初始化

func Test1(t *testing.T) {
	map1 := map[string]int{"a": 1}
	map2 := make(map[int]string)    // 默认容量为16，不像数组，不用太关注容量，只管高效的使用map即可
	map3 := make(map[int]string, 2) // 初始化容量为2

	fmt.Println(map1)
	fmt.Println(map2)
	fmt.Println(map3)
}

操作

添加和更新元素、删除元素

func Test3(t *testing.T) {
	map1 := map[int]string{1: "x", 2: "y"}
	fmt.Println(map1)

	// 更新键值对
	map1[1] = "xxx"
	fmt.Println(map1)
	// 插入新键值对
	map1[3] = "z"
	fmt.Println(map1)
	// 删除键值对
	delete(map1, 2)
	fmt.Println(map1)
}

输出：

map[1:x 2:y]
map[1:xxx 2:y]
map[1:xxx 2:y 3:z]
map[1:xxx 3:z]

访问元素并检查存在性：

/*
获取键值对
*/
func Test2(t *testing.T) {
	var map1 map[string]int = map[string]int{"a": 1}

	fmt.Println(map1)

	fmt.Println(map1["a"])
	fmt.Println(map1["b"])    // 不存在的键值对，返回类型零值
	value, exist := map1["b"] // 获取键值对，第二个返回值表示键值对是否存在
	if exist {
		println(value)
	} else {
		fmt.Println("b键不存在！")
	}
}

遍历 map

func Test4(t *testing.T) {
	// key 为 int
	// value 为 string 切片
	map1 := map[int][]string{1: {"x", "x"}, 2: {"y", "y"}}

	for key := range map1 {
		fmt.Println(key)
	}

	for key, value := range map1 {
		fmt.Println(key, value)
	}
}

获取长度
```
func Test5(t *testing.T) {
	map1 := map[string]int{"a": 1}
	fmt.Println(len(map1))
}
```
map 并不像切片那样直接提供容量（capacity）的概念和相关函数。对于 map，我们只能获取当前存储的键值对数量，而无法直接查看或控制其底层容量。

注意事项

如果访问一个不存在的键，返回该类型的零值。
遍历时，顺序不固定，每次可能不同。
并发读写不安全，需要同步机制（如 sync.RWMutex）保护。

只声明的情况下，无法插入值，会报错：assignment to entry in nil map

func Test6(t *testing.T) {
	// 只声明，为nil
	var map1 map[string]int
	println(map1)

	map1["x"] = 1 // 为nil插入一个值 ,会报错
	fmt.Println(map1)
}

底层原理

Go语言中的 map 是通过哈希表实现的。

基本组成（简单）

哈希表：
- map 使用哈希表来存储键值对，通过计算键的哈希值来确定存储位置。
桶（bucket）：
- 哈希表由多个桶组成，每个桶可以容纳多个键值对。
- 每个桶有一个固定大小，通常为8个元素。
溢出桶（overflow bucket）：
- 当一个桶被填满时，会创建溢出桶来存放更多元素。
- 溢出链可能会影响性能，因为需要遍历链条查找元素。

基本组成（详细）

源码位置在：src/runtime/map.go

hmap结构体（哈希表）：

hmap 是 Go 中表示一个 map 的主要数据结构。
它包含了关于整个哈希表的信息，如桶数组、元素数量等。
hmap 结构的一些关键字段
- count：当前 map 中的键值对数量。
- B：用于计算bucket索引的shift值，len(buckets) = 2^B。
- buckets：指向第一个 bucket 数组的指针。
- oldbuckets：用于渐进式扩容时保存旧的 bucket 数组。
- nevacuate：记录已经迁移到新 buckets 的旧 buckets 数量，用于渐进式扩容控制。

// A header for a Go map.
type hmap struct {
	// Note: the format of the hmap is also encoded in cmd/compile/internal/reflectdata/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
}

bucket（桶，即 bmap）：
- 哈希表由多个桶（bucket）组成，每个桶可以容纳多个键值对。
- 每个桶有一个固定大小（通常为8个键值对），这有助于减少内存碎片并提高缓存命中率。
- 每个 bucket 包含
  - tophash：用于存储每个键对应哈希值的一部分。这个数组帮助快速判断某个位置是否可能包含目标键。
  - 键和值存储：
    - 键和值以紧凑形式存储在 bucket 中。
    - 每个 bucket 可以容纳多个键值对（通常为8），这有助于减少内存碎片并提高缓存命中率。
  - 溢出指针（overflow）：
    - 当一个 bucket 被填满时，会使用溢出指针链接到下一个溢出 bucket。
    - 溢出链条用于处理哈希冲突和高负载情况。
```
// A bucket for a Go map.
type bmap struct {
	// tophash generally contains the top byte of the hash value
	// for each key in this bucket. If tophash[0] < minTopHash,
	// tophash[0] is a bucket evacuation state instead.
	tophash [abi.MapBucketCount]uint8
	// Followed by bucketCnt keys and then bucketCnt elems.
	// NOTE: packing all the keys together and then all the elems together makes the
	// code a bit more complicated than alternating key/elem/key/elem/... but it allows
	// us to eliminate padding which would be needed for, e.g., map[int64]int8.
	// Followed by an overflow pointer.
}
```
注意：bmap 的确有一个结构体定义，但它只是包含了 tophash。键和值数组以及溢出指针（overflow）并没有直接在这个结构体中定义，而是通过内存布局和编译器生成的代码来实现。
溢出桶 (Overflow Buckets)

当某个 bucket 因为碰撞过多而填满时，并且无法通过再散列来解决时，会使用溢出桶来存储额外的元素。这些溢出桶被动态地添加到相应基本 bucket 上以处理冲突。

初始化过程

当我们使用 make(map[string]string, 10) 来初始化一个 map 时，底层进行了一系列操作以配置和优化这个数据结构的性能。

第一步：创建一个 hmap 结构体对象

第二步：生成一个哈希因子 hash0 并赋值到 hmap 对象中

hash0 是用于生成 key 哈希值的随机种子。这个种子在 map 的整个生命周期内保持不变，并用于确保 hash 函数能够将键均匀分布在各个桶中，减少碰撞。

第三步：根据 hint=10 创建 B

这里 B 表示 buckets 数组中 bucket 的位数。如果 hint 为 10，则选择最小的 B 使得 $2^B \geq hint$ 。因此，则 $B = 4$ 因为 $2^4 = 16$ 是大于或等于10且最接近10的2次幂数。

第四步：创建 buckets 和 bmaps

当 B < 4时, 桶数是 $2^B$ ，由于数据较少、使用溢出桶的可能性较低，会省略创建的过程以减少额外开销；
当 B >= 4时，会额外创建 $2^{(B-4)}$ 个溢出桶，所以桶数是 $2^B + 2^{(B-4)}$ 。

注意：每个bmap中可以存储8个键值对，当不够存储时需要使用溢出桶，并将当前bmap中的overflow字段指向溢出桶的位置。

插入或更新值过程

当执行 info["name"] = "xxx" 来为一个 map 赋值时，底层会进行一系列操作以确保键值对正确存储。

第一步：计算 Key 的哈希值

首先，使用预先存储在 hmap 结构体中的哈希因子 hash0 来计算 key "name" 的哈希值。这个过程通常涉及到一个或多个快速的哈希函数，目的是将字符串 "name" 转换成一个整数型的哈希码。

第二步：确定桶位置

使用计算出来的哈希码来确定该键应该放置在哪个桶（bucket）。这通常通过取哈希码与当前桶数量减一之间的位与操作（例如，如果有 16 个桶，则为 hash & (16-1)）来实现。这样可以保证得到一个介于 0 到桶总数-1 的索引。

第三步：检查键是否存在

遍历目标 bucket 中所有已经存在的条目（即遍历该 bucket 对应的 bmap），查看 "name" 这个 key 是否已经存在：

如果找到了相同的 key，则更新其对应 value 值为 "xxx".
如果没有找到，则进行下一步。

第四步：添加新键值对

如果在当前 bucket 中没有找到相同 key，则先检查此 bucket 是否还有空间添加新条目

如果有空间，则直接在此 bmap 中添加新条目。
如果没有空间（即此 bmap 已满），则需要处理溢出情况：
- 检查是否已经有溢出 bucket 存在。
  - 有则插入新条目
- 如果没有溢出 bucket 或者溢出 buckets 也已满，则创建一个新的溢出 bmap 并链接到当前链表上。
  - 在适当位置插入新条目。
hmap的个数count++（map中的元素个数+1）