戈朗地图的O表现如何? [英] What is the Big O performance of maps in golang?

问题描述

go语言规范的地图类型"部分描述了该语言的界面和一般用法地图类型和The Go Blog上的行动中的地图" 随便提到哈希表和快速查找，添加和删除".

The "Map types" section of the go language specification describes the interface and general usage of map types and the "Go maps in action" post on The Go Blog casually mentions hash tables and "fast lookups, adds, and deletes".

当前runtime/hashmap.go源代码将其实现描述为哈希表(通常在O(1)中摊销)；但是，在语言规范或其他材料中我看不到任何性能特征(例如Big O性能)的保证.

The current runtime/hashmap.go source code describes its implementation as a hashtable (which are typically amortized O(1)); however, I don't see any guarantee of performance characteristics (such as Big O performance) in the language specification or other materials.

go语言是否为地图类型提供任何性能保证(例如，恒定时间插入/查找/删除?)或仅提供 interface 保证? (与Java语言相比，接口和实现明显分开.)

Does the go language make any performance guarantees (e.g. constant-time insertion/lookup/deletion?) for map types or only interface guarantees? (Compare to the Java language where interfaces and implementations are clearly separate.)

推荐答案

语言参考并未明确保证地图的性能.映射的执行有一个隐含的期望，就像您期望哈希表执行一样.我看不出如何能保证避免模糊地指定或不准确.

The language reference doesn't make explicit guarantees about the performance of maps. There's an implicit expectation that maps perform like you expect hash-tables to perform. I don't see how a performance guarantee would avoid being either vaguely specified or inaccurate.

Big-O复杂度是描述地图运行时间的一种糟糕方法:实际上，实际时钟时间是相关的，而复杂度则无关紧要.从理论上讲，具有有限域键(例如ints)的映射在空间和时间上通常为O(1)，具有无限域键(例如字符串)的映射需要散列，并且相等性测试的详细信息包括在成本中，这使得插入和查找的平均情况最好为O(N log N)(因为键的平均大小必须至少为O(log N)才能构造具有N个条目的哈希表.除非您正确获得这些详细信息，否则规范将是不准确的，正确实现它的好处显然不值得.

Big-O complexity is a poor way to describe run-times for maps: practically speaking the actual clock time is relevant and complexity isn't. Theoretically, maps with keys from finite domains (such as ints) are trivially O(1) in space and time, and maps with keys with infinite domains (such as strings) require hashing and the specifics of equality testing to be included in the cost, which makes inserts and lookups best case O(N log N) on average (since the keys have to be at least O(log N) in size on average to construct a hash table with N entries. Unless you get these details right in the specification it's going to be inaccurate, and the benefit of getting it right isn't clearly worth it.

要保证实际运行时间而不是复杂性，这也很困难:目标计算机种类繁多，还有缓存和垃圾回收的混杂问题.

To provide guarantees about actual run-time rather than complexity it'd be also be difficult: there's a wide range of target machines, as well as the confounding problems of caching and garbage collection.

这篇关于戈朗地图的O表现如何?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！