java - Searching a linked list with O(1)

Question

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

Answer 1

不，绝对不是。链表没有快速找到项目的巧妙方法 - 它是 O(n)。

如果您有足够好的哈希码，则在哈希表中搜索只需 O(1)。如果您所有的密钥都具有相同的哈希码，那么无论您使用什么寻址方案，它都是 O(n)。

Answer 2

除非您在其他结构中保留对链表中节点的引用，否则您无法在 O(1) 中访问链表中的元素。这是因为链表保留了对链表头的引用，并且必须遍历每个下一个元素以找到请求的元素，结果为 O(n)。

Answer 3

不，您不能在 O(1) 复杂度内搜索链表。

Hashtable 创建具有相同哈希值的元素的结构链或链表。

如果散列是均匀分布的（好的散列），那么散列表将具有 O(1) 的搜索元素复杂度。哈希表有桶，每个桶都可以从哈希值访问，然后每个桶包含具有相同哈希值的元素的链表。

http://www.algolist.net/Data_structures/Hash_table/Chaining