# Using hash tables instead of lists for buckets in hash tables

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?

• "What would be the average case for this problem?" -- what exactly do you mean; lookup time? – Raphael Jul 5 '12 at 7:18
• – David Cary Aug 15 '16 at 4:05

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.
• 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. – edA-qa mort-ora-y Jul 4 '12 at 18:47
• @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". – JeffE Jul 7 '12 at 16:54