Can hash tables really be O(1)
- by drawnonward
It seems to be common knowledge that hash tables can achieve O(1) but that has never made sense to me. Can someone please explain it?
A. The value is an int smaller than the size of the hash table, so the value is its own hash, so there is no hash table but if there was it would be O(1) and still be inefficient.
B. You have to calculate the hash, so the order is O(n) for the size of the data being looked up. The lookup might be O(1) after you do O(n) work, but that still comes out to O(n) in my eyes.
And unless you have a perfect hash or a large hash table there are probably several items per bucket so it devolves into a small linear search at some point anyway.
I think hash tables are awesome, but I do not get the O(1) designation unless it is just supposed to be theoretical.