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?
$\begingroup$
$\endgroup$
2
asked Oct 28, 2012 at 3:50
-
$\begingroup$ Your question is quite thin. Please give some detail of the data structure you are proposing here. $\endgroup$– Raphael ♦Oct 28, 2012 at 10:58
-
$\begingroup$ duplicate of "Using hash tables instead of lists for buckets in hash tables"? $\endgroup$– David CaryAug 15, 2016 at 4:02
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
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.
$\begingroup$
$\endgroup$
4
The short answer is that this is, more or less, equivalent to having one hash table. Let's say you're hashing $n$ items into $m$ slots, and each slot has its own hash table of size $c$. You propose first hashing into one of the $m$ slots using some function $h$, then hashing again into one of the $c$ slots using some function $g$. This is more or less equivalent to hashing to any of the $cm$ slots initially, with a new hash function that combines your initial two hash functions. In other words, instead of taking $h(x)$ for which of the $m$ slots to hash it to and then $g(x)$ to find the appropriate slot in the subtable, you can take $f(x) = h(x)m + g(x)$ and get the same answer with a new hash function $f$.
Something else to consider is what you do if there are collisions in the second hash. You need...some sort of methodology to chain the contents! So you're back where you started with linear probing/chaining/etc, and all you've done is increase your hash table size from $m$ to $cm$.
-
1$\begingroup$ Dynamically allocate inner hash tables, and then nested hashes are different than your suggestion. Certainly it's still true that eventually you need to break the hash inside hash recursion. $\endgroup$– rrenaudOct 28, 2012 at 16:53
-
$\begingroup$ @rrenaud In that case, why not dynamically allocate the outer one? $\endgroup$– Raphael ♦Nov 2, 2012 at 7:10
-
$\begingroup$ @Raphael: One potential reason is that--especially in multi-threaded applications it's much easier to reason about mutable structures whose identity is immutable, than those whose content and identity are both mutable. Among other things, it's very important to prevent any situation where two methods which think they are working with the same object are in fact modifying different objects, but in fact one has a reference to an object which has been superseded by the other. Never having any object get superseded avoids that problem. $\endgroup$– supercatJan 30, 2014 at 17:55
-
$\begingroup$ If hypothetically some system always used the same g(x) secondary hash function independent of the value of h(x), then that system would have the problems you describe. That may be why, when people actually do implement dynamic perfect hashing, they use a different secondary hash function for every one of the secondary hash tables. When the hash functions are chosen and re-chosen appropriately, they don't need any methodology to chain the contents. $\endgroup$ Aug 13, 2016 at 3:56