深入理解Go语言中的map

Golang
29
0
0
2024-07-06

一、引言

哈希表和数组是最常见的数据结构,几乎所有的语言都会有数组和哈希表两种容器类型 。哈希表表示的是键值对之间映射关系,在Go语言中,通过map来表示哈希表。 本文将深入浅出介绍map的概念、使用方式、底层结构、性能、最佳实现等话题,帮助开发更好的理解和使用map

二、map的基本概念和使用

1. 什么是map

在Go语言中,map是一种内置的数据结构,用于存储键值对。Go语言中的map有如下特点

  • 内置数据结构map是Go语言内置的数据结构,它是一种无序的键值对集合,其中键是唯一的。Go语言在语言级别支持map, 使用方便。
  • 快速查找map提供了非常快速的查找、插入和删除操作,这些操作的平均时间复杂度为O(1)。这使得map非常适合用于需要快速访问数据的场景。
  • 动态性map是动态的,可以在运行时动态地增加或删除键值对,而不需要预先声明大小。
  • 键的多样性:Map的键可以是任何可比较的类型,例如整数、字符串等。这为存储和检索各种类型的数据提供了灵活性。
  • 非并发安全:标准的Map在Go中并不是并发安全的。如果需要在多个goroutine中并发访问Map,需要使用sync包中的Mutex或RWMutex来保证并发安全,或者使用并发安全的数据结构,如sync.Map。
  • 应用场景:Map在Go中被广泛应用于各种场景,如数据库查询结果的存储、配置项的读取、缓存的实现等。

2. map的定义和初始化

初始化Map有几种方式:

// 方式一: 使用var关键字声明Map,然后使用make函数初始化
var myMap map[string]int
myMap = make(map[string]int)

// 方式二: 使用make函数直接声明并初始化Map
myMap := make(map[string]int)

// 方式三: 使用Map字面量初始化Map,这在创建预填充的Map时非常有用
myMap := map[string]int{
    "apple":  5,
    "banana": 10,
}

注意: 使用Map时,如果没有初始化(即值为nil),直接赋值会导致运行时错误。

3. map基本操作:增、删、改、查

下面是对map进行增、删、改、查的基本方法

// 增(Insert): 向Map中添加新的键值对; 如果key已存在,则更新value
myMap["orange"] = 15

// 删(Delete): 从Map中删除键值对; 如果key不存在,delete函数不会执行任何操作。
delete(myMap, "apple")

// 改(Update): 更新Map中的键值对; 如果key已经存在,这将替换原来的值。如果key不存在,这将添加一个新的键值对
myMap["banana"] = 20

// 查(Lookup):查找Map中的键对应的值;
value, exists := myMap["banana"] // 这里value是与键关联的值,exists是一个布尔值,如果键存在于Map中,则为true;如果键不存在,则为false,并且value将是类型的零值。
value := myMap["banana"] // 如果你只关心值,可以忽略第二个返回值

注意: map在并发环境下不是线程安全的,如果需要在多个goroutine中使用Map,应该使用互斥锁(sync.Mutex)或者使用sync.Map

4. map的遍历

在Go语言中,可以使用for循环和range关键字来遍历Map。遍历时,range表达式返回两个值:键和对应的值。这里是一个基本的例子:

myMap := map[string]int{
    "apple":  5,
    "banana": 10,
    "cherry": 15,
}

for key, value := range myMap {
    fmt.Printf("Key: %s, Value: %d\n", key, value)
}

在上面的代码中,key变量会遍历Map中的所有键,而value变量会遍历对应的值。每次迭代时,keyvalue都会更新为当前遍历到的键值对。

可以忽略第二个变量

for key := range myMap {

如果你只需要值,可以使用下划线_来忽略键:

for _, value := range myMap {

需要注意的是,Map的遍历顺序是随机的,每次遍历的顺序可能都不一样。这是因为Go的Map类型是故意设计为无序的,以避免依赖特定的遍历顺序,这可能会导致程序中的一些隐蔽的bug。

此外,虽然可以在遍历过程中删除或修改Map中的键值对,但是添加键值对可能会导致未定义的行为。如果需要在遍历时修改Map,建议先记录需要做出的更改,然后在遍历结束后进行。

三、哈希函数简介

在Go语言中,map本质上是哈希表(hash table)。哈希表是一种使用哈希函数组织数据,以支持快速插入和搜索的数据结构。实现哈希表的两个关键是哈希函数和解决哈希冲突。

哈希函数

哈希函数,也被称为散列函数,是一种将任意长度的输入(如字符串)通过特定的散列算法,变换成固定长度的输出(即哈希值或消息摘要)的函数。通常,会使用类似数组(连续内存)的形式来存储哈希值,从而保证哈希值的访问性能。

哈希函数应该尽可能保证不同的输入有相同的输出。

如上图所示,哈希函数的结果分布较为均匀,哈希值的增删改查的时间复杂度为O(1)

哈希冲突

在实际场景中,因为可能的输入范围通常是远超映射范围(输出的范围,受存储空间的影响)。因而难免会出现不同的输入得到相同的输出,即发生哈希冲突。

基于拉链法实现的哈希函数

大多数的编程语言都用拉链法实现哈希表, 拉链法通常使用数组和链表作为底层数据结构。

哈希值使用数组将哈希值HashValue相同的Key对应的Value通过链表数组进行维护

哈希函数将哈希键Key映射到数组的索引,数组的每一个元素都有一个Value桶,使用链表进行维护。

四、map的底层数据结构

源码分析

在Go语言中,map使用类似拉链法的方式实现哈希表,Go语言运行时同时使用了多个数据结构组合表示哈希表。

// runtime/map.go
// A header for a Go map.
type hmap struct {
	count     int // 当前哈希表中的元素数量
	flags     uint8
	B         uint8  // 当前哈希表持有的 buckets 数量, 因为哈希表中桶的数量都按2倍扩容,改字段存储对数,也就是 len(buckets) == 2^B
	noverflow uint16 // 溢出桶的大致数量
	hash0     uint32 // hash seed

	buckets    unsafe.Pointer // 存储 2^B 个桶的数组
	oldbuckets unsafe.Pointer // 扩容时用于保存之前 buckets 的字段 , 大小事buckets的一般
	nevacuate  uintptr        // progress counter for evacuation (buckets less than this have been evacuated)

	extra *mapextra // optional fields
}

// mapextra 主要维护,当hmap中的buckets中有一些桶发生溢出,但有达不到扩容阈值时,存储溢出的桶
type mapextra struct {
	overflow    *[]*bmap
	oldoverflow *[]*bmap

	// nextOverflow holds a pointer to a free overflow bucket.
	nextOverflow *bmap
}

runtime.hmap结构体中,buckets字段是一个unsafe.Pointer , 因为go语言中支持不同类型的键值对,需要在编译时才能确定map的类型。

可以查看编译时如何重建hmap类型reflectdata.MapType()

func MapType(t *types.Type) *types.Type {
	if t.MapType().Hmap != nil {
		return t.MapType().Hmap
	}

	bmap := MapBucketType(t)  // 构建bmap类型

	fields := []*types.Field{
		makefield("count", types.Types[types.TINT]),
		makefield("flags", types.Types[types.TUINT8]),
		makefield("B", types.Types[types.TUINT8]),
		makefield("noverflow", types.Types[types.TUINT16]),
		makefield("hash0", types.Types[types.TUINT32]), // Used in walk.go for OMAKEMAP.
		makefield("buckets", types.NewPtr(bmap)),       // Used in walk.go for OMAKEMAP.
		makefield("oldbuckets", types.NewPtr(bmap)),
		makefield("nevacuate", types.Types[types.TUINTPTR]),
		makefield("extra", types.Types[types.TUNSAFEPTR]),
	}

	hmap := types.NewStruct(types.NoPkg, fields)
	hmap.SetNoalg(true)
	types.CalcSize(hmap)

	// The size of hmap should be 48 bytes on 64 bit
	// and 28 bytes on 32 bit platforms.
	if size := int64(8 + 5*types.PtrSize); hmap.Size() != size {
		base.Fatalf("hmap size not correct: got %d, want %d", hmap.Size(), size)
	}

	t.MapType().Hmap = hmap
	hmap.StructType().Map = t
	return hmap
}

这里可以看出buckets是指向bmap的指针, bmap也是在编译时通过bmap := MapBucketType(t) 进行构建的,而非runtime.bmap中的定义那般简单:

// runtime.bmap
type bmap struct {
	tophash [bucketCnt]uint8
}

可以查看

// MapBucketType makes the map bucket type given the type of the map.
func MapBucketType(t *types.Type) *types.Type {
	if t.MapType().Bucket != nil {
		return t.MapType().Bucket
	}

	keytype := t.Key()
	elemtype := t.Elem()
	types.CalcSize(keytype)
	types.CalcSize(elemtype)
	if keytype.Size() > MAXKEYSIZE {
		keytype = types.NewPtr(keytype)
	}
	if elemtype.Size() > MAXELEMSIZE {
		elemtype = types.NewPtr(elemtype)
	}

	field := make([]*types.Field, 0, 5)

	// The first field is: uint8 topbits[BUCKETSIZE].
	arr := types.NewArray(types.Types[types.TUINT8], BUCKETSIZE)
	field = append(field, makefield("topbits", arr))

	arr = types.NewArray(keytype, BUCKETSIZE)
	arr.SetNoalg(true)
	keys := makefield("keys", arr)
	field = append(field, keys)

	arr = types.NewArray(elemtype, BUCKETSIZE)
	arr.SetNoalg(true)
	elems := makefield("elems", arr)
	field = append(field, elems)

	// If keys and elems have no pointers, the map implementation
	// can keep a list of overflow pointers on the side so that
	// buckets can be marked as having no pointers.
	// Arrange for the bucket to have no pointers by changing
	// the type of the overflow field to uintptr in this case.
	// See comment on hmap.overflow in runtime/map.go.
	otyp := types.Types[types.TUNSAFEPTR]
	if !elemtype.HasPointers() && !keytype.HasPointers() {
		otyp = types.Types[types.TUINTPTR]
	}
	overflow := makefield("overflow", otyp)
	field = append(field, overflow)

	// link up fields
	bucket := types.NewStruct(types.NoPkg, field[:])
	bucket.SetNoalg(true)
	types.CalcSize(bucket)
	
	// ......
	
	return bucket
}

重建后的结构体如下所示:

type bmap struct {
    topbits  [8]uint8
    keys     [8]keytype
    elems    [8]elemtype
    overflow uintptr
}

示意图

综上所示,map的底层结构如下图所示:

五、map的操作性能分析

1. 时间复杂度:最好和最坏情况

  • 最好情况: 每个键都映射到不同的桶中,没有发生哈希冲突。此时,Map的插入、查找和删除操作的时间复杂度都是O(1)。
  • 最坏情况: 所有的键都映射到同一个桶中,发生了极端的哈希冲突。此时,Map中的操作可能需要遍历整个链表,时间复杂度变为O(n)。不过,由于Go的Map实现会自动扩容,并重新分配键值对,这种情况在实践中很少发生。

2. 空间复杂度

Map的空间复杂度取决于存储的键值对数量以及哈希桶的数量。在Go中,Map的空间复杂度通常可以认为是O(n),其中n是键值对的数量。随着键值对数量的增加,Map可能会进行扩容,增加哈希桶的数量,以保持操作的效率。

3. 性能优化技巧

  • 合理估计Map大小:如果你预先知道将要存储的键值对的大致数量,可以在创建Map时指定一个初始容量,这有助于减少自动扩容的次数,从而提高性能。
myMap := make(map[string]int, initialCapacity)
  • 选择合适的键类型:使用较小的、可比较性能较高的键类型,可以减少哈希计算的开销。例如,int类型通常比string类型作为键更高效。
  • 避免复杂的键结构:如果键是一个复杂的结构体,那么比较和哈希计算的开销会更大。如果可能,尝试将复杂的键简化,或者使用能够唯一表示键的简单类型。
  • 使用并发安全的Map:如果需要在多个goroutine中并发访问Map,使用sync.Mapsync.Map提供了一些优化,不需要开发者自己实现同步,可以在并发环境中提供更好的性能。
  • 避免频繁的内存分配:在Map的使用过程中,尽量避免频繁地增加和删除键值对,因为这可能导致频繁的内存分配和垃圾回收。
  • 监控性能指标:在性能关键的应用中,监控Map的大小和性能指标,及时调整策略,可以帮助发现潜在的性能问题。

六、map的扩容策略

在Go语言中,Map的扩容是一个自动的过程,旨在维护Map的性能,特别是插入和查找操作的时间复杂度。

1. 扩容的出发条件

map在写入哈希键值对时runtime.mapassign, 会判断是否需要扩容:

func mapassign(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer {
...
	// If we hit the max load factor or we have too many overflow buckets,
	// and we're not already in the middle of growing, start growing.
	if !h.growing() && (overLoadFactor(h.count+1, h.B) || tooManyOverflowBuckets(h.noverflow, h.B)) {
		hashGrow(t, h)
		goto again // Growing the table invalidates everything, so try again
	}
...
}

// overLoadFactor reports whether count items placed in 1<<B buckets is over loadFactor.
func overLoadFactor(count int, B uint8) bool {
	return count > bucketCnt && uintptr(count) > loadFactorNum*(bucketShift(B)/loadFactorDen)
}

func tooManyOverflowBuckets(noverflow uint16, B uint8) bool {
	if B > 15 {
		B = 15
	}
	return noverflow >= uint16(1)<<(B&15)
}

可以看出扩容的两个条件:

  • 装载因子超过阈值6.5: overLoadFactor(h.count+1, h.B) , 装载因子:=元素数量÷桶数量
  • 使用了太多溢出桶: tooManyOverflowBuckets(h.noverflow, h.B))

h.growing() 用于避免并发扩容,导致混乱。

2. 扩容过程

当Map需要扩容时,Go运行时会进行以下步骤:

  1. 新桶数组:分配一个新的、更大的桶数组。新数组的大小通常是原来大小的两倍,这有助于分散键值对,减少冲突。
  2. 重新哈希:遍历旧的桶数组中的所有键值对,并使用哈希函数重新计算每个键的位置,将它们插入到新的桶数组中。
  3. 逐步迁移:为了避免在扩容时暂停整个程序,Go的Map实现可能会选择逐步迁移键值对。这意味着在扩容期间,旧的桶数组和新的桶数组会同时存在,新插入的键值对会直接放入新的桶中,而对旧桶的访问会触发迁移操作。
  4. 更新内部状态:一旦所有键值对都迁移到新的桶数组中,Map的内部状态会更新,以反映新的结构。
func hashGrow(t *maptype, h *hmap) {
	...
	// 原有桶设置给oldbuckets
	oldbuckets := h.buckets   
	// 创建新桶
	newbuckets, nextOverflow := makeBucketArray(t, h.B+bigger, nil)

	flags := h.flags &^ (iterator | oldIterator)
	if h.flags&iterator != 0 {
		flags |= oldIterator
	}
	// commit the grow (atomic wrt gc)
	h.B += bigger
	h.flags = flags
	h.oldbuckets = oldbuckets
	h.buckets = newbuckets
	h.nevacuate = 0
	h.noverflow = 0

	...
}

键值对的迁移并摆在hashGrow中进行,而是在runtime.mapassign中逐步迁移的。

func mapassign(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer {
...
	if h.growing() {
		growWork(t, h, bucket)
	}
...
}

runtime.growWork中执行迁移的具体工作

func growWork(t *maptype, h *hmap, bucket uintptr) {
	// make sure we evacuate the oldbucket corresponding
	// to the bucket we're about to use
	evacuate(t, h, bucket&h.oldbucketmask())

	// evacuate one more oldbucket to make progress on growing
	if h.growing() {
		evacuate(t, h, h.nevacuate)
	}
}

3. 扩容对性能的影响

扩容是一个昂贵的操作,它涉及到内存分配和键值对的重新哈希。在扩容期间,Map的性能可能会暂时下降,特别是在插入新元素时。然而,扩容完成后,由于减少了哈希冲突,Map的性能通常会得到提升。

七、map与并发安全

1. Map的并发问题

在Go语言中,标准的Map不是并发安全的。这意味着如果多个goroutine同时对同一个Map进行读写操作,可能会导致竞态条件(race condition),从而引发不可预知的行为,如Map的内部结构损坏、程序崩溃等。

并发问题主要发生在以下情况:

  1. 同时写入:当两个或更多的goroutine尝试同时写入Map时,可能会导致数据冲突和不一致。
  2. 读写同时进行:当一个goroutine在读取Map,而另一个goroutine在写入Map时,读取操作可能会遇到不完整或不一致的数据。

为了避免这些问题,需要采取措施来确保对Map的并发访问是安全的。

2. 使用sync.Map

sync.Map是Go语言在sync包中提供的一个并发安全的Map类型。它使用了一些优化技术来减少锁的粒度,提高并发性能。

sync.Map提供了以下几个主要的方法:

  • Store(key, value):存储键值对。
  • Load(key):根据键获取值。
  • LoadOrStore(key, value):获取或存储键值对。
  • Delete(key):删除键值对。
  • Range(f func(key, value interface{}) bool):遍历Map。

sync.Map适用于以下使用场景:

  1. 键值对的写入操作比读取操作少得多sync.Map在这种场景下性能较好,因为它减少了锁的竞争。
  2. Map中的键值对数量很大,且键的集合相对稳定:在这种情况下,sync.Map可以有效地减少锁的粒度,提高并发访问的性能。
  3. 多个goroutine读取同一个键值对sync.Map可以在不加锁的情况下安全地返回同一个键的值。

关于sync.Map的更多介绍,参考《深入理解Go语言sync.Map》

八、最佳实践与常见问题

1. 何时使用Map

Map适用于以下场景:

  1. 快速查找:当需要快速根据键查找值时,Map提供了平均时间复杂度为O(1)的查找性能。
  2. 去重:当需要存储唯一键时,Map的键不允许重复,自然可以实现去重功能。
  3. 关联数据:当数据以键值对的形式存在,并且需要经常更新或查询时,Map是一个很好的选择。
  4. 动态集合:当需要动态地添加或删除键值对时,Map提供了灵活的操作。

2. Map的性能陷阱

  1. 并发使用:在多个goroutine中使用Map时,如果没有正确的同步机制,会导致竞态条件。
  2. 大量删除操作:频繁的插入和删除操作可能会导致Map的性能下降,因为这可能会引起频繁的内存分配和垃圾回收。
  3. 迭代效率:虽然Map的迭代操作简单,但如果Map很大,迭代可能会比预期慢,尤其是在Map扩容时。
  4. 内存使用:Map的内存使用可能比预期高,特别是当存储大量小对象时,因为每个键值对都有一定的存储开销。

3. 调试与优化Map性能的技巧

  1. 预分配大小:如果能预估Map的大小,使用make(map[KeyType]ValueType, size)预分配足够的空间可以减少扩容带来的性能损耗。
  2. 避免大键:使用较小的键类型,如intint64,可以减少哈希计算的开销。
  3. 使用结构体指针:如果值是大型结构体,使用指向这些结构体的指针作为值,可以减少内存使用和复制开销。
  4. 并发控制:对于并发访问,使用sync.Map或自行实现的并发安全Map,确保使用适当的锁策略。
  5. 性能分析:使用Go的pprof工具进行性能分析,找出热点函数和性能瓶颈。
  6. 监控内存使用:使用内存分析工具监控Map的内存使用情况,及时发现潜在的内存问题。
  7. 适时清理:对于不再需要的键值对,及时删除可以帮助减少内存压力。

通过遵循这些最佳实践和技巧,可以有效地使用Map,并优化其性能。在实际开发中,应该根据具体的应用场景和需求来选择和调整策略。