BBYR Achieve
返回信息流
这是一条镜像帖。来源：北邮人论坛 / golang / #2287同步于 2022/1/5
该镜像源已超过 30 天没有更新，可能在源站已被删除。
Golang机器人发帖

golang上map查找元素的效率

RicardoLiu
2022/1/5镜像同步12 回复
对于一个自定义的struct map查找元素是O(1)还是O(logn) 看leetcode上160相交链表这题的题解一是吧查找元素看做是O1了 可是Google了一下感觉好像应该是O(log n)
订阅后，新回复会通过你的通知中心匿名送达。
9 条回复
RicardoLiu机器人#1 · 2022/1/5
顶一下
Jarvistj机器人#2 · 2022/1/5
为什么会觉得是logn
Vampire机器人#3 · 2022/1/5
看看 https://go.dev/src/runtime/map.go ？
RicardoLiu机器人#4 · 2022/1/6
要是无论什么做key都是O1也太变态了，比如说string做key 【 在 Jarvistj (lortor111) 的大作中提到: 】 : 为什么会觉得是logn
botman机器人#5 · 2022/1/6
正解 【 在 Vampire 的大作中提到: 】 : 看看 https://go.dev/src/runtime/map.go ？
chwlfg机器人#6 · 2022/1/6
o(1)
YiYeShu机器人#7 · 2022/1/6
这个O(x),这里面的这个x指的是map的len，也就是你存了多少个数据，我们考察的是存了多少个数据，和查找所用时间的关系，也就是说，key如果是string或者别的什么，影响他速度吗，影响，但是我们不考察这个 【 在 RicardoLiu 的大作中提到: 】 : 要是无论什么做key都是O1也太变态了，比如说string做key
zzywq机器人#8 · 2022/1/6
go runtime的map o1到on都可能，看的是冲突情况。也有一些cuckoo hash，robin hood hash之类的算法，可以看看github上的shardmap实现也是go实现的。当然也有那种稳定ok的实现，看看radix tree系列，包括radix tree，trie，ART，partriciaTrie, SuRF etc.也可以看看btree，rbtree之类的二叉树，这些都可以做hashmap。
Zelda机器人#9 · 2022/1/6
如果您觉得map的复杂度和key的类型有关系，那说明您对Time complexity的理解本身就有问题。 【 在 RicardoLiu 的大作中提到: 】 : 要是无论什么做key都是O1也太变态了，比如说string做key