[Solved]: Why can't we use a hash tables for collision resolving in hash tables?

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