golang 中的 map 的 Big O 性能是什么？

Question

"Map types"部分 介绍了go语言中map类型的接口和一般用法，而"Go maps in action"文章则随意提到了哈希表和“快速查找、添加和删除”。

当前的runtime/map.go源代码将其实现描述为哈希表（通常是摊销O(1)）; 然而，我没有在语言规范或其他材料中看到任何性能特征的保证（如大O性能）。

go语言是否对map类型做出任何性能保证（例如常数时间插入/查找/删除）或仅有接口保证？（与Java语言相比，其中界面和实现明确分离。）

- maerics

---

请查看此页面：Issue 3885: profile and tune map code (旧链接)。 - icza

哈希不是O(1)，例如对于字符串。 - Paul Hankin

Answer 1

语言参考手册并没有对地图性能作出明确保证。隐含的期望是地图的性能与哈希表的性能相似。我不明白性能保证如何避免含糊不清或不准确。

大O复杂度是描述地图运行时间的不好方式：实际上时钟时间是相关的，而复杂度则无关紧要。理论上，键来自有限域（例如整数）的映射在空间和时间上都是微不足道的O(1)，而键来自无限域（例如字符串）的映射需要散列以及包括相等测试在内的成本，这使得插入和查找平均情况下的最佳情况是O(N log N)（因为键至少平均大小为O(log N)，才能构造具有N个条目的哈希表。除非在规范中正确处理这些细节，否则它将是不准确的，并且获得正确的好处并不明显值得。

提供关于实际运行时间而不是复杂度的保证也很困难：有各种各样的目标机器，还有缓存和垃圾收集的混淆问题。

- Paul Hankin

---

“平均情况下，查找是O(N log N)”这完全是错误的。在正确加载哈希映射表的情况下，查找是O(1)。如果哈希函数非常糟糕且不幸，所有键都在一个桶中，那么它将变成O(n)，但在Go语言中实际上从未发生过。请记住，N是元素数量。 - Laurent Demailly

@LaurentDemailly 您使用了关于哈希表查找平均比较次数的陈述（它是O(1) - 我同意），但我的答案表明“比较次数”是一种性能度量选择，这在实际（时钟）运行哈希映射时很难或至少不清晰。如果哈希映射中有N个元素，则每个元素都需要大约log(n)位才能使它们全部不同，因此哈希和比较时间应该至少像log(N)那样增长。这些技术细节可能会使准确的语言参考陈述变得困难。 - Paul Hankin

即使 k O(1) 的常数部分略微增长 log(n)，仍然是 O(1) / 与 N 相比可以忽略不计。而且无论如何都与 O(N log N) 没有任何关系。请更正您的答案，因为人们正在重复他们在这里看到的内容而没有理解。 - Laurent Demailly

Answer 2

准确来说，哈希表的性能是O(1 + n/k)，用于解决碰撞，其中n/k指的是负载因子。Go规范声明映射中键的数量是非限制性的，因此它们需要进行动态调整大小，并进行部分重新哈希以在增长或缩小时保持负载因子。这意味着查找常量大小映射可以轻松地实现近似O(1)，但对于大量插入或删除操作甚至不能从理论上保证。这些操作需要重新分配，部分重新哈希和可能的垃圾回收以保持负载因子和合理的内存使用率。

- Uvelichitel

---

感谢提供详细信息。我想要的应该是有关甚至一般特征的文档保证，例如各种操作的对数时间与常数时间之间的区别。 - maerics

正如您可以在源代码中读到的那样 // 当哈希表增长时，我们会分配一个新的桶数组 // 大小是原来的两倍 - Uvelichitel

在我看来，当顺序插入N个项目到新的映射中时，可以假设为对数时间。然后在查找方面接近O(1)。 - Uvelichitel

当然，不要忘记你可以为 make 提供一个大小提示，以便在你知道大小（或大致大小）时跳过一些或全部重新分配。 - Dave C

Answer 3

据我所见，Go编程语言规范没有为映射类型提供任何性能保证。一般来说，哈希表的插入、查找和删除数据的时间复杂度都是O(1)；我们可以假设这对于Go的映射也是如此。

如果您担心映射的性能问题，您可以在不同负载下对代码进行基准测试，然后决定是否使用Go的映射或其他数据结构。

- Ainar-G

---

+1，吹毛求疵：摊销 O(1) - thwd

谢谢你的回答！我想知道我们是否只能假设我们会得到摊销的O(1)性能，或者是否有（或将有）任何文档保证。 - maerics