golang中地图的大O性能是多少？
发布时间：2020-12-16 19:22:28 所属栏目：大数据 来源：网络整理
导读：“Map types” section of the go language specification描述了地图类型的界面和一般用法以及 “Go maps in action” post on The Go Blog随便提及的哈希表和“快速查找,添加和删除”. current runtime/hashmap.go source code将其实现描述为哈希表(通常是
|
“Map types” section of the go language specification描述了地图类型的界面和一般用法以及
“Go maps in action” post on The Go Blog随便提及的哈希表和“快速查找,添加和删除”.
current go语言是否为地图类型或仅提供接口保证提供任何性能保证(例如,恒定时间插入/查找/删除？)？ (与接口和实现明显分开的Java语言相比.)
语言参考没有明确保证地图的性能.有一种隐含的期望,即地图的执行方式与您希望执行的哈希表类似.我不知道性能保证如何避免模糊指定或不准确.
Big-O复杂度是描述地图运行时间的一种不好的方式：实际上,实际的时钟时间是相关的,而复杂性则不然.从理论上讲,具有来自有限域(例如整数)的密钥的映射在空间和时间上通常是O(1),而具有无限域(例如字符串)的密钥的映射需要散列并且相等性测试的细节包括在成本中,这使得插入和查找最佳情况O(N log N)平均(因为密钥平均大小必须至少为O(log N),以构造具有N个条目的哈希表.除非您在规范它将是不准确的,并且实现正确的好处并不值得. 为了保证实际的运行时而不是复杂性,它也很难：有各种各样的目标机器,以及缓存和垃圾收集的混淆问题. （编辑：李大同） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |