0

I have read wikipedia, since accessing a hast table is just simply by array index like hast_table[index], so it should be O(1), Why the worst case of hast table's time complexity is O(n). And what is the worst case?

Alexander
  • 59,041
  • 12
  • 98
  • 151
Sato
  • 8,192
  • 17
  • 60
  • 115
  • Worst-case: all elements are hashed into the same bucket. The worst-case in general is the consequence of limited memory (or having an infinite amound of memory: non-perfect hashing). But take my comment with a grain of salt as analysis can be much more complex, e.g. [cuckoo hashing](https://en.wikipedia.org/wiki/Cuckoo_hashing) + [dearmortization](https://en.wikipedia.org/wiki/Amortized_analysis) strategies. – sascha Sep 05 '17 at 00:13
  • https://www.youtube.com/watch?v=h2d9b_nEzoA – Alexander Sep 05 '17 at 00:15

1 Answers1

1

A hash table of capacity 1, that used side chaining, degenerates into a linked list, causing lookups to require linear searches across the single bucket of the table.

https://en.wikipedia.org/wiki/Hash_table#Separate_chaining_with_linked_lists

Alexander
  • 59,041
  • 12
  • 98
  • 151