Golang地图内部实现 - 如何在地图中搜索密钥？

Question

我读过的"围棋程序设计语言",一个"给定的密钥可以被检索...使用键比较恒定的数量平均,无论多么大的哈希表." 我不确定这在内部的实现意味着什么.这是否意味着它会搜索每个键,直到找到匹配或内部使用的某种类型的二进制(或其他)搜索算法？

例如,如果我有一个包含2,000个密钥的地图,那么它"平均"是否需要查看1,000来查找匹配项,或者它只查看11(log2 n),就像二元搜索一样？

谢谢,本

Answer 1

映射实现为哈希表.有很多地方可以解释哈希; 这是一个很好的可视化,你可以运行.

Go的一个很好的特点是

• 源代码可以在github上获得,和
• 它编写得很好并且有文档记录,所以理解起来并不难.

从hashmap的源文件:

// A map is just a hash table. The data is arranged
// into an array of buckets. Each bucket contains up to
// 8 key/value pairs. The low-order bits of the hash are
// used to select a bucket. Each bucket contains a few
// high-order bits of each hash to distinguish the entries
// within a single bucket.
//
// If more than 8 keys hash to a bucket, we chain on
// extra buckets.

https://github.com/golang/go/blob/master/src/runtime/map.go

您可以从许多类中通常不涉及的代码中学到的一件事是,如何在内部调整地图大小时使迭代器无效.

Answer 2

本机映射类型使用哈希表实现.它在密钥上使用散列函数来生成数据数组的索引.因此,通常,大多数动作发生在O(1)时间内.这通常是正确的,因为某些键在散列时可能会产生相同的索引,称为碰撞,然后必须专门处理.

哈希表很酷!

Answer 3

概览图

桶详细信息map[string]string

每个桶存储

• 哈希码数组
  • 哈希码数组存储桶中每个键的哈希码，这用于更快的比较。
• 键值对列表
  • 每个桶最多可以存储8个这样的键值对。
• 溢出指针。
  • 如果桶接收超过 8 个值，则溢出指针可以指向新桶。

当我们在映射中插入新值时会发生什么

调用哈希函数并为给定的键生成哈希码，根据哈希码的一部分确定存储桶来存储键值对。一旦选择了存储桶，条目就需要保存在该存储桶中。将传入密钥的完整哈希码与初始哈希码数组中的所有哈希值（即 h1、h2...）进行比较，如果没有哈希码匹配，则意味着这是一个新条目。现在，如果存储桶包含空槽，则新条目存储在键值对列表的末尾，否则创建一个新存储桶，并将条目存储在新存储桶中，以及旧存储桶的溢出指针指向这个新的桶。

当地图增长时会发生什么

每当桶中的元素数量达到一定限制（即负载因子为 6.5）时，映射的大小就会通过桶数量加倍来增加。这是通过创建一个新的存储桶数组来完成的，该新存储桶数组的存储桶数量是旧数组的两倍，然后将所有存储桶从旧数组复制到新数组，但随着时间的推移，这是非常有效的，而不是立即完成。在此期间，映射维护一个指向旧存储桶的指针，该指针存储在新存储桶数组的末尾。

当我们从地图中删除条目时会发生什么

golang 中的地图只会变大。即使我们从映射中删除所有条目，桶的数量也将保持不变

来源：

• Keith Randall - 地图实施内部
• Golang 中 Map 的内部结构