映射（也称为关联数组、哈希表、哈希映射、哈希集、字典）是日常工作、编程竞赛或工作面试中解决不同算法问题的重要数据结构。因此，了解映射为您作为开发人员提供的功能至关重要：它们支持的操作、不同操作的时间和空间复杂度，以及如何在代码中使用此结构。利用这些知识和一些实践经验，您将能够检测出何时需要应用映射来解决您的问题的情况。您正在阅读的文章提供了有关映射使用的全面指南。我们将首先简要概述映射数据结构，然后深入研究 Go 编程语言中映射的实现，并讨论在并发代码中使用映射的策略。 初学者地图 关联数组 首先，我们来讨论一下各种编程语言中实现的所有数据结构背后的一个重要概念：抽象数据类型。这是一个数学模型，用于描述数据类型所支持的操作、这些操作的行为以及可以传递给它们或从它们接收的可能值。映射还有一种抽象数据类型，称为关联数组。 关联数组是一种抽象数据类型，用于存储键值对的集合，其中每个键在集合中仅出现一次，换句话说，集合中每个键只有一个值。它支持 、 和 操作。 get set delete 让我们想象一下，我们在 Go 编程语言中实现了一个关联数组，它可以存储键和值对，其中键和值都是字符串，并看看操作是什么样的。 package main import ( "fmt" ) // type AssociativeArray implementation somewhere here func main() { // Initialize a new associative array. associativeArray := NewAssociativeArray() // Set the value for the key "Alice". associativeArray.Set("Alice", "apple") // Attempt to retrieve and print the value associated with "Alice". valueForAlice, found := associativeArray.Get("Alice") if found { fmt.Println(valueForAlice) // Output: "apple" } else { fmt.Println("No value found for Alice.") } // Delete the entry associated with "Alice". associativeArray.Delete("Alice") // Attempt to retrieve the value for "Alice" after deletion to check error handling. valueForAlice, found = associativeArray.Get("Alice") if !found { fmt.Println("No value found for Alice. (Deleted)") } // Attempt to retrieve the value for "Bob" which was never set. valueForBob, found := associativeArray.Get("Bob") if !found { fmt.Println("No value found for Bob. (Never set)") } } 设置之前已设置的键是有效操作，但在这种情况下，新值将与旧键关联，并且无法检索先前的值。它可能会被删除或隐藏，具体取决于关联数组的实现。 package main import ( "fmt" ) // type AssociativeArray implementation somewhere here func main() { // Initialize a new associative array. associativeArray := NewAssociativeArray() // Set value associated with "Alice" key associativeArray.Set("Alice", "apple") // Get value associated with "Alice" key valueForAlice := associativeArray.Get("Alice") fmt.Println(valueForAlice) // This line will print "apple" // Set new value associated with "Alice" key associativeArray.Set("Alice", "orange") // Get new value associated with "Alice" key valueForAlice = associativeArray.Get("Alice") fmt.Println(valueForAlice) // This line will print "orange" } 这很好，但你可能会问如何在现实生活中实现关联数组。实际上，实现没有限制。你可以用任何你能想到的方式实现它；你只需要支持这种抽象数据类型所需的操作。然而，有几种最常见的方法：哈希图和二叉搜索树。它们之间的区别在于它们的时间和空间复杂性，当然还有存储和检索键和值的算法。接下来，我们将专注于哈希图的实现，但值得注意的是，二叉搜索树也可用于实现关联数组。 哈希图 我们发现哈希映射是一种实现关联数组操作的数据结构：为键设置值、通过键检索值以及删除与键关联的值。但是哈希映射在底层是如何工作的呢？让我们来一探究竟。 这里的核心思想隐藏在“哈希”一词背后。哈希映射使用哈希函数通过将键传递给哈希函数来计算数组中将存储值的位置的索引。让我们尝试使用 Go 编程语言实现一个简单的哈希映射，看看哈希函数和数组如何一起运行以构建哈希映射。 package main import "fmt" func main() { // Define an array to hold string data array := make([]string, 10) // Hash function that returns an integer based on the key and array length hash := func(key string, length int) int { calculatedHash := 0 for _, char := range key { calculatedHash += int(char) } return calculatedHash % length } // Set operation: store a value associated with a key index := hash("Alice", len(array)) array[index] = "apple" // Get operation: retrieve the value associated with a key index = hash("Alice", len(array)) fmt.Println(array[index]) // Should print "apple" // Delete operation: remove the value associated with a key index = hash("Alice", len(array)) array[index] = "" // Setting it to empty string, assuming nil is not an option // Check if the deletion was successful index = hash("Alice", len(array)) if array[index] == "" { fmt.Println("Value deleted successfully.") } else { fmt.Println("Value still exists:", array[index]) } } 这实际上是真实哈希映射工作方式的简化方式。您可能会注意到我们的实现在某些情况下可能会中断。如果您没有注意到，请花一点时间考虑一下潜在的问题，然后再继续阅读。 碰撞 您是否设法找出了上一个实现中的问题所在？这是两个不同的字符串可以产生相同哈希值的情况。确切地说，我们只有 可能的哈希值，但有无数个不同的键，根据 ，我们可以找到两个不同的键，它们将生成相同的哈希值，这意味着它们将对应于数组中的相同位置。 len(array) 鸽巢原理 我们该怎么做呢？我们需要找到某种方法来处理这种情况。幸运的是，聪明人已经解决了这个问题并实施了几个众所周知的解决方案，所以我们就直接使用它们，而不是重新发明轮子。 分开链接。 在这种方法中，我们不会将值直接存储在数组中，而是将每个索引存储在数组中的 。当我们向映射中添加新值时，我们将首先搜索是否存在具有相同键的项目。如果有，则只需更新该值；否则，将新项目添加到链接列表。 链接列表 开放寻址 开放寻址是解决冲突的另一种方法。现在我们将在每个数组位置存储一个键和值对。如果我们尝试添加一个新值并遇到此位置已经有一个值的情况，我们开始使用探测。探测可以是线性的、二次的、使用另一个哈希函数，甚至是随机的。在线性探测中，您开始将索引增加一，直到在底层数组中找到可用空间。当您尝试从数组中检索值并遇到数组位置中的键与搜索键不对应的情况时，也会发生相同的过程。 让我们看一下单独链接方法的实现，因为它与 Go 中实现的方法非常相似。但在检查模式之前，让我们先看看哈希图是什么样子的。 package main import ( "fmt" "hash/fnv" ) // Entry represents a key-value pair in the linked list type Entry struct { Key string Value string Next *Entry } // HashMap represents the hash table structure type HashMap struct { Buckets []*Entry Size int } // NewHashMap creates a new hash map with a given size func NewHashMap(size int) *HashMap { return &HashMap{ Buckets: make([]*Entry, size), Size: size, } } // HashFunction computes the bucket index for a given key func (h *HashMap) HashFunction(key string) int { hasher := fnv.New32() hasher.Write([]byte(key)) return int(hasher.Sum32()) % h.Size } // Insert adds a new key-value pair to the hash map func (h *HashMap) Set(key, value string) { index := h.HashFunction(key) entry := &Entry{Key: key, Value: value} if h.Buckets[index] == nil { h.Buckets[index] = entry } else { current := h.Buckets[index] for current.Next != nil { current = current.Next } current.Next = entry } } // Search finds the value for a given key in the hash map func (h *HashMap) Get(key string) (string, bool) { index := h.HashFunction(key) current := h.Buckets[index] for current != nil { if current.Key == key { return current.Value, true } current = current.Next } return "", false } // Delete removes an entry from the hash map based on the key func (h *HashMap) Delete(key string) { index := h.HashFunction(key) if h.Buckets[index] != nil { if h.Buckets[index].Key == key { h.Buckets[index] = h.Buckets[index].Next } else { current := h.Buckets[index] for current.Next != nil { if current.Next.Key == key { current.Next = current.Next.Next break } current = current.Next } } } } func main() { hm := NewHashMap(10) hm.Set("name", "John") hm.Set("age", "30") value, exists := hm.Get("name") if exists { fmt.Println("Found:", value) } else { fmt.Println("Not found") } hm.Delete("name") value, exists = hm.Get("name") if exists { fmt.Println("Found:", value) } else { fmt.Println("Not found") } } // OUTPUT: // Found: John // Not found 复杂 对于不熟悉算法复杂性概念的人来说，这可能是一个高级主题。如果您在这个描述中认出了自己，请点击 并了解这个概念。 此链接 当我们推理算法和数据结构时，时间和空间复杂度非常重要，因为它们直接影响代码的性能。让我们试着弄清楚上一章提供的实现的复杂性。 要将新的键值对添加到哈希映射中，我们需要计算哈希值，找到位于索引处的链接列表，然后遍历链接列表以找到我们的键。可能影响时间复杂度的第一件事是密钥大小；我们假设平均密钥大小很小，并且哈希函数的时间复杂度与密钥大小线性相关。在这种情况下，我们可以假设计算密钥哈希值的平均时间复杂度为 。接下来，我们需要遍历链接列表中的所有项目。项目的数量取决于发生了多少次碰撞，在最坏的情况下，当所有项目都对应于同一个哈希值时，它将是 。因此，添加操作的总时间复杂度为 （最坏情况和平均情况）。 O(1) O(n) O(1) + O(n) = O(n) 我们可以通过基于一种名为负载因子的启发式方法实现底层数组的大小调整来降低平均时间复杂度。它只是哈希映射中的键数除以底层数组中的槽数。如果此值超过某个阈值，我们可以调整底层数组的大小并将所有值复制到新数组。之后，每个链接列表的平均大小将受到限制。在这种情况下，我们可以找到一个负载因子值，使得大多数情况下的平均时间复杂度为 。我们不会在这里讨论计算，但理解这一点很重要。 O(1) 因此，哈希图提供了以下时间和空间复杂度约束： 时间复杂度：所有操作平均为 。 O(1) 空间复杂度： ，因为我们为每个键存储一个链表实体。 O(n) Go 中的 Map 了解了实现哈希映射的理论后，让我们看看 Go 编程语言为我们提供了哪些内置的映射类型。在 Go 中有几种方法可以创建映射： package main func main() { // Using the make Function: This is the most common way to create a map. // You specify the type of the keys and values. m1 := make(map[string]int) // Create a map with string keys and integer values. // You can also optionally set the size of the underlying array using a second argument if // you know how many items you will store in the map before creation. m2 := make(map[string]int, 10) // Using Map Literals: This method is similar to array or slice literals and is // useful for initializing a map with some values. m3 := map[string]int{"one": 1, "two": 2} // Creates and initializes a map. // Nil Map: A map can also be declared without initialization. Such a map // is nil and has no keys, nor can it be added to. var m4 map[string]int // m4 is nil and you cannot add keys to it without initializing it first. // To add keys to a nil map, it must first be initialized using the make function. // m3["hello"] = 1 // Would panic. Map m3 is not nil here and will not cause a panic, this comment should refer to m4 or another nil map. m4 = make(map[string]int) // Now m4 is initialized and ready for use. } Go 的内置地图类型还实现了关联数组所需的所有三个操作以及用于迭代地图项的附加功能： package main import "fmt" func main() { m := make(map[string]int) // Adding or updating an element. m["one"] = 1 // Retrieving an element and checking if a key exists. value, ok := m["four"] if ok { fmt.Println("Value exists in map:", value) } else { fmt.Println("Value doesn't exist.") } // Deleting an element. delete(m, "one") // You can iterate over a map using a for loop along with the range keyword. // This gives you access to each key and value in the map. // You shouldn't rely on the order of items; even if you run the for loop several times // in sequence, you can get a different order of items. It's a property of hash tables // in general. Items in the hash table do not have a particular order. for key, value := range m { fmt.Println(key, value) } } 任何可比较的类型都可以作为 Go 映射中的键。可比较的类型包括布尔值、数字、字符串、指针、通道和接口类型，以及仅包含可比较类型的结构或数组。此外，对于可用作映射值的类型几乎没有任何限制。它们可以是任何类型，从整数和字符串等简单类型到切片、其他映射甚至函数等复杂类型。 深入探究 Go Maps 现在我们将通过探索地图源代码来检查地图的实现。这将帮助我们更好地理解地图的内部实现方式。Go 地图的源代码可以 找到。 在这里 Go 中的映射是前面讨论过的哈希映射的一种实现。在我们之前的例子中，我们使用链表来解决冲突。Go 使用不同的方法；它不使用链表，而是使用存储桶 - 每个底层数组索引处都有其他子数组。因此本质上，底层数组是一个二维子数组。每个存储桶最多包含 8 个键值对。如果超过 8 个键哈希到一个存储桶，我们会将额外的存储桶链接到现有的存储桶 - 溢出存储桶。哈希的低位用于选择存储桶。每个存储桶包含每个哈希的几个高位，以区分单个存储桶内的条目。当映射增长时，我们会分配一个两倍大的新存储桶数组。存储桶会从旧存储桶数组逐步复制到新存储桶数组。 表示映射的主要结构称为 和 。为简单起见，我们跳过了结构中的一些辅助字段。它们对于理解算法的思想并不重要： hmap bmap type hmap struct { count int // # of live cells == size of map. Must be first (used by len() builtin) 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 // some other fields... } // 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 [abi.MapBucketCount]uint8 // Followed by bucketCnt keys and then bucketCnt elems. // Followed by an overflow pointer. } 是当前存储在映射中的项目数。buckets 是我们存储新项目的 数组， 是在调整映射大小之前存储项目的数组。Go 不会在调整大小时移动映射项目，而是逐步移动 和 是指向 结构的指针，该结构存储 （存储在 bucket 中每个键的哈希值的第一个字节的数组），后跟 键和 值，末尾有一个溢出指针 是一个特定于体系结构的值，根据文档，它不超过 8。为了更好地理解映射在内存中的样子，这里有一张图片。 count buckets oldbuckets buckets oldbuckets bmap tophash MapBucketCount MapBucketCount MapBucketCount 要找到与键关联的值，我们首先需要计算哈希值，我们将使用该哈希值来确定键所在的存储桶。为此，Go 根据体系结构和需要进行哈希处理的类型使用不同的哈希函数。计算哈希值后，Go 使用最后几个位来计算键可能所在的索引。Go 还将哈希值的第一个字节存储在 tophash 数组中，使用键的哈希值，您可以使用 轻松找到存储桶中可能的键索引。之后，我们还需要将搜索到的键与存储在存储桶中的键进行比较，因为哈希值的第一个字节之间也可能存在冲突。该过程如图所示。 tophash 并发：Map 与 sync.Map 并发映射 我们已经了解了 map 的内部实现，但 Go 是一种旨在开发高并发代码的语言。当两个或多个 goroutine 同时对 map 执行操作时，我们将如何处理 map？让我们考虑两种情况：两个并发运行的 goroutine 从先前初始化的 map 中读取一些值，以及 goroutine 执行写入操作。 如果两个 goroutine 同时运行以从共享映射中读取一些值，则不会遇到问题，因为在读取操作期间映射的内部状态不会发生变化。因此，我们可以安全地同时读取。 package main import ( "fmt" "sync" ) func main() { var wg sync.WaitGroup m := make(map[string]int) m["a"] = 1 m["b"] = 2 readMap := func(key string) { value, ok := m[key] if ok { fmt.Println("Read:", key, value) } else { fmt.Println("Key not found:", key) } wg.Done() } wg.Add(2) go readMap("a") go readMap("b") wg.Wait() } 另一方面，当我们执行并发写入时，映射可以在写入操作期间改变状态。正如我们在上一节中已经检查过的，写入操作不是原子的。这意味着在映射修改步骤之间可能存在其他操作，如果我们尝试在另一个写入过程中读取或写入，我们可能会面临处于错误状态的映射。Go 足够聪明，可以检测到您是否尝试对映射执行并发写入，并会抛出 。 fatal error: concurrent map writes 为了解决这个问题，我们需要使用互斥锁。互斥锁是一种同步原语，可防止多个执行线程同时修改或访问状态。它支持两个操作，锁定和解锁，这两个操作是原子执行的，因此是安全的。实际上，我们可以使用 RWMutex，它允许多个读取器锁定读取，但只能锁定一个写入。这可以帮助我们在有大量读取的情况下优化性能。让我们看看并发安全映射的实现。 package main import ( "fmt" "sync" ) // ConcurrentMap wraps a Go map with a sync.RWMutex to manage concurrent access with optimized read performance type ConcurrentMap struct { sync.RWMutex items map[string]interface{} } // NewConcurrentMap creates a new concurrent map func NewConcurrentMap() *ConcurrentMap { return &ConcurrentMap{ items: make(map[string]interface{}), } } // Set adds or updates an element in the map func (m *ConcurrentMap) Set(key string, value interface{}) { m.Lock() defer m.Unlock() m.items[key] = value } // Get retrieves an element from the map func (m *ConcurrentMap) Get(key string) (interface{}, bool) { m.RLock() defer m.RUnlock() value, exists := m.items[key] return value, exists } // Delete removes an element from the map func (m *ConcurrentMap) Delete(key string) { m.Lock() defer m.Unlock() delete(m.items, key) } // Items returns a copy of all items in the map for safe iteration func (m *ConcurrentMap) Items() map[string]interface{} { m.RLock() defer m.RUnlock() itemsCopy := make(map[string]interface{}) for key, value := range m.items { itemsCopy[key] = value } return itemsCopy } func main() { cmap := NewConcurrentMap() cmap.Set("name", "John Doe") cmap.Set("age", 30) if name, ok := cmap.Get("name"); ok { fmt.Println("Name:", name) } if age, ok := cmap.Get("age"); ok { fmt.Println("Age:", age) } items := cmap.Items() fmt.Println("All items:", items) } 同步地图 标准包中还有一个并发安全映射的实现：sync.Map。但是我们什么时候应该使用 sync.Map 或带有互斥锁的映射呢？是时候弄清楚了。根据文档，Map 类型针对两种常见用例进行了优化： 当给定键的条目仅被写入一次但被读取多次时，就像在仅增长的缓存中一样 当多个 goroutine 读取、写入和覆盖不相交的键集的条目时。在这两种情况下，与使用单独的 Mutex 或 RWMutex 配对的 Go map 相比，使用 Map 可以显著减少锁争用。 为了更好地理解和体会为什么在这些情况下 sync.Map 比带有 Mutex 的地图效果更好，我们应该检查 sync.Map 的 。 源代码 type Map struct { mu Mutex read atomic.Pointer[readOnly] dirty map[any]*entry // some other fields... } // readOnly is an immutable struct stored atomically in the Map.read field. type readOnly struct { m map[any]*entry amended bool // true if the dirty map contains some key not in m. } // An entry is a slot in the map corresponding to a particular key. type entry struct { p atomic.Pointer[any] } 维护两种映射数据表示： 和 。读取映射 ( )：这是 的主要数据存储，用于并发读取访问。它由指向 结构的 表示，确保对映射快照进行原子和无锁读取。查找键时，它首先检查 映射。如果未找到键且映射被标记为 （表示 映射中有新键，但尚未出现在 映射中），它会回退到在互斥锁 ( ) 下检查 映射。脏映射 ( )：此映射存储正在修改的条目和 映射中尚未可见的新条目。访问此映射需要持有互斥锁以确保独占访问。在写入操作中，如果键不在 映射中或需要更新，则操作将在 映射上继续。如果 映射为 ，则通过对 映射进行浅拷贝来初始化它，排除不再有效的条目。在“未命中”（查找失败，需要回退到 图）达到一定阈值后， 图将被提升为新的 图，并且在必要时准备一个新的 图。 Map read dirty read Map readOnly atomic.Pointer read amended dirty read mu dirty dirty read read dirty dirty nil read dirty dirty read dirty 与内置带有互斥锁的 Go Map 的区别 现在我们可以弄清楚带有 Mutex 的内置 map 和 sync.Map 之间的区别了： ： 锁争用 ：旨在最大限度地减少锁争用。对于大多数读取操作，由于 指针是原子的，因此无需锁定。仅影响一小部分映射的写入和删除也会最大限度地缩短锁定持续时间，因为它们仅锁定 映射。 sync.Map read dirty ：每次访问（读取或写入）都需要获取互斥锁，这在高并发场景中可能成为瓶颈。 带互斥锁的内置地图 ： 内存开销和复杂性 ：维护两个版本的地图，可能占用更多内存。管理这些版本的逻辑增加了复杂性。 sync.Map ：与 相比更简单且占用更少的内存，因为它只维护地图的一个版本。 带有互斥锁的内置地图 sync.Map ： 用例特殊性 ：针对大多数情况下只读取键而很少更新键的情况，或者许多操作发生在不相交的键集上的用例进行了优化。 sync.Map ：通用，使用简单，但由于通用锁争用，在特定的高并发场景下可能表现不佳。 带互斥锁的内置映射 综上所述， 专门用于可以利用其并发优化来减少锁争用的场景，但代价是增加复杂性和内存使用量。相比之下，带有互斥锁的标准 Go map 是一种更简单、更通用的解决方案，但在高度并发的环境中可能会出现性能问题。 sync.Map 包起来 在本文中，我们探讨了使用映射数据结构的复杂性，特别是关注它们在 Go 编程语言中的实现和用法。从关联数组的基本概念开始，我们深入研究了哈希映射的机制，讨论了它们的操作过程、时间和空间复杂性，以及用于处理冲突的不同方法，例如单独链接和开放寻址。 在 Go 领域，我们研究了如何使用和将地图构建到语言中，研究了诸如 和 之类的底层结构。此探索包括实际的代码示例，演示了如何在 Go 应用程序中初始化、操作和有效使用地图。此外，我们强调了使用地图时并发的潜在陷阱，并针对需要并发访问的场景引入了 ，这可以减少锁争用并优化性能。 hmap bmap sync.Map 了解地图数据结构的这些方面不仅可以增强您的编码工具包，还可以让您以更高的效率和信心应对常见的编程挑战。无论您是在开发简单的应用程序还是需要在并发环境中实现最佳性能的复杂系统，了解如何以及何时使用不同类型的地图都是非常宝贵的。随着您继续积累编程专业知识，请继续尝试这些结构及其各种实现，以充分利用它们在您的项目中的潜力。
