Problem Detail: To prevent collisions, hash tables with open addressing use a methodology to chain the contents. Why can’t we use another hash table allocated to each slot of the primary hash table?
Asked By : user1675999
Answered By : jbapple
The method you propose is, as far as I know, the historically first one for “perfect” hashing in linear space. In perfect hashing, lookup takes $O(1)$ time in the worst-case. (Recall that in most simple hash tables, lookup takes $O(1)$ time only in expectation.) The idea is to use chaining (rather than open addressing), but make each chain a hash table of size $Omega(m^2)$ where $m$ is the number of items in the bucket. This is sometimes called “FKS”, after the initials of the inventors. Here are some freely available resources:
- “Universal and Perfect Hashing” by Avrim Blum
- “Storing a Sparse Table with $O(1)$ Worst Case Access Time” by Fredman et al.
- “Dynamic perfect hashing” (Wikipedia) supports dynamic insertion and deletion with expected amortized $O(1)$ time, in addition to (like other perfect hashing algorithms) $O(1)$ worst-case lookup time.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/6348 Ask a Question Download Related Notes/Documents
