Dynamic hash table will expand when it is full. If we simply use modulo to map hash value to the entry position, there are some properties on the data movement while expanding.
Let’s start with some questions:
- If at the very first, the table size is n, and for the entry at ith place ( k \mod n = i), what is the possible place for it after expanding?
- Can we describe the moving process?
Q1
Lemma:
n, m \in \mathcal{Z}^+, k \mod n = i \implies k \mod mn \in \{i, i+n, \dots, i+(m-1)n\} .
Proof:
k \mod n = i \implies k - n\lfloor \frac{k}{n} \rfloor = i , and k \mod mn = k - mn\lfloor \frac{k}{mn} \rfloor
So that
k \mod mn - k \mod n = n\lfloor \frac{k}{n} \rfloor - mn = k - mn\lfloor \frac{k}{mn} \rfloor = n(\lfloor \frac{k}{n} \rfloor - m\lfloor \frac{k}{mn} \rfloor)Thus, k \mod mn - k \mod n is a multiplier for n. Next, let’s take a close look at (\lfloor \frac{k}{n} \rfloor - m\lfloor \frac{k}{mn} \rfloor).
Let \alpha = \lfloor \frac{k}{mn} \rfloor, then \alpha \le \frac{k}{mn} < \alpha + 1 \implies m\alpha \le \frac{k}{n} < m( \alpha + 1) \implies m\alpha \le \lfloor \frac{k}{n}\rfloor < m( \alpha + 1) .
So we have 0 \le \lfloor \frac{k}{n}\rfloor -m\alpha = \lfloor \frac{k}{n} \rfloor - m\lfloor \frac{k}{mn} \rfloor < m. QED.
And we can see that if we expand hash table times, data will always move to larger place. This property is so important.
Q2
Let’s use a concrete example to illustrate the analysis process. Suppose we expand the hash table from n to 2n, then to 4n.
Our knowledge database initially is key k in ith place: \{k \mod n = i\}.
First, we expand to 2n. According to the lemma, i might go to i or i+n.
- Given i goes to i, which means that it does not move, k \mod 2n = i. Then our knowledge database is also extended: \{k \mod n = i, k \mod 2n = i\}. Using the two knowledge, we have k \mod 4n \in \{i, i+n, i+2n, i+3n\} \cap \{i, i+2n\}=\{i, i+2n\}.
- Given i goes to i+n, which means that k \mod 2n = i+n. Then our knowledge database is also extended: \{k \mod n = i, k \mod 2n = i+n\}. Using the two knowledge, we have k \mod 4n \in \{i, i+n, i+2n, i+3n\} \cap \{i, i+n+2n\}=\{i+n, i+3n\}.