TAOCP 6.4 Exercise 13

In Algorithm C (separate chaining) the hash table consists of \(M\) list headers.

taocpmathematicsalgorithmsvolume-3medium

Section 6.4: Hashing

Exercise 13. ▶ [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 \bmod M$ and $q(K)=\lfloor K/M\rfloor$; in multiplicative hashing we may let $h(K)$ be the leading bits of $(AK/w) \bmod 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: 9m12s

Solution

1. Abbreviated keys in separate chaining

In Algorithm C (separate chaining) the hash table consists of (M) list headers.
All records in the list headed by header (h) satisfy (h(K)=h).
Because the key (K) is uniquely determined by the pair (\bigl(h(K),q(K)\bigr)), the value (h(K)) is already known from the list header.
Hence it suffices to store only the abbreviated key (q(K)) in each record.
When searching for a key (K) we compute (h=h(K)) and (q=q(K)), then traverse the list for (h) comparing the stored (q) values with (q).
A match on (q) implies a match on (K).
The parenthetical remark “This almost saves the space needed for the link fields” means that the space saved by storing (q(K)) instead of the full key (K) is approximately the size of a link pointer, so the total record size ((q(K)+\text{link})) is roughly the same as the original key (K).

2. Modification of Algorithm C

Algorithm C uses a separate pool of nodes for the linked lists; this pool is auxiliary storage for overflow records.
To eliminate that auxiliary storage while still avoiding overlapping lists (i.e. each record occupies a distinct cell), we store the records directly in the hash table array, provided the table size (M) is at least the maximum number of records (N).
A free list of unused cells is maintained within the same array.

Data structure

  • An array T[0..M-1]. Each cell T[i] contains two fields:
    • T[i].Q - the abbreviated key (q(K)), or a special value EMPTY marking an unused cell.
    • T[i].LINK - an integer in ({0,\dots,M-1}) giving the index of the next cell in the chain; a value Λ (e.g. M or -1) terminates the chain.
  • A variable AVAIL pointing to the head of a stack (or linked list) of free cells.
    Initially all cells are free: AVAIL = 0, and for (i=0,\dots,M-2), T[i].LINK = i+1, T[M-1].LINK = Λ, and T[i].Q = EMPTY.

The hash function (h(K)) returns a value in (0..M-1). The chain for hash value (h) starts at cell T[h].

Search (Algorithm C1)

Given a key (K):

  1. (h \gets h(K),; q \gets q(K)).
  2. (i \gets h).
  3. While (i \neq \Lambda) and T[i].Q ≠ q do (i \gets \text{T[i].LINK}).
  4. If (i \neq \Lambda) then record found at index (i); else (K) is not in the table.

Invariant: At the start of each iteration of step 3, (i) is the index of the next record in the chain for (h) that has not yet been compared with (q).
Termination: The chain is finite (no cycles because each cell belongs to at most one chain) and (i) eventually becomes Λ.

Insert (Algorithm C2)

To insert a new key (K) (assumed not already present):

  1. (h \gets h(K),; q \gets q(K)).
  2. If T[h].Q = EMPTY then
     T[h].Q \gets q; T[h].LINK \gets Λ; return.
  3. (i \gets h).
  4. While T[i].LINK ≠ Λ do (i \gets \text{T[i].LINK}). (Find the end of the chain.)
  5. If AVAIL = Λ then signal overflow (table full).
  6. (j \gets \text{AVAIL}); AVAIL \gets \text{T[AVAIL].LINK}. (Allocate a free cell.)
  7. T[j].Q \gets q; T[j].LINK \gets Λ.
  8. T[i].LINK \gets j. (Append the new cell to the chain.)

Invariant: Before step 4, the chain starting at T[h] contains exactly the records previously inserted with hash value (h), in insertion order. Step 4 finds the last cell of that chain.
Termination: The chain length is bounded by the number of records already inserted; step 4 therefore terminates. Step 6 succeeds because (N \le M) guarantees a free cell exists.

Deletion (if required)

Removing the first cell of a chain ((i = h)) can be handled by moving the next cell’s contents into T[h] and freeing the next cell, or by marking T[h].Q = DELETED and treating DELETED as a special value during search/insert.

Verification of the required properties

  • Abbreviated keys - Only q(K) is stored in T[i].Q; (h(K)) is implicit from the chain header (h).
  • No overlapping lists - Each cell belongs to at most one hash chain (the one starting at its home address). The free list is disjoint from all hash chains.
  • No auxiliary storage - The only memory used is the array T[0..M-1] and the single variable AVAIL. The free list is embedded in T via the LINK fields of empty cells. No separate node pool is needed.

This completes the proof. ∎