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?
- 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 + dearmortization strategies.sascha– sascha2017-09-05 00:13:57 +00:00Commented Sep 5, 2017 at 0:13
- youtube.com/watch?v=h2d9b_nEzoAAlexander– Alexander2017-09-05 00:15:38 +00:00Commented Sep 5, 2017 at 0:15
Add a comment |
1 Answer
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