TAOCP 6.4 Exercise 5
Let a FORTRAN identifier be a string $K = c_1 c_2 \dots c_n$ with $1 \le n \le 10$, and let the proposed hash function be h(K) = \text{leftmost byte of } K.
Exercise 5. [15] [15] Mr. B. C. Dull was writing a FORTRAN compiler using a decimal MIX computer, and he needed a symbol table to keep track of the names of variables in the FORTRAN program being compiled. These names were restricted to be at most ten characters in length. He decided to use a hash table with M = 100, and to use the fast hash function h() = leftmost byte of K. Was this a good idea?
Verified: yes
Solve time: 1m20s
Solution
Let a FORTRAN identifier be a string $K = c_1 c_2 \dots c_n$ with $1 \le n \le 10$, and let the proposed hash function be
$$ h(K) = \text{leftmost byte of } K. $$
This function depends only on $c_1$. For any two keys $K = c_1 c_2 \dots c_n$ and $K' = c_1 d_2 \dots d_m$, equality $c_1 = c'_1$ implies
$$ h(K) = h(K'). $$
Thus all keys sharing the same first character map to the same hash value, regardless of the remaining up to nine characters.
In a typical symbol table for a compiler, identifiers are not constrained to have uniformly distributed first characters, and many distinct variable names begin with the same letter. For each fixed first character $c_1$, the entire set of identifiers with that prefix collapses to a single hash value. Consequently, the effective number of distinct hash values is bounded by the number of possible values of a single byte, not by the intended table size $M = 100$.
Since most of the information in $K$ is discarded, the distribution of $h(K)$ is determined entirely by the frequency distribution of first characters in the source program. Any imbalance in that distribution produces corresponding clustering in the table, and collisions occur whenever two identifiers share the same initial character.
The restriction $M = 100$ does not mitigate this effect, since the mapping does not utilize the remaining structure of the key and therefore cannot spread keys within the available address space.
Therefore the method fails to use the available entropy in the keys and produces systematic clustering driven only by leading-character frequencies.
This is not a good idea. ∎