TAOCP 6.4 Exercise 12

We first recall the structure of Program C (linear probing) as given in the text.

taocpmathematicsalgorithmsvolume-3medium

Section 6.4: Hashing

Exercise 12. ▶ [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.

Verified: no
Solve time: 6m48s

Solution

We first recall the structure of Program C (linear probing) as given in the text. The inner loop of the original program (lines 10-13 in the book’s listing) is

10  CMPA TABLE,X
11  JE   SUCCESS
12  LDA  TABLE,X
13  JAZ  FAILURE

followed by instructions to reload the search key, increment the index, and jump back to line 10.
Thus each probe that finds an occupied non‑matching cell executes two conditional jumps (JE and JAZ) and two LDA instructions.

Modified program with one conditional jump

Reserve one extra cell in the table, say TABLE[M], which is kept empty at all times except during a search.
Before entering the loop we plant the search key in this sentinel cell:

STA  TABLE,M          (2u)   * plant sentinel *

The inner loop then becomes

10  CMPA TABLE,X      (2u)
11  JE   FOUND        (1u)
12  INCX              (1u)
13  JMP  10B          (1u)

Only one conditional jump (JE) appears in the loop.
When a match occurs we branch to FOUND, where we distinguish a real match from the sentinel:

FOUND CMPX =M=        (2u)
      JNE  SUCCESS    (1u)
      JMP  FAILURE    (1u)

Running‑time comparison

We use the standard MIX instruction times (Section 1.3.1):
LDA/STA/CMPA = 2u, conditional jumps = 1u, INCX/JMP = 1u.

Let (P) be the number of probes made (the terminal probe is the (P)-th).

Original program

  • Non‑terminal probe (occupied, no match):
    CMPA (2) + JE (1) + LDA (2) + JAZ (1) + LDA (2) + INCX (1) + JMP (1) = 10u.
  • Terminal successful probe: CMPA (2) + JE (1) = 3u.
  • Terminal unsuccessful probe: CMPA (2) + JE (1) + LDA (2) + JAZ (1) = 6u.

Hence
[ T_{\text{orig}}^{\text{succ}} = 10(P-1) + 3 = 10P - 7, \qquad T_{\text{orig}}^{\text{unsucc}} = 10(P-1) + 6 = 10P - 4. ]

Modified program

  • Setup: STA TABLE,M = 2u.
  • Non‑terminal probe: CMPA (2) + JE (1) + INCX (1) + JMP (1) = 5u.
  • Terminal probe: CMPA (2) + JE (1) = 3u, then
    successful: CMPX (2) + JNE (1) = 3u;
    unsuccessful: CMPX (2) + JNE (1) + JMP (1) = 4u.

Hence
[ T_{\text{mod}}^{\text{succ}} = 2 + 5(P-1) + 3 + 3 = 5P + 3, \qquad T_{\text{mod}}^{\text{unsucc}} = 2 + 5(P-1) + 3 + 4 = 5P + 4. ]

Comparison
For (P = 1) the original program is faster (3u vs 8u for successful, 6u vs 9u for unsuccessful) because the sentinel setup overhead dominates.
For (P \ge 2) the modified program is faster: e.g. for (P=2), original successful = 13u, modified = 13u (tie); for (P=3), original = 23u, modified = 18u. Since practical hash tables operate with average probe lengths (> 1) (typically (1/(1-\alpha)) for load factor (\alpha)), the modified program yields a substantial speedup for both successful and unsuccessful searches.

The modified program requires the table to be maintained with exactly one permanently empty cell (the sentinel). This is a mild restriction (load factor (\le M/(M+1))) that is compatible with linear probing.
This completes the proof. ∎