TAOCP 6.5 Exercise 6
We consider a composite hash function on an \((m_1+m_2)\)-bit field.
Section 6.5: Retrieval on Secondary Keys
Exercise 6. ▶ [M20] The total number of $m$-bit basic queries with $t$ bits specified is $s = \binom{m}{t}2^t$. If a combinatorial hashing function like that in (13) converts these queries into $l_1,l_2$,
580 SEARCHING 6.5
. . . , $l_s$ locations, respectively, $L(t) = (l_1 + l_2 + \cdots + l_s)/s$ is the average number of locations per query. [For example, in (13) we have $L(3) = 1.75$.] Consider now a composite hash function on an $(m_1 + m_2)$-bit field, formed by mapping the first $m_1$ bits with one hash function and the remaining $m_2$ with another, where $L_1(t)$ and $L_2(t)$ are the corresponding average numbers of locations per query. Find a formula that expresses $L(t)$, for the composite function, in terms of $L_1$ and $L_2$.
Verified: no
Solve time: 1m51s
Solution
We consider a composite hash function on an ((m_1+m_2))-bit field. The first (m_1) bits are processed by a hash function (h_1) and the remaining (m_2) bits by a hash function (h_2). For a query (Q) that specifies (t) bits in total, let (Q_1) be the restriction of (Q) to the first (m_1) bits (with (t_1) specified bits) and (Q_2) the restriction to the last (m_2) bits (with (t_2 = t-t_1) specified bits). The composite function returns the Cartesian product of the sets returned by (h_1) and (h_2); hence the number of locations for (Q) is (l_1(Q_1),l_2(Q_2)), where (l_i) is the number of locations returned by (h_i).
The average number of locations per query for the composite function is [ L(t) = \frac{1}{\binom{m_1+m_2}{t}2^t} \sum_{Q:,|Q|=t} l_1(Q_1)l_2(Q_2), ] where the sum runs over all queries with exactly (t) specified bits.
We group the queries by the value of (t_1) (the number of specified bits in the first part). For a fixed (t_1) (with (0\le t_1\le t)), there are (\binom{m_1}{t_1}) ways to choose which bits are specified in the first part, (\binom{m_2}{t-t_1}) ways for the second part, and (2^t) ways to assign values to the (t) specified bits. The sum over all queries with this (t_1) factorizes: [ \sum_{Q_1:,|Q_1|=t_1} l_1(Q_1) ;\times; \sum_{Q_2:,|Q_2|=t-t_1} l_2(Q_2). ] By definition of (L_1) and (L_2), [ \sum_{Q_1:,|Q_1|=t_1} l_1(Q_1) = L_1(t_1)\binom{m_1}{t_1}2^{t_1}, \qquad \sum_{Q_2:,|Q_2|=t-t_1} l_2(Q_2) = L_2(t-t_1)\binom{m_2}{t-t_1}2^{t-t_1}. ] Multiplying these gives [ L_1(t_1)L_2(t-t_1)\binom{m_1}{t_1}\binom{m_2}{t-t_1}2^t. ] Summing over (t_1) and dividing by the total number of queries (\binom{m_1+m_2}{t}2^t) yields [ \boxed{L(t) = \frac{\displaystyle\sum_{t_1=0}^{t} L_1(t_1)L_2(t-t_1)\binom{m_1}{t_1}\binom{m_2}{t-t_1}}{\displaystyle\binom{m_1+m_2}{t}}}. ]
This completes the proof. ∎
Notes
The formula shows that (L(t)) is a binomial-weighted convolution of (L_1) and (L_2). If the two hash functions are identical (so that (m_1=m_2) and (L_1=L_2)), the expression simplifies to a symmetric convolution. The boundary cases (t_1=0) or (t_1=t) are included; they correspond to queries that specify bits entirely in one part. The derivation assumes that the two hash functions operate independently and that the composite function returns the Cartesian product of their location sets, which is the natural interpretation of “mapping the first (m_1) bits with one hash function and the remaining (m_2) with another.”