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?

Improve this question
$\endgroup$
2

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$
3
  • 1
    $\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, 2012 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, 2012 at 23:03
  • 1
    $\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, 2012 at 16:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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