我在“Go 编程语言”中读到“可以检索给定的键......平均使用恒定数量的键比较,无论哈希表有多大。”不过,我不确定这在内部实现方面意味着什么。这是否意味着它会搜索每个键,直到找到匹配项或内部使用某种类型的二进制(或其他)搜索算法?
例如,如果我有一个包含 2,000 个键的映射,它“平均”是否需要查看 1,000 个才能找到匹配项,还是只需要查看 11 (log2 n) 个,就像使用二分搜索一样?
最佳答案
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 大小时不使迭代器失效。
关于dictionary - Golang map 内部实现 - 它如何在 map 中搜索键?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/37995648/