我在接受采访时被问及哈希表,我必须解释结构链。
有人问我如何以 O(1) 的复杂度在链表中搜索元素。
我们真的能用 O(1) 找到吗?
谢谢
最佳答案
不,绝对不是。链接列表没有快速查找项目的巧妙方法 - 它的时间复杂度为 O(n)。
如果你有足够好的哈希码,在哈希表中搜索仅需 O(1)。如果您的所有 key 都具有相同的哈希码,那么无论您使用什么寻址方案,其复杂度都是 O(n)。
关于java - 用 O(1) 搜索链表,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/14965550/