I was in an interview and I was asked about hashtable and I had to explain structural chaining.
I was asked how to search for an element in the linked list with O(1) complexity.
Can we actually find with O(1)?
Thanks
问问题
2929 次
3 回答
9
不，绝对不是。链表没有快速找到项目的巧妙方法 - 它是 O(n)。
如果您有足够好的哈希码，则在哈希表中搜索只需 O(1)。如果您所有的密钥都具有相同的哈希码，那么无论您使用什么寻址方案，它都是 O(n)。
于 2013-02-19T19:17:09.470 回答
6
除非您在其他结构中保留对链表中节点的引用，否则您无法在 O(1) 中访问链表中的元素。这是因为链表保留了对链表头的引用，并且必须遍历每个下一个元素以找到请求的元素，结果为 O(n)。
于 2013-02-19T19:17:15.727 回答
0
不，您不能在 O(1) 复杂度内搜索链表。
Hashtable 创建具有相同哈希值的元素的结构链或链表。
如果散列是均匀分布的（好的散列），那么散列表将具有 O(1) 的搜索元素复杂度。哈希表有桶，每个桶都可以从哈希值访问，然后每个桶包含具有相同哈希值的元素的链表。
于 2013-02-19T19:20:16.880 回答