Go 语言中的字典 Map

大家好，我是码农先森。

概念

在 Go 语言中，字典被称为 map，它是一种无序的集合，用于存储键值对。每个键在 map 中必须是唯一的，并且对应一个值。map 是一种非常常用的数据结构，用于快速查找和检索数据。

键约束

字典（map）的键必须是支持相等运算符（==）的类型。这意味着键必须是可以比较是否相等的类型，如整数、字符串、指针、数组、结构体等。不能使用切片、函数或包含切片的结构体作为字典的键，因为它们不支持相等运算符。

var badMap = map[interface{}]int{
    "1":      1,
    []int{2}: 2, // 这里会引发 panic
    3:        3,
}

实现原理

字典（map）是基于哈希表（hash table）实现的。哈希表是一种数据结构，通过将键转换为索引来快速定位值的位置。字典使用了哈希函数来计算键的哈希值，然后根据哈希值将键值对存储在内部的哈希桶（hash bucket）中。当需要查找时，字典会根据键的哈希值快速定位到对应的哈希桶，从而快速操作键值对。

当在字典（map）中发生哈希冲突时，会使用链地址法（chaining）进行处理。当不同的键经过哈希函数计算后得到相同的哈希值，在哈希桶（hash bucket）中会形成一个链表，该链表包含所有哈希值相同的键值对。

需要查找具有相同哈希值的键值对时，会遍历哈希桶中的链表，按顺序比较键的实际值，以确保找到正确的键值对。这种链地址法能够有效处理哈希冲突，确保字典操作的正确性，并保持较高的查询性能。

在实际使用中，字典实现会根据负载因子（load factor）等因素，动态调整哈希表的大小，以减少哈希冲突的概率，并保持字典的性能。因此，即使发生哈希冲突，字典仍然能够保持高效的操作。

总结

map 是一种常用的数据结构，操作效率高。字典的键不能使用切片、函数或包含切片的结构体，原因是它们不支持等值运算。字典使用了哈希表的数据结构实现，会遇到哈希冲突的问题；因此，还额外采用了链地址法来处理该问题，把冲突键对应的值形成一个链表，查找元素时会遍历该链表。

欢迎关注、分享、点赞、收藏、在看，我是码农先森。

本作品采用《CC 协议》，转载必须注明作者和本文链接