Golang 地图内部实现 - 它如何在地图中搜索键？

Question

我在“Go 编程语言”中读到“可以检索给定的键......平均使用恒定数量的键比较，无论哈希表有多大。” 不过，我不确定这在内部实现方面意味着什么。这是否意味着它会搜索每个键，直到找到匹配项，或者在内部使用某种类型的二进制（或其他）搜索算法？例如，如果我有一个包含 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) 时间内。这通常是正确的，因为某些键在散列时可能会导致相同的索引，称为冲突，然后必须进行特殊处理。