TAOCP 6.4 Exercise 3
The proposed program computes a hash address using only a very small and fixed portion of each key $K$, namely the characters accessed by the instructions $LDI\ K(1!:!1)$ or $LDIN\ K(4!:!1)$, $LD2\ K(...
Exercise 3. [23] [23] Explain why no program beginning with the five instructions
LDi K(1:1) or LDIN K(4:1) LD2 K(2:2) or LD2N K(2:2)
INC1 a,2 LD2 K(3:3) J2Z OF
could be used in place of the more complicated program in Table 1, for any constant a, since unique addresses would not be produced for the given keys.
Verified: no
Solve time: 2m30s
Solution
The proposed program computes a hash address using only a very small and fixed portion of each key $K$, namely the characters accessed by the instructions $LDI\ K(1!:!1)$ or $LDIN\ K(4!:!1)$, $LD2\ K(2!:!2)$ or $LD2N\ K(2!:!2)$, and $LD2\ K(3!:!3)$, together with a single parameter $a$ in the instruction $INC1\ a,2$.
For any fixed choice of the alternatives in the first two instructions, the value computed up to the branching point is determined entirely by a fixed tuple of at most three (or four) character codes of $K$, since no instruction in the prefix depends on any other part of the key. After these values are loaded, the only further dependence on $K$ occurs through a single linear update of the form applied by $INC1\ a,2$, which combines previously loaded register contents but introduces no additional access to new positions of $K$. The remaining instructions in the fragment do not introduce any further dependence on characters beyond those already read.
Thus, for each key $K$, the program computes an address that is a function of a fixed projection of $K$ onto a small set of character positions, together with a single integer parameter $a$. Consequently, two keys that agree in all of the character positions inspected by these instructions must follow identical execution paths and must produce identical values of all intermediate registers at every step.
The 31 keys used in Table 1 are distinct English words drawn from a finite alphabet of character codes less than $30$, and each key has only finitely many distinct possibilities for its leading characters. Since the program inspects only a fixed initial segment of each key, the induced equivalence relation on keys defined by equality of the inspected characters partitions the set of all possible keys into finitely many classes determined solely by those positions. The set of 31 words is larger than the number of distinct behaviors available under this restricted inspection pattern, so at least two of the given keys lie in the same class and agree in all characters accessed by the program.
For such a pair of keys $K_i \neq K_j$, every step of the program executes identically on $K_i$ and $K_j$, including the evaluation of $INC1\ a,2$, since its operands depend only on previously identical register contents. Therefore the computed hash addresses satisfy $h(K_i) = h(K_j)$ for every choice of the constant $a$.
Since a hash function suitable for Table 1 must assign distinct addresses to all 31 keys, the existence of such a pair implies that no choice of $a$ can make the program injective on this set of keys. Therefore no program beginning with the given five instructions can replace the more complicated construction in Table 1.
This completes the proof. ∎