dictionary - Golang map 内部实现 - 它如何在 map 中搜索键？

Question

我在“Go 编程语言”中读到“可以检索给定的键......平均使用恒定数量的键比较，无论哈希表有多大。”不过，我不确定这在内部实现方面意味着什么。这是否意味着它会搜索每个键，直到找到匹配项或内部使用某种类型的二进制(或其他)搜索算法？

例如，如果我有一个包含 2,000 个键的映射，它“平均”是否需要查看 1,000 个才能找到匹配项，还是只需要查看 11 (log2 n) 个，就像使用二分搜索一样？

Answer 1

map 被实现为哈希表。有很多地方可以解释散列； Here's你可以运行一个很好的可视化。

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

您可以从这段代码中学到很多类通常不会涵盖的一件事，那就是如何在内部调整 map 大小时不使迭代器失效。