我们将讨论不使用泛型的语言中Map的实现，考虑什么是哈希表，如何在Go中进行排列，此实现的利弊是什么，以及在使用此结构时应注意的事项。
细节剪下。
注意！ 如果您已经熟悉Go中的哈希表，建议您跳过基础知识，然后转到
此处 ，否则可能会厌倦最有趣的时刻。
什么是哈希表
首先，我会提醒您什么是哈希表。 这是一个数据结构，允许您存储键值对，并且通常具有以下功能：
- 映射：
map(key) → value
- 插入：
insert(map, key, value)
- 删除：
delete(map, key)
- 搜索：
lookup(key) → value
Go语言中的哈希表
go语言的哈希表由map关键字表示，可以通过以下方式之一进行声明（稍后会详细介绍）：
m := make(map[key_type]value_type) m := new(map[key_type]value_type) var m map[key_type]value_type m := map[key_type]value_type{key1: val1, key2: val2}
主要操作如下：
- 插入：
m[key] = value
- 去除：
delete(m, key)
- 搜索：
value = m[key]
或
value, ok = m[key]
围着桌子走
考虑以下程序：
package main import "fmt" func main() { m := map[int]bool{} for i := 0; i < 5; i++ { m[i] = ((i % 2) == 0) } for k, v := range m { fmt.Printf("key: %d, value: %t\n", k, v) } }
发射1：
key: 3, value: false key: 4, value: true key: 0, value: true key: 1, value: false key: 2, value: true
运行2：
key: 4, value: true key: 0, value: true key: 1, value: false key: 2, value: true key: 3, value: false
如您所见，输出在每次运行中都不同。 所有这些都是因为Go中的地图是无序的，也就是说，是无序的。 这意味着您在走动时不需要依赖顺序。 原因可以在语言运行时的源代码中找到：
搜索位置是
随机确定的，记住这一点！ 有传言说运行时开发人员强迫用户不要依赖顺序。
去表搜索
让我们再次看一段代码。 假设我们要创建“数字”-“数字乘以10”对：
package main import ( "fmt" ) func main() { m := map[int]int{0: 0, 1: 10} fmt.Println(m, m[0], m[1], m[2]) }
我们推出：
map[0:0 1:10] 0 10 0
而且我们看到，当我们尝试获取2的值（我们忘记放置）时，得到0。我们在
文档中找到解释此行为的行：“尝试使用映射中不存在的键来获取映射值将返回零值。 ”，但翻译成俄语，这意味着当我们尝试从地图中获取值，但不存在时，我们会得到“零类型值”，如果是数字0，该值，该怎么做，我们是否要区分案例0和缺席2？ 为此，我们提出了一种特殊的“多重分配”形式-映射返回一个对，而不是通常的单个值：该值本身和另一个布尔值，用于回答映射中是否存在所请求的键的问题“
正确地，前面的代码如下所示：
package main import ( "fmt" ) func main() { m := map[int]int{0: 0, 1: 10} m2, ok := m[2] if !ok {
在启动时，我们得到：
map[0:0 1:10] 0 10 20
在Go中创建一个表。
假设我们要计算一个字符串中每个单词的出现次数，为此启动一个字典并遍历它。
package main func main() { var m map[string]int for _, word := range []string{"hello", "world", "from", "the", "best", "language", "in", "the", "world"} { m[word]++ } for k, v := range m { println(k, v) } }
你看到
地鼠了吗？ -他是！
当我们尝试启动这样的程序时，会出现恐慌和消息“分配给nil map中的条目”。 所有这些都是因为mapa是引用类型，而且还不足以声明一个变量，因此您需要对其进行初始化：
m := make(map[string]int)
稍微降低一点，就很清楚为什么这样做会如此。 最初，已经介绍了创建映射的4种方法，我们研究了其中的两种方法-将其声明为变量并通过make进行创建。 您也可以使用“
复合文字 ”设计进行创建
map[key_type]value_type{}
如果愿意，即使立即使用值进行初始化，此方法也有效。 至于使用new的创建-我认为这是没有意义的，因为此函数为变量分配内存并返回指向它的指针，该指针填充有零值类型，在map的情况下，该值将为nil（我们得到的结果与在var中，更确切地说是指向它的指针）。
映射如何传递给函数？
假设我们有一个函数试图更改传递给它的数字。 让我们看看通话前后会发生什么：
package main func foo(n int) { n = 10 } func main() { n := 15 println("n before foo =", n) foo(n) println("n after foo =", n) }
我认为一个例子是很明显的，但仍然包括结论：
n before foo = 15 n after foo = 15
您可能已经猜到了，n函数是通过值而不是通过引用来实现的，因此原始变量没有更改。
让我们做一个类似的mapa技巧：
package main func foo(m map[int]int) { m[10] = 10 } func main() { m := make(map[int]int) m[10] = 15 println("m[10] before foo =", m[10]) foo(m) println("m[10] after foo =", m[10]) }
瞧瞧：
m[10] before foo = 15 m[10] after foo = 10
该值已更改。 “好吧，Mapa是通过引用传递的？”，您问。
不行 Go中没有链接。 例如，在C ++中，不可能用1个地址创建2个变量。 但是然后您可以创建2个指向相同地址的变量（但是它们是指针，并且在Go中）。
假设我们有一个函数fn初始化映射m。 在main函数中，我们仅声明一个变量，将其发送以进行初始化，然后查看发生了什么。
package main import "fmt" func fn(m map[int]int) { m = make(map[int]int) fmt.Println("m == nil in fn?:", m == nil) } func main() { var m map[int]int fn(m) fmt.Println("m == nil in main?:", m == nil) }
结论：
m == nil in fn?: false
m == nil in main?: true
因此，变量m是通过
value传递
的 ，因此，就像将常规int传递给函数的情况一样，它没有改变（fn中值的本地副本已改变）。 那么，为什么m本身的值会发生变化？ 要回答此问题，请考虑语言运行时中的代码：
Go中的Map只是指向hmap结构的指针。 这就是为什么这个问题的答案，尽管事实上映射是通过值传递给函数的，但其中的值本身却发生了变化-这全都与指针有关。 hmap结构还包含以下内容：元素数量，“存储桶”数量（以对数形式表示，以加快计算速度），用于随机散列的种子（使其难以添加-尝试拾取键，以便出现连续冲突），各种服务字段最重要的是指向存储值的存储桶的指针 让我们看一下图片：
图片显示了内存中结构的示意图-有一个hmap头，该指针是Go中的一个映射（使用var声明时创建，但未初始化，这导致程序在尝试插入时崩溃）。 buckets字段是键-值对的存储库，有几个这样的bucket，每个bucket包含8对。 “存储桶”中的第一个是用于其他哈希位的插槽（e0..e7被称为e-因为
额外的哈希位）。 接下来是键和值，首先是所有键的列表，然后是所有值的列表。
根据函数的哈希值，确定我们将值放入哪个“ bucket”中，每个“ bucket”内部最多可以有8个冲突，如果前一个溢出，则在每个“ bucket”的末尾都有一个指向另一个指针的指针。
地图如何成长？
在源代码中，您可以找到以下行：
也就是说，如果每个存储桶中平均有6.5个以上的元素，则存储桶数组将增加。 在这种情况下，该数组的分配量是原来的2倍，并且每次插入或删除时，旧数据都会一小部分复制到该数组中，以免造成很大的延迟。 因此，在疏散数据的过程中，所有操作都会稍慢一些（搜索时，我们也必须在两个地方搜索）。 疏散成功后，新数据将开始使用。
获取地图元素的地址。
另一个有趣的观点-在使用该语言的一开始，我想这样做：
package main import ( "fmt" ) func main() { m := make(map[int]int) m[1] = 10 a := &m[1] fmt.Println(m[1], *a) }
但是Go表示：“无法采用m [1]的地址”。 为何无法取值的地址的解释在于数据撤离程序。 想象一下，我们获取了值的地址，然后mapa增长了，分配了新的内存，撤出了数据，删除了旧的数据，指针变得不正确，因此禁止了此类操作。
没有泛型的地图如何实现？
空接口和代码生成都与它无关；整个事情是在编译时替换它。 考虑一下Go熟悉的功能变成了什么：
v := m["k"] → func mapaccess1(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer v, ok := m["k"] → func mapaccess2(t *maptype, h *hmap, key unsafe.Pointer) (unsafe.Pointer, bool) m["k"] = 9001 → func mapassign(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer delete(m, "k") → func mapdelete(t *maptype, h *hmap, key unsafe.Pointer)
我们看到，有用于访问的mapaccess函数，分别用于写入和删除mapassign和mapdelete。 所有操作都使用unsafe.Pointer，它不关心它指向的类型，并且有关每个值的信息由
类型描述符描述 。
type mapType struct { key *_type elem *_type ...} type _type struct { size uintptr alg *typeAlg ...} type typeAlg struct { hash func(unsafe.Pointer, uintptr) uintptr equal func(unsafe.Pointer, unsafe.Pointer) bool...}
MapType存储键和值的描述符（_type）。 对于类型描述符，定义了比较操作（typeAlg），采用哈希，大小等，因此我们始终知道如何产生它们。
有关其工作原理的更多信息。 当我们写v = m [k]（试图从键k获得v的值）时，编译器将生成如下内容：
kPointer := unsafe.Pointer(&k) vPointer := mapaccess1(typeOf(m), m, kPointer) v = *(*typeOfvalue)vPointer
也就是说，我们使用指向键的指针mapType结构，从中找出键和值的哪些描述符，指向hmap本身的指针（即map），并将其全部传递给mapaccess1，后者将返回指向值的指针。 我们将指针转换为所需的类型，取消引用并获取值。
现在，让我们看一下运行时的搜索代码（略微适合阅读）：
func lookup(t *mapType, m *mapHeader, key unsafe.Pointer) unsafe.Pointer {
该函数在映射中搜索键并返回指向相应值的指针，这些参数已经为我们所熟悉-这是mapType，它存储键类型和值的描述符，映射本身（mapHeader）和指向存储键的内存的指针。 我们返回一个指向存储该值的内存的指针。
if m == nil || m.count == 0 { return zero }
接下来，我们检查映射头的指针是否不为null，那里是否有0个元素，如果为零，则返回null值。
hash := t.key.hash(key, m.seed)
我们计算键哈希值（我们知道如何从类型描述符中计算给定键）。 然后，我们尝试了解您需要去查看哪个“存储桶”（除以“存储桶”的数量的剩余部分，计算会略有加快）。 然后，我们计算额外的哈希（我们采用哈希的8个最高有效位），并确定“存储桶”在内存中的位置（地址算术）。
for { for i := 0; i < 8; i++ { if b.extra[i] != extra {
如果您看的话，搜索并不是那么复杂：如果没有找到，我们会遍历“存储桶”的链，然后转到下一个存储桶。 在“存储桶”中的搜索首先是对其他散列的快速比较（这就是为什么每个e0 ... e7开头都是该对的“迷你”散列，以便进行快速比较的原因）。 如果不匹配，请进一步检查（如果匹配），然后我们进行更仔细的检查-确定怀疑要搜索的密钥在内存中的位置，并比较该密钥是否与请求的密钥相等。 如果相等，请确定该值在内存中的位置并返回。 如您所见，没有什么超自然的。
结论
使用地图，但知道并了解它们的工作原理！ 您可以通过了解一些细微差别来避免陷入困境-为什么无法获取值的地址，为什么在初始化期间所有内容都落在没有初始化的情况下，为什么最好事先分配内存，如果知道元素的数量（我们将避免疏散）等等。
参考文献：
“行动中的地图”，安德鲁·格朗德“ Go运行时如何有效地实现地图”，Dave Cheney威廉·肯尼迪：“了解类型”内部地图实现，Keith Randall地图源代码，运行时高朗规格有效的去地鼠图片