4
$\begingroup$

Say instead of using a linked list as buckets for a hash table of size $m$, we use another hash table of size $p$ as buckets this time. What would be the average case for this problem?

I looked up perfect hashing and I got a very close algorithm, and it is $O(1)$. Can someone please clarify?

$\endgroup$
6
$\begingroup$

Using a hash table with $n$ buckets and a hash function $h_n : S \rightarrow \{0, 1, ..., n - 1\}$ , where each bucket is a hash table with $m$ buckets and a hash function $h_m : S \rightarrow \{0, 1, ..., m - 1\}$, is equivalent to a hash table wit $nm$ buckets and a hash function $h_{nm} : S \rightarrow \{0, 1, 2, ..., nm - 1\}$ where $h_{nm}(x) = mh_n(x) + h_m(x)$. In other words, using more than one level has no effect whatsoever on the complexity: it's the same as a for a garden-variety hash table.

Perfect hashing is a completely separate issue.

$\endgroup$
  • $\begingroup$ One would presume, though not mentioned in the question, that each bucket would have an independent size $m_n$. The sum of these would also be bound by the total number of items in the hashmap. $\endgroup$ – edA-qa mort-ora-y Jul 4 '12 at 18:47
  • $\begingroup$ @edA-qamort-ora-y Possibly, but that's just playing around with some of the expressions, not the answer. $\endgroup$ – Patrick87 Jul 4 '12 at 23:03
  • $\begingroup$ @Patrick87: Sure, but there is no reason that every secondary hash table has to have the same size. Suppose $n_i$ is the number of elements in the $i$th bucket of the primary hash table. If we use a random hash function $h_i \colon S \to \{0, 1, \dots, n_i^2\}$, we get constant-time lookups in linear space with high probability, not just in expectation. This scheme is sometimes called "perfect hashing". $\endgroup$ – JeffE Jul 7 '12 at 16:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.