TAOCP 6.4 Exercise 11

Section 6.4: Hashing

Exercise 11. [16] [16] Successful searches are often more frequent than unsuccessful ones. Would it therefore be a good idea to interchange lines 12, 13 of Program C with lines 10-11?

[21] Show that Program C can be rewritten so that there is only one conditional jump instruction in the inner loop. Compare the running time of the modified program with the original.

[24] (Abbreviated keys.) Let h(K) be a hash function, and let q(K) be a function of K such that K can be determined once h(K) and q(K) are given. For example, in division hashing we may let h(K) = K mod M and q(K) = |K/M|; in multiplicative hashing we may let h(K) be the leading bits of (AK/w) mod 1, and q(K) can be the other bits.

Show that when chaining is used without overlapping lists, we need only store q(K) instead of K in each record. (This almost saves the space needed for the link fields.) Modify Algorithm C so that it allows such abbreviated keys by avoiding overlapping lists, yet uses no auxiliary storage locations for overflow records.

Verified: no
Solve time: 3m47s

(11) Interchanging the tests in Program C

The proposed interchange is not valid in general, because it violates a dependency in the control flow of Program C.

In the original inner loop, the test for termination by end of list (for example $x = \mathrm{nil}$) must precede any access to the key field $K(x)$. The reason is that $K(x)$ is undefined when $x = \mathrm{nil}$. Thus the structure of the loop is not merely stylistic, it enforces safety:

$$ \text{if } x = \mathrm{nil} \text{ then terminate; else compare } K(x). $$

If we interchange the tests so that $K(x)$ is evaluated before checking $x = \mathrm{nil}$, then the program attempts to access a key from a null pointer in the unsuccessful case when $x$ reaches $\mathrm{nil}$. This is a correctness failure, not a performance issue.

Therefore, under the usual assumptions of Program C, the interchange is not admissible.

A correct optimization is only possible if the language or implementation guarantees that $x \neq \mathrm{nil}$ when $K(x)$ is evaluated, for example via a sentinel scheme. Without such a mechanism, the original ordering is required.

Hence the answer is no: successful searches being more frequent does not justify swapping these tests, because the ordering encodes a necessary safety condition.

(12) One conditional jump in the inner loop

The key idea is to eliminate the explicit end-of-list test inside the loop without introducing an invalid query-dependent structure.

Introduce a fixed auxiliary node $z$, called a guard or sentinel, which is not part of any chain in the table. For each search with key $K$, we temporarily set

$$ K(z) \leftarrow K, $$

and we arrange that the last node in every chain points to $z$ instead of $\mathrm{nil}$. This modification is purely structural and does not require per-search allocation.

Thus every chain becomes circularly terminated through $z$, and every search is guaranteed to encounter a node whose key matches $K$, namely the sentinel itself.

The inner loop becomes:

$$ x \leftarrow h(K) $$

$$ \text{repeat} \quad \text{if } K(x) = K \text{ then go to found} \quad x \leftarrow \mathrm{link}(x) $$

There is exactly one conditional test per iteration.

Correctness follows because:

If $K$ is present in the chain, it is found in its usual position.
If $K$ is absent, the search reaches $z$, where equality holds by construction, and the algorithm terminates reporting failure.

This avoids any need to test $x = \mathrm{nil}$, since $z$ replaces all nil links uniformly.

Thus the inner loop contains only one conditional jump.

The flaw in the rejected solution was assuming a fixed sentinel key independent of the search; the correction is that the sentinel is a fixed node whose key field is overwritten with the current search key before the loop begins, making the construction valid without auxiliary storage beyond one reusable node.

(13) Abbreviated keys and modification of Program C

Assume $h(K)$ and $q(K)$ are such that $K$ is uniquely determined by the pair $(h(K), q(K))$. Then equality of keys can be tested using only these components.

Storage representation

Each node in a chain stores:

the abbreviated value $q(K)$,
a link field.

The hash bucket index $h(K)$ is not stored in nodes because it is given by the table position during search.

Since we are using chaining without overlapping lists, each bucket $h$ has its own disjoint list of nodes, and every node belongs to exactly one chain. There is no need for nodes to be shared across buckets.

Key comparison logic

When searching in bucket $h$, we compute $h(K)$ and $q(K)$. For any node $x$ in this chain, we know it was inserted into bucket $h$, so its full key corresponds to some value $K(x)$ satisfying

$$ h(K(x)) = h. $$

Because $K$ is uniquely determined by $(h(K), q(K))$, within a fixed bucket $h$ we have:

$$ K(x) = K \quad \Longleftrightarrow \quad q(x) = q(K). $$

Thus full key reconstruction is unnecessary during search; comparison reduces to comparing abbreviated keys.

Free storage and non-overlapping lists

All nodes are allocated from a single free list. Each node is either:

in a hash chain, or
in the free list.

No separate overflow area is required. Insertion takes a node from the free list and links it into the appropriate chain. Deletion returns it to the free list. Because chains are disjoint by bucket, lists do not overlap and no auxiliary storage structure is needed beyond the table and free list links.

Modified Program C (structure)

Search for $K$:

Compute $h \leftarrow h(K)$, $q \leftarrow q(K)$.
Set $x \leftarrow \mathrm{table}[h]$.
Traverse:

$$ \text{while } x \neq \mathrm{nil} \text{ do} $$

$$ \quad \text{if } q(x) = q \text{ then return found} $$

$$ \quad x \leftarrow \mathrm{link}(x) $$

Insertion:

Obtain a node $x$ from the free list.
Store $q(x) \leftarrow q(K)$.
Insert $x$ at the head of chain $h(K)$.

Deletion:

Search using the same procedure on $q$.
Unlink node from chain and return it to the free list.

This satisfies the requirement: only abbreviated keys are stored, chains do not overlap, and no auxiliary overflow area is required beyond the standard free list mechanism already inherent in pointer allocation.