golang中map的Big O表现如何？

本篇文章向大家介绍《golang中map的Big O表现如何？》，主要包括golang，具有一定的参考价值，需要的朋友可以参考一下。

问题内容

Go 语言规范的“Map types”部分描述了 map 类型的接口和一般用法，[Go 博客上的“Go maps in action”帖子](https://blog.golang.org/go-maps-in- action)随便提到了哈希表和“快速查找、添加和删除”。

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

go 语言是否为映射类型或仅接口 保证提供任何 性能 保证（例如，恒定时间插入/查找/删除？）？ （与接口 和 实现 明显分开的 Java 语言相比。） __ __ __

正确答案

语言参考没有明确保证地图的性能。有一个隐含的期望，即 map 的执行方式与您期望的哈希表执行方式一样。我看不出性能保证如何避免模糊指定或不准确。

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

要提供有关实际运行时间而不是复杂性的保证也很困难：目标机器范围广泛，以及缓存和垃圾收集的混杂问题。

到这里，我们也就讲完了《golang中map的Big O表现如何？》的内容了。个人认为，基础知识的学习和巩固，是为了更好的将其运用到项目中，欢迎关注golang学习网公众号，带你了解更多关于golang的知识点！