TAOCP 6.4 Exercise 65
Let a variable-length key $K$ be a finite sequence of MIX characters $K = c_1 c_2 \dots c_\ell,$ where each $c_i$ is an element of a fixed alphabet of radix $r$ (for MIX, typically $r = 64$ or $r = 10...
Exercise 65. [20] [20] (Variable-length keys.) Many applications of hash tables deal with keys that can be any number of characters long. In such cases we can’t simply store the key in the table as in the programs of this section. What would be a good way to deal with variable-length keys in a hash table on the MIX computer?
Verified: yes
Solve time: 1m15s
Solution
Let a variable-length key $K$ be a finite sequence of MIX characters
$K = c_1 c_2 \dots c_\ell,$
where each $c_i$ is an element of a fixed alphabet of radix $r$ (for MIX, typically $r = 64$ or $r = 100$ as in Section 6.4).
A hash function for such keys must be defined without requiring a fixed number of characters. A suitable construction is to interpret the sequence as a positional number in base $r$ and to evaluate it incrementally during a single left-to-right scan. Define
$h(K) = \bigl(\cdots((c_1 r + c_2) r + c_3)\cdots r + c_\ell\bigr) \bmod M,$
where $M$ is the table size used for hashing. This computation requires only the current accumulated value and the next character, so no storage of the full key is needed during hashing.
Let $H_i$ denote the partial value after processing $c_i$, so that $H_1 = c_1 \bmod M$ and
$H_i = (H_{i-1} r + c_i) \bmod M \quad (2 \le i \le \ell).$
Then $h(K) = H_\ell$. This recurrence matches the structure of modular polynomial evaluation and avoids overflow by reduction modulo $M$ at each step.
For storage in a MIX hash table, each entry cannot contain the entire variable-length key directly. Instead, each key is stored in a separate sequential area of memory as a contiguous block of MIX words containing its characters, terminated by a special end-of-key marker (for example, a non-alphabetic sentinel character). The hash table itself stores only a reference to the key block, implemented as the address of the first word of the stored key.
When a key $K$ is inserted, its characters are written into the next available region of the auxiliary key storage. The hash table cell at position $h(K)$ stores the pointer to this region. If collision resolution requires probing or chaining, each alternative table entry similarly stores a pointer to a distinct key block, and equality tests are performed by following pointers and comparing character sequences sequentially until the terminator is reached.
During search, a probe at position $j$ retrieves a pointer to a candidate key $K'$. Equality with the search key $K$ is tested by simultaneous sequential comparison of their character streams, stopping at the first mismatch or at the terminator in both streams. This avoids any requirement that keys be aligned in length or representation within the table itself.
This scheme separates two concerns: the hash function depends only on sequential arithmetic over characters, and collision resolution depends only on pointer-based access to stored sequences. The representation supports arbitrary key length without modifying the structure of the hash table or the definition of $h(K)$.
This completes the solution. ∎