"Map types"部分 介绍了go语言中map类型的接口和一般用法,而"Go maps in action"文章则随意提到了哈希表和“快速查找、添加和删除”。
当前的runtime/map.go
源代码将其实现描述为哈希表(通常是摊销O(1)); 然而,我没有在语言规范或其他材料中看到任何性能特征的保证(如大O性能)。
go语言是否对map类型做出任何性能保证(例如常数时间插入/查找/删除)或仅有接口保证?(与Java语言相比,其中界面和实现明确分离。)
"Map types"部分 介绍了go语言中map类型的接口和一般用法,而"Go maps in action"文章则随意提到了哈希表和“快速查找、添加和删除”。
当前的runtime/map.go
源代码将其实现描述为哈希表(通常是摊销O(1)); 然而,我没有在语言规范或其他材料中看到任何性能特征的保证(如大O性能)。
go语言是否对map类型做出任何性能保证(例如常数时间插入/查找/删除)或仅有接口保证?(与Java语言相比,其中界面和实现明确分离。)
准确来说,哈希表的性能是O(1 + n/k),用于解决碰撞,其中n/k指的是负载因子。Go规范声明映射中键的数量是非限制性的,因此它们需要进行动态调整大小,并进行部分重新哈希以在增长或缩小时保持负载因子。这意味着查找常量大小映射可以轻松地实现近似O(1),但对于大量插入或删除操作甚至不能从理论上保证。这些操作需要重新分配,部分重新哈希和可能的垃圾回收以保持负载因子和合理的内存使用率。
make
提供一个大小提示,以便在你知道大小(或大致大小)时跳过一些或全部重新分配。 - Dave C