猿问

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

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

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


GCT1015
浏览 202回答 2
2回答

翻过高山走不出你

映射被实现为哈希表。有很多地方可以解释散列; 这是一个很好的可视化,你可以运行。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您可以从这段代码中学到的一件事通常不会在很多类中涵盖,那就是如何在内部调整地图大小时不使迭代器无效。

慕桂英546537

本机地图类型使用哈希表实现。它使用键上的散列函数来生成数据数组的索引。因此,通常,大多数动作发生在 O(1) 时间内。这通常是正确的,因为某些键在散列时可能会导致相同的索引,称为冲突,然后必须进行特殊处理。
随时随地看视频慕课网APP

相关分类

Go
我要回答