go Map
# 定义
存储一个 KV 模式的数据类型
map[K]V
map[K1]map[K2]V
1
2
2
案例:
m := map[string]string {
"name": "wujie",
"course": "golang",
"site": "wjstar",
"quality": "notbad",
}
m2 := make(map[string]int) // empty map
var m3 map[string]int // nil
fmt.Println(m, m2, m3)
1
2
3
4
5
6
7
8
9
10
11
12
2
3
4
5
6
7
8
9
10
11
12
map[course:golang name:wujie quality:notbad site:wjstar] map[] map[]
1
# 遍历操作
func map1() {
m := map[string]string {
"name": "wujie",
"course": "golang",
"site": "wjstar",
"quality": "notbad",
}
fmt.Println("Traversing map")
for k, v := range m {
fmt.Println(k, v)
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
2
3
4
5
6
7
8
9
10
11
12
13
14
Traversing map
name wujie
course golang
site wjstar
quality notbad
1
2
3
4
5
6
2
3
4
5
6
这里的k
也可以使用_
进行省略
for _, v := range m {
fmt.Println(v)
}
1
2
3
2
3
几次运行下来,可以发现一个问题:
有时候键”name“是在前面的,有时候键”quality“是在前面的。
这说明了一个这个k
在map
里是无序的,而且底层是HashMap
# 获取 map 的值
func map1() {
m := map[string]string {
"name": "wujie",
"course": "golang",
"site": "wjstar",
"quality": "notbad",
}
fmt.Println("Getting value")
// 存在的key
courseName := m["course"]
fmt.Println(courseName)
// 不存在的key
causeName := m["cause"]
fmt.Println(causeName)
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
这里我们测试了一个不存在的k
去获取值,此时会得到一个空的字符串,虽然在控制台打印看不出啥,但是正符合了go
语言定义的一个总归会有一个Zero value
提供使用。
但是我们如何进行判断这个k
是否存在呢?
fmt.Println("Getting value")
courseName, ok := m["course"]
fmt.Println(courseName, ok)
if causeName, ok := m["cause"]; ok {
fmt.Println(causeName)
} else {
fmt.Println("key does not exist")
}
1
2
3
4
5
6
7
8
2
3
4
5
6
7
8
golang true
key does not exist
1
2
3
2
3
# 删除元素
fmt.Println("deleting values")
name, ok := m["name"]
fmt.Println(name, ok)
delete(m, "name")
name, ok = m["name"]
fmt.Println(name, ok)
1
2
3
4
5
6
7
8
2
3
4
5
6
7
8
wujie true
false
1
2
3
2
3
# Map 的 Key
map
使用了哈希表,必须可以比较相等- 除了
slice,map,function
的内奸类型都可以作为key
Struct
类型不包含上述字段,也可以作为key
,在编译的时候会进行检查
# 实例
寻找最长不含有重复字符的子串
从abcabcbb
-> abc
从bbbbb
-> b
从pwwkew
-> wke
思路步骤:
对于每一个字母x
lastOccurred[x]
不存在,或者< start
则无需操作lastOccurred[x] >= start
,则更新start
的位置- 更新
lastOccurred[x]
,更新maxLength
func lengthOfNnRepeatingSubStr(s string) int {
lastOccurred := make(map[byte]int)
start := 0
maxLength := 0
for i, ch := range []byte(s) {
// 避免ch为0的情况
lastI, ok := lastOccurred[ch]
if ok && lastI >= start {
// 更新 start
start = lastI + 1
}
if i-start+1 > maxLength {
maxLength = i - start + 1
}
lastOccurred[ch] = i
}
return maxLength
}
func map2() {
fmt.Println(lengthOfNnRepeatingSubStr("abcabcbb")) // 3
fmt.Println(lengthOfNnRepeatingSubStr("bbbbbbb")) // 1
fmt.Println(lengthOfNnRepeatingSubStr("pwwkew")) // 3
fmt.Println(lengthOfNnRepeatingSubStr("")) // 0
fmt.Println(lengthOfNnRepeatingSubStr("b")) // 1
fmt.Println(lengthOfNnRepeatingSubStr("abcdef")) // 6
}
func main() {
map2()
}
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
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
fmt.Println(lengthOfNnRepeatingSubStr("这里是中文"))
fmt.Println(lengthOfNnRepeatingSubStr("一二三二一"))
1
2
2
假如这里使用了中文,这里就不对了,因为这里是使用的byte
类型,必须转换为ascii
。
# 操作总结
- 创建:
make(map[string]int)
- 获取元素:
m[k]
key
不存在时,获得value
类型的初始值- 用
value, ok := m[key]
来判断是否存在key
- 使用
range
遍历key
或者遍历key value
对 - 遍历不保证顺序,如果需要顺序,需手动对
key
排序 - 使用
len
获得元素个数
# HashMap 的基本方案
- 开放寻址法
- 拉链法
# 开放寻址法
大致过程
- 首先有一个底层数组已经存了一部分的
KV
值 - 进来一个新的
a:A
键值 - 首先经过
Hash
,hash
的是k
,哈希成一个数据,然后对数组的长度取模,可以算出这个键要去数组的几号位 - 假如要去的目标的地址已经有人占用了,就向后去寻找目标的地址,如果向后的也被占了,就继续往后,遇到空闲的,就进行分配
读取也是差不多的一个流程,如果哈希再经过取模之后,从 1 号位开始往后找,直到找到为止。
# 拉链法
主要流程
- 同样的也会经过 hash 然后取模,找到位置
- 但是对于的位置并不直接放数据,每一个位置上都是存的指针,会额外放的一个像链表的东西
- 产生相同的 hash 的时候,就会在下面继续追加一个键值,这个就解决了
hash
碰撞的位置,纵向的往下拉一个链表
读取:
- 同样经过 hash 取模之后找到位置
- 然后找到对应的链表进行遍历即可获取到对应的数据
# Go 的 map
有一个map.go
文件里面有一个结构体:hmap
// 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
// 桶数量的2 的对数
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 用于计算k的哈希值的
// 桶 => 拉链法
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
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
bmap
代表了hmap
里面的桶的内容
// A bucket for a Go map.
type bmap struct {
tophash [bucketCnt]uint8 // key 的哈希值 8个哈希值
}
1
2
3
4
2
3
4
bucketCntBits = 3
bucketCnt = 1 << bucketCntBits // 8
1
2
2
# map 的初始化
# 使用 make 初始化
m := make(map[string]int, 10)
1
0x001c 00028 (/Users/wujie/GolangProjects/src/rpc-test/demo/demo4.go:6) PCDATA $1, ZR
0x001c 00028 (/Users/wujie/GolangProjects/src/rpc-test/demo/demo4.go:6) CALL runtime.makemap_small(SB)
0x0020 00032 (/Users/wujie/GolangProjects/src/rpc-test/demo/demo4.go:6) MOVD 8(RSP), R0
0x0024 00036 (/Users/wujie/GolangProjects/src/rpc-test/demo/demo4.go:7) STP (ZR, ZR), ""..autotmp_11-16(SP)
0x0028 00040 (/Users/wujie/GolangProjects/src/rpc-test/demo/demo4.go:7) MOVD $type.map[string]int(SB), R1
0x0030 00048 (/Users/wujie/GolangProjects/src/rpc-test/demo/demo4.go:7) MOVD R1, ""..autotmp_11-16(SP)
0x0034 00052 (/Users/wujie/GolangProjects/src/rpc-test/demo/demo4.go:7) MOVD R0, ""..autotmp_11-8(SP)
1
2
3
4
5
6
7
8
2
3
4
5
6
7
8
这里编译下来它调用了runtime.makemap_small
方法,如果是windows
可能是makemap
方法,我现在是mac m1
架构的
func makemap_small() *hmap {
h := new(hmap)
h.hash0 = fastrand()
return h
}
1
2
3
4
5
2
3
4
5
func 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
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
35
36
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
35
36
# 字面量初始化
- 元素少于 25 个时,转化为简单赋值
hash := map[string]int{
"1": 2,
"3": 4,
"5": 6,
}
1
2
3
4
5
2
3
4
5
编译的时候直接 给你改成下面的:
hash := make(map[string]int, 3)
hash["1"] = 2
hash["3"] = 4
hash["5"] = 6
1
2
3
4
2
3
4
- 元素多于 25 个时,转换为循环赋值
hash := map[string]int{
"1": 2,
"2": 2,
"3": 4,
...
"26": 26,
}
1
2
3
4
5
6
7
2
3
4
5
6
7
转化
hash := make(map[string]int, 26)
// 存放key的数组
vstatk := []string{"1", "2", "3", ..., "26"}
// 存放value的数组
vstatv := []int{1, 2, 3, ..., 26}
for i := 0; i < len(vstatk); i++ {
hash[vstatk[i]] = vstatv[i]
}
1
2
3
4
5
6
7
8
2
3
4
5
6
7
8
# 总结
- Go 语言使用了拉链法实现了
hashmap
- 每一个桶中存储键哈希的前 8 位
- 桶超出 8 个数据,就会存储到溢出桶中
编辑 (opens new window)
上次更新: 2022/05/19, 00:48:05