Golang

8.map

[toc]

map

1. 基础知识

1.1. 声明方式

区分: 数组定义了长度, 就会自动初始化, map make 时定义了长度, 也是 0

无论 map 是否初始化, 都可以使用 len 进行判断长度

仅仅声明一个 map , 没有初始化, 是 nil map , 不能使用

1
2
3
4
5
6
7

m := map[string]string{
		"name":"ccmouse",
		"course":"golang",
	}

m2 := make(map[string]int) // m2 == {}  即  len(m2) == 0
var m3 map[string]int   // m3 == nil  也可以  len(m3) == 0

注意不能对 map 中的元素进行取址 , map的key必须是可比较的类型

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

1

_ = &ages["bob"] // ❌

不能直接更新 map 中 struct 的元素字段值，注意 : array 和 slice 是可以的直接更新的。

1

m["x"].name = "Jerry" // ❌

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

type data struct {
	name string
}

func TestData(t *testing.T) {
	m := map[string]data{
		"x": {"Tom"},
	}
	r := m["x"]
	r.name = "Jerry"
	m["x"] = r
	fmt.Println(m)
}

1.2. 遍历数据

Map的迭代顺序是不确定的, 在实践中，遍历的顺序是随机的，每一次遍历的顺序都不相同。这是故意的，每次都使用随机的遍历顺序可以强制要求程序不会依赖具体的哈希函数实现。如果要按顺序遍历key/value对，我们必须显式地对key进行排序，可以使用sort包的Strings函数对字符串slice进行排序。

1
2
3
4
5

m1 := map[string]string{"1":"2"}

for k,v:=range m1 {
  t.Log(k," >>> ",v)
}

如果想要排序, 可以对 key 排序

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

import "sort"

var names []string
for name := range ages {
    names = append(names, name)
}
sort.Strings(names)
for _, name := range names {
    fmt.Printf("%s\t%d\n", name, ages[name])
}

因为我们一开始就知道names的最终大小，因此给slice分配一个合适的大小将会更有效。会避免 append 时浪费内存

1

names := make([]string, 0, len(ages))

1.3. map 为 nil 做操作

map上的大部分操作，包括查找、删除、len和range循环都可以安全工作在nil值的map上，它们的行为和一个空的map类似。但是向一个nil值的map存入元素将导致一个panic异常 , 在向map存数据前必须先创建map, 即分配内存空间。

访问不存在的 key

1
2

m1 := map[int]int{}  // 空 map
t.Log(m1[1])   // 访问不存在的 key

返回的结果是零值 , 当访问的 key 不存在, 会返回 value 对应类型的零值

如果 value 类型是 int, 赋值后是 0 值, 不存在时 也是 0 值, 如何判断?

key 存在, 则 ok 为 ture, 不存在 false

1
2
3

if value, ok:=m1[3]; ok {
		t.Logf( " key 3 is  = %d",value)
}

和slice一样，map之间也不能进行相等比较；唯一的例外是和nil进行比较。

删除某个 key

使用 delete , 传入 map 和 key 参数

1
2

m1 := map[int]int{1:1,2:4,3:9,4:16}
delete(m1,1)

map 的 key

  1. map 使用哈希表, 必须 key 比较相等

  2. 除了 slice, map, function 的内建类型都可以作为 key

    如果想用 slice, 可以定义一个函数获取 slice 的字符串 , 作为 map 的 key

  3. struct 类型不包含以上字段(slice,map), 也可以作为 key

作为函数参数

传递时拷贝地址, 所以有传引用的效果

set

内置集合没有 set 实现, 可以使用 map[type]bool

1

set := map[string]bool

2. 使用案例

2.1. 寻找最长不含有重复字符的子串

front 指针从 0 开始, 如果没有遇到重复的字符, 就停止移动, 遍历后面的字符, 通过 当前长度-front 获取最长子串

如果当前遍历的字符在 front 后面出现过, front 就移动到上一次出现位置+1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

func TestSelectLongOfNotRepeatingSubStr(t *testing.T)  {
	str := "abcabcdabacd"

	m1 := make(map[rune]int,len(str))
	front :=0  // 头指针
	maxLen :=0 // 最大子串长度

	for i,ch := range []rune(str) {
	  // 如果当前字符在 front 后面出现过一次
    if back,ok := m1[ch]; ok && back >= front {
      // 增加 front 位置, 当前遍历到的字符后一个位置
			front = back +1
		}
		maxLen = i-front+1
    // 更新位置
		m1[ch] = i
	}

	t.Log(maxLen)
}

3. 注意

4. 了解源码

结构体

runtime/map.go/hmap

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

type hmap struct{
  	count int  // 键值对数量
  	flags uint8
  	B			uint8	// 桶的数目是 2 的多少次幂
  	noverflow uint8
  	hash0  uint32
  
  	buckets unsafe.Pointer // 桶在哪里
  	oldbuckets unsafe.Pointer // 用于扩容阶段保存旧桶在哪儿
  	nevacuate uintptr  // 即将迁移的旧桶编号
  	extra *mapextra
}

Golang的map使用哈希表作为底层实现，一个哈希表里可以有多个哈希表节点，也即bucket，而每个bucket就保存了map中的一个或一组键值对。

下图展示一个拥有4个bucket的map：

bucket数据结构

1
2
3
4
5

type bmap struct {
    tophash [8]uint8 //存储哈希值的高8位
    data    byte[1]  //key value数据:key/key/key/.../value/value/value...
    overflow *bmap   //溢出bucket的地址
}

每个bucket可以存储8个键值对。

  • tophash是个长度为8的数组，哈希值相同的键（准确的说是哈希值低位相同的键）存入当前bucket时会将哈希值的高位存储在该数组中，以方便后续匹配。
  • data区存放的是key-value数据，存放顺序是key/key/key/…value/value/value，如此存放是为了节省字节对齐带来的空间浪费。
  • overflow 指针指向的是下一个bucket，据此将所有冲突的键连接起来。

下图展示bucket存放8个key-value对：

哈希冲突

当有两个或以上数量的键被哈希到了同一个bucket时，我们称这些键发生了冲突。Go使用链地址法来解决键冲突。由于每个bucket可以存放8个键值对，所以同一个bucket存放超过8个键值对时就会再创建一个键值对，用类似链表的方式将bucket连接起来。

下图展示产生冲突后的map：

bucket数据结构指示下一个bucket的指针称为overflow bucket，意为当前bucket盛不下而溢出的部分。事实上哈希冲突并不是好事情，它降低了存取效率，好的哈希算法可以保证哈希值的随机性，但冲突过多也是要控制的，后面会再详细介绍。

负载因子

负载因子用于衡量一个哈希表冲突情况，公式为：

1

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

哈希表需要将负载因子控制在合适的大小，超过其阀值需要进行rehash，也即键值对重新组织：

  • 哈希因子过小，说明空间利用率低
  • 哈希因子过大，说明冲突严重，存取效率低

每个哈希表的实现对负载因子容忍程度不同，比如Redis实现中负载因子大于1时就会触发rehash，而Go则在在负载因子达到6.5时才会触发rehash，因为Redis的每个bucket只能存1个键值对，而Go的bucket可能存8个键值对，所以Go可以容忍更高的负载因子。

渐进式扩容

为了保证访问效率，当新元素将要添加进map时，都会检查是否需要扩容，扩容实际上是以空间换时间的手段。触发扩容的条件有二个：

  1. 负载因子 > 6.5时，也即平均每个bucket存储的键值对达到6.5个。
  2. overflow数量 > 2^15时，也即overflow数量超过32768时。

增量扩容

当负载因子过大时，就新建一个bucket，新的bucket长度是原来的2倍，然后旧bucket数据搬迁到新的bucket。考虑到如果map存储了数以亿计的key-value，一次性搬迁将会造成比较大的延时，Go采用逐步搬迁策略，即每次访问map时都会触发一次搬迁，每次搬迁2个键值对。

下图展示了包含一个bucket满载的map(为了描述方便，图中bucket省略了value区域):

当前map存储了7个键值对，只有1个bucket。此地负载因子为7。再次插入数据时将会触发扩容操作，扩容之后再将新插入键写入新的bucket。

当第8个键值对插入时，将会触发扩容，扩容后示意图如下：

hmap数据结构中oldbuckets成员指身原bucket，而buckets指向了新申请的bucket。新的键值对被插入新的bucket中。后续对map的访问操作会触发迁移，将oldbuckets中的键值对逐步的搬迁过来。当oldbuckets中的键值对全部搬迁完毕后，删除oldbuckets。

搬迁完成后的示意图如下：

数据搬迁过程中原bucket中的键值对将存在于新bucket的前面，新插入的键值对将存在于新bucket的后面。实际搬迁过程中比较复杂，将在后续源码分析中详细介绍。

等量扩容

所谓等量扩容，实际上并不是扩大容量，buckets数量不变，重新做一遍类似增量扩容的搬迁动作，把松散的键值对重新排列一次，以使bucket的使用率更高，进而保证更快的存取。在极端场景下，比如不断的增删，而键值对正好集中在一小部分的bucket，这样会造成overflow的bucket数量增多，但负载因子又不高，从而无法执行增量搬迁的情况，如下图所示：

1.3 map - 图7

上图可见，overflow的buckt中大部分是空的，访问效率会很差。此时进行一次等量扩容，即buckets数量不变，经过重新组织后overflow的bucket数量会减少，即节省了空间又会提高访问效率。

查找过程

查找过程如下：

  1. 跟据key值算出哈希值
  2. 取哈希值低位与hmpa.B取模确定bucket位置
  3. 取哈希值高位在tophash数组中查询
  4. 如果tophash[i]中存储值也哈希值相等，则去找到该bucket中的key值进行比较
  5. 当前bucket没有找到，则继续从下个overflow的bucket中查找。
  6. 如果当前处于搬迁过程，则优先从oldbuckets查找

注：如果查找不到，也不会返回空值，而是返回相应类型的0值。

插入过程

新员素插入过程如下：

  1. 跟据key值算出哈希值
  2. 取哈希值低位与hmap.B取模确定bucket位置
  3. 查找该key是否已经存在，如果存在则直接更新值
  4. 如果没找到将key，将key插入
Go
Licensed under CC BY-NC-SA 4.0
© 2018 - 2024 ixugo
本文阅读量 次， 总访问量 次 ，总访客数 人
Built with Hugo .   Theme Stack designed by Jimmy