golang数据结构初探之字典map

Map

Go语言的map底层使用Hash表实现的

特性预览

操作方式

初始化

map分别支持字面量初始化和内置函数make()初始化

字面量初始化

func MapInit() {
	m := map[string]int{
		"apple":  1,
		"banana": 2,
	}
	for k, v := range m {
    fmt.Printf(" %s : %d \n", k, v)
	}
}

内置函数make()

func MapInit() {
	m := make(map[string]int, 10)
	m["apple"] = 1
	m["banana"] = 2
	
	for k, v := range m {
    fmt.Printf(" %s : %d \n", k, v)
	}
}

使用make()函数初始化时可以指定map的容量，指定容量可以有效的减少内存的分配次数，有利于提升性能。

增删改查

map的增删改查操作比较简单，如下：

func MapCurd() {
	m := make(map[string]int, 10)
	m["apple"] = 1      // add
	m["apple"] = 2      // update
	delete(m, "apple")  //delete
	v, ok := m["apple"] //查询
	if ok {
		fmt.Println(v)
	}
}

需要注意的是，在上面的update操作中，如果键"apple"不存在，则map会创建一个新的键值对并存储，等同于add操作。

删除元素使用内置函数delete()，delete()函数没有返回值，在map为nil或者指定键不存在的情况下，delete()也不会报错，相当于空操作。

在查询操作中，最多可以给两个变量赋值，第一个为值，第二个为bool类型的变量，用于指示是否存在指定的键，如果键不存在，则第一个变量为对应类型的零值。如果只指定一个变量，那么该变量仅表示该键对应的值，如果键不存在，同样该值表示的是对应类型的零值。

内置函数len()可以查询map的长度，该长度反应的是map中存储的键值对数量。

危险操作

并发读写

map操作不是原子的，这意味着多个协程同时操作map时有可能产生读写冲突，读写冲突会触发panic从而导致程序异常退出。

空map

未初始化的map值为nil，在向值为nil的map中添加元素时，会触发panic，在使用时需要额外注意。

值为nil的map，长度与为空的map一样，尽管操作值为nil的map没有意义，但是查询、删除操作不会报错。

小结

• 初始化map时推荐使用内置函数并指定初始化容量
• 修改键值对时，需要先查询是否存在，否则会创建新的键值对
• 查询键值对时，最好检查键值对是否存在，避免零值操作
• 避免并发读写map，如果需要并发读写，则可以使用额外的锁(互斥锁、读写锁)，也可以考虑使用标准库sync包中的sync.Map。

实现原理

数据结构

Go语言的map使用hash表作为底层实现，一个hash表中可以有多个bucket，而每个bucket保存了map中的一个或者多个键值对。

map的数据结构

map的数据结构由src/runtime/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/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
}

下图展示一个有4个bucket的map:

本例中，hmap.B=2，hmap.buckets 数组的长度是4（2的B次方），元素经过Hash运算后会落到某个bucket中进行存储。

bucket很多时候会被翻译成桶，所谓的hash桶实际上就是bucket。

bucket的数据结构

bucket的数据结构是由 src/runtime/map.go:bmap 定义：

// 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 [bucketCnt]uint8	//存储hash值的高8位
	// 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.
}

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

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

注意，bucket的数据结构中的data和overflow成员并没有显式的在结构体中声明，运行时在访问bucket时直接通过指针的偏移来访问这些虚拟成员。

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

Hash冲突

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

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

在bucket的数据结构中使用指针指向溢出的bucket，表示为当前bucket装不下而溢出的部分。事实上hash冲突并不是好事，因为降低了效率，好的hash算法可以保证hash值的随机性。但无论哪种hash算法，冲突是无法避免的，当冲突比较多的时候就需要选择一些方式来减少冲突。

负载因子

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

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

例如，对于一个bucket数量为4，包含4个键值对的hash表来说，这个hash表的负载因子为1。

负载因子过大或者过小都不好：

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

负载因子过小，可能是预分配的空间太大，也有可能是大部分元素被删除造成的。随着元素不断添加到map中，负载因子会逐渐升高。

当hash表的负载因子过大时，需要申请更多的bucket，并对所有的键值对重新组织。使其均分的分布到这些bucket中，这个过程称为rehash。

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

扩容

扩容条件

降低负载因子常用的手段是扩容，为了保证访问效率，当新元素要添加到map时，都会被检测是否需要扩容，扩容实际上是以空间换时间的手段。

触发扩容需要满足以下任一条件：

• 负载因子大于6.5时，即平均每个bucket存储的键值对达到6.5个以上
• overflow的数量大于2的15次方，即overflow的数量超过32768

增量扩容

当负载因子过大时，就新建一个bucket数组，新的bucket数组长度是原来的2倍，然后旧bucket数组中的数据搬迁到新的bucket数组中。

考虑到如果map存储了数以亿计的键值对，那么一次性搬迁会造成巨大的延时，所以Go采用了逐步搬迁策略，即每次访问map时都会触发一次搬迁，每次搬迁2个键值对。

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

当前map存储了7个键值对，只有一个bucket，根据公式 负载因子=键数量/bucket数量 得出此时负载因子为7。再次添加数据时因为超过了6.5的阈值会触发扩容操作，扩容之后再将新的键值对写入新的bucket中。

当添加第8个键值对时，将触发扩容，扩容后的示意图如下所示：

扩容时的处理非常巧妙，先是让hmap数据结构中的oldbuckets成员指向原buckets数组，然后申请新的buckets数组(长度为原来的两倍),并将数组指针保存到hmap数据结构的buckets成员中。这样子就完成了新老bucket数组的交接，后续的迁移工作将从oldbuckets数组中逐步搬迁到新的buckets数组中，等待oldbuckets搬迁完毕后，就可以安全释放oldbuckets数组了。

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

等量扩容

所谓等量扩容，并不是扩大容量，而是bucket的数量不变，重新再做一遍类似增量扩容的搬迁动作，把松散的键值对重新排列一次，以使bucket的使用率更高，进而保证更快的存取速度。

在极端的情况下，比如经过大量的元素增删后，键值对刚好集中在一小部分bucket中，这样子会造成溢出的bucket增多，但溢出的bucket中的key-value大部分都是空的，访问效率很差，此时会进行一次等量扩容，即bucket数量不变，经过重新组织后overflow的bucket数量会减少，这样子即减少空间又提高了访问效率。

增删改查

无论是元素的添加还是查询操作，都需要先根据键的hash值确定一个bucket，并查询该bucket中是否存在指定的键。

• 对于查询操作而言，查询到指定的键后获取值并返回，否则返回对应类型的零值
• 对于添加操作而言，查到指定的键意味着当前的添加操作实际上是更新操作，否则在bucket中查找一个空余位置并插入。

查找过程

查找过程简述如下：

• 根据key值计算hash值
• 取hash值低位为hmap.B取模来确定bucket的位置
• 取hash值高位，在tophash数组中查询
• 如果tophash[i]中存储的hash值与当前key的hash值相等，则获取tophash[i]的key值进行比较
• 当前bucket中没有找到，则依次从溢出的bucket中查找

如果当前map处于搬迁过程中，那么查找时优先从oldbuckets数组中查找，不再从新的buckets中查找。如果查不到，那么也不会返回nil，而是返回相应类型的零值。

添加过程

新元素添加过程简述如下：

• 根据key值算出hash值
• 取hash值低位与hmap.B取模来确定bucket的位置
• 查找该key是否已经存在，如果存在则直接更新值
• 如果该key不存在，则从该bucket中寻找空余位置并插入

如果当前map处于搬迁过程中，那么新元素会直接插入到新的buckets数组中，但查找过程仍从oldbuckets数组中开始。

更新操作

更新操作实际上是添加操作的特殊情况，如果元素不存在，则更新操作实际上等同于新增操作

删除操作

删除元素实际上是先查找元素，如果元素存在则把元素从相应的bucket中删除掉，如果不存在则忽略。