Perfect Hashing: FKS Method: Two-Level Hashing

[This page is auto-generated; please prefer to read the article’s PDF Form.]

[Prev] [Up] [Next]

Two-Level Hashing

Above method does help us to ﬁnd a collision-free function in simple steps quickly. But its drawback is that it requires the hashtable to have size m in O(n²), which may be acceptable only when n is small enough. To solve this issue, we use two level of hashing whenever n is not suﬃciently small. The level-1 hash-function h₁ (subscript ‘1’ indicates level-1) maps the n keys of S to ℤm. We will use S_i to denote the set of keys which get mapped to slot i by h₁, and s_i to denote |S_i|, for each i ∈ ℤm.

For any slot i with s_i ≥ 2, there are collisions. To handle such collisions, we use level-2 hashtables T_i, one for each slot i. For each slot with s_i ≥ 2, we map its s_i keys to hashtable T_i, using a collision-free hash-function h_2,i (subscript ‘2’ indicates level-2). Using the method from the last section, we can search for a collision-free function, given the set of keys S_i. That is, we ﬁrst choose a 1∕m_i-Universal class with table-size m_i = si(si − 1) and search in it for the function which is collision-free for keys in S_i. For the h_2,i function thus found, we will store its necessary details somewhere, to allow its reconstruction later.

For slots with s_i = 1, the table T_i has a single key and hence does not require hashing. For slots with s_i = 0, table T_i is simply empty.

To lookup any key x, we ﬁrst compute i ← h₁(x). If s_i ≥ 2, we compute j ← h_2,i(x). Else if s_i = 1,j ← 0. We can then return the key from the level-2 hashtable T_i, from its slot j. If s_i = 0, we conclude that the key is not found. Note that if the lookups may also be performed for keys outside the static set S, we must also compare the key thus found with key x to ensure they are equal. Because, other keys outside of set S may still map to the same location as any key from S.

To implement this approach, we don’t need to keep a level-1 hashtable, and level-2 hashtables (T_i) separately. We can simply maintain a single table T which is a concatenation of tables T₀,T₁,T₂,…,T_m−1, in that order. The oﬀsets of all these T_i tables in T will be calculated and stored somewhere. So, the slot j of table T_i is located at this index of T: (oﬀset of T_i) + j.

Number of elements required in T, corresponding to each T_i,i ∈ ℤm is:

{ si, si = 0 or 1 ei = si(si − 1), si ≥ 2

Note that, for s_i ≥ 2, e_i = si(si − 1) ≤ s_i². Also, for s_i = 0 or 1, e_i = s_i = s_i². Thus, the total number of elements in T are:

∑ ∑ ei ≤ s2i i∈ℤm i∈ℤm

The last section’s method required space in O(n²). What can we say about the space complexity of table T? Note that if h₁ maps all n keys to one slot, ∑ i∈ℤm s_i² = n², and if it maps each to a diﬀerent slot, ∑ i∈ℤm s_i² = n.

We can take help from Corollary 4 in [3]. We can search for h₁ in a 1∕m-Universal class (𝜖 = 1∕m). That corollary then ensures that for at least half of the functions in the class, ∑ i∈ℤm s_i² has the given bound:

∑ s2i < 2n-(n-−-1) + n i∈ℤm m

Choosing m = n, we get the bound as 3n − 2, which is O(n) and hence very useful. It tells that at least half of the functions in the class will keep the table T size within 3n. So, we can randomly select a function from this class and hash all the keys from S to see if this 3n bound is met. We can repeat until we ﬁnd such a function, and then use it as h₁.

We could thus create an injective (“collision-free”) mapping of an arbitrary set of n keys to the indices in table T, which are at most 3n integers {0,1,2,...,3n − 1}. This is an interesting achievement of the FKS method.

[Prev] [Up] [Next]