There are several techniques that guarantee that lookups will always require O(1) operations, even in the worst case.
How can I determine whether a hash table has a chance of having O(1)
operations, and possibly which techniques to use on my hash function?
The worst case happens when some malicious attacker (Mallory) deliberately gives you data that Mallory has specifically selected to make the system run slow.
Once you have picked some particular hash function, it's probably over-optimistic to assume Mallory will never find out which hash function you picked.
Once Mallory discovers which hash function you picked, if you allow Mallory to give you lots of data to be inserted into your hash table using that hash function, then you are doomed: Mallory can internally rapidly generate billions of data items, hash them with your hash function to find which data items are likely to collide, and then feed you millions of one-in-a-thousand data items that are likely to collide, leading to lookups that run much slower than O(1).
All the techniques that guarantee "O(1) lookups even in the worst case" avoid this problem by doing a little bit of extra work on each insertion to guarantee that, in the future, every possible lookup can succeed in O(1) time.
In particular, we assume (worst case) that Mallory will sooner or later discover which hash function we are using; but he only gets a chance to insert a few data items before we pick a different hash function -- tabulation hashing or some other universal hashing -- one that we specially select such that all the data we have so far can be looked up in 2 or 3 probes -- i.e., O(1).
Because we randomly select this function, we can be fairly sure that Mallory won't know what function we picked for a while.
Even if Mallory immediately gives us data that, even with this new hash function, collides with previous data,
we can then pick yet another a fresh new hash function such that, after rehashing,
all the previous data he and everyone else has fed us can now be looked up in 2 or 3 probes in the worst case -- i.e., O(1) lookups in the worst case.
It's fairly easy to randomly select a new hash function and rehash the entire table often enough to guarantee that each lookup is always O(1).
While this guarantees that each lookup is always O(1), these techniques, when inserting the Nth item into a hash table that already contains N-1 items, can occasionally require O(N) time for that insert.
However, it is possible to design the system such that,
even when Mallory deliberately gives you new data that, using the new hash function, collides with previous data, the system can accept lots of items from Mallory and others before it needs to do a full O(N) rebuild.
Hash table techniques that pick-a-new-function-and-rehash in order to guarantee O(1) lookups, even in the worst case, include:
- cuckoo hashing guarantees that each key lookup succeeds with at most 2 hash calculations and 2 table lookups.
- hopscotch hashing guarantees that each key lookup succeeds after inspecting at small number H (perhaps H=32) consecutive entries in the table.
- dynamic perfect hashing -- the 1994 paper by Dietzfelbinger is the first one I've read that pointed out that, even though it rehashes "frequently" in order to guarantee that each key lookup always succeeds with 2 hash calculations and 2 lookups, it's possible to do a full rehash so rarely that even though each full rehash uses O(n) time, the expected average cost of insertions and deletion are O(1) amortized.
Data Structures/Hash Tables