深入理解Go语言中的map

Golang
163
0
0
2024-07-06
深入浅出：Go语言编译原理与过程解析
上一篇
golang的设计哲学
下一篇

一、引言

哈希表和数组是最常见的数据结构，几乎所有的语言都会有数组和哈希表两种容器类型 。哈希表表示的是键值对之间映射关系，在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变量会遍历对应的值。每次迭代时，key和value都会更新为当前遍历到的键值对。

可以忽略第二个变量

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.Map。sync.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. 避免大键：使用较小的键类型，如int或int64，可以减少哈希计算的开销。
  3. 使用结构体指针：如果值是大型结构体，使用指向这些结构体的指针作为值，可以减少内存使用和复制开销。
  4. 并发控制：对于并发访问，使用sync.Map或自行实现的并发安全Map，确保使用适当的锁策略。
  5. 性能分析：使用Go的pprof工具进行性能分析，找出热点函数和性能瓶颈。
  6. 监控内存使用：使用内存分析工具监控Map的内存使用情况，及时发现潜在的内存问题。
  7. 适时清理：对于不再需要的键值对，及时删除可以帮助减少内存压力。

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

深入浅出：Go语言编译原理与过程解析
上一篇
golang的设计哲学
下一篇