TAOCP 6.4 Exercise 23

We assume the chained hash table data structures as used in Algorithm C (Section 6.

taocpmathematicsalgorithmsvolume-3hard

Section 6.4: Hashing

Exercise 23. ▶ [33] Design an algorithm analogous to Algorithm R, for deleting entries from a chained hash table that has been constructed by Algorithm C.

Verified: no
Solve time: 2m33s

Setup

We assume the chained hash table data structures as used in Algorithm C (Section 6.4):

  • (M): number of hash buckets.
  • (\text{TABLE}[0\ldots M-1]): array of pointers to the first node of each chain; (\Lambda) indicates an empty chain.
  • Each node has two fields: (\text{KEY}) (the key value) and (\text{LINK}) (pointer to the next node in the chain, or (\Lambda)).
  • (\text{AVAIL}): pointer to the head of the available-space list (free nodes).
  • (N): integer variable counting the number of keys currently stored in the table.
  • (h(K)): hash function, with (0 \le h(K) < M) for all keys (K).

Solution

Algorithm R (Deletion from Chained Hash Table). Given a key (K), this algorithm deletes the node with (\text{KEY} = K) from the chained hash table if it exists; otherwise it reports failure.

R1. [Hash.] Set (i \leftarrow h(K)).

R2. [Initialize pointers.] Set (p \leftarrow \text{TABLE}[i]), (q \leftarrow \Lambda).
((p) traverses the chain; (q) trails (p).)

R3. [End of chain?] If (p = \Lambda), go to R7 (key not found).

R4. [Key match?] If (\text{KEY}(p) = K), go to R6.

R5. [Advance.] Set (q \leftarrow p), (p \leftarrow \text{LINK}(p)), and go to R3.

R6. [Remove node.] If (q = \Lambda), set (\text{TABLE}[i] \leftarrow \text{LINK}(p)); otherwise set (\text{LINK}(q) \leftarrow \text{LINK}(p)). Then set (\text{LINK}(p) \leftarrow \text{AVAIL}), (\text{AVAIL} \leftarrow p). Set (N \leftarrow N - 1). Exit (success).

R7. [Failure.] Signal that (K) is not in the table. Exit.

Verification

We verify the correctness of Algorithm R by proving that it maintains the hash table invariants and correctly deletes the target key when present.

Invariant during search (steps R3-R5): At the start of each iteration of step R3, the following hold:

  • The chain starting at (\text{TABLE}[i]) is unchanged from its initial state.
  • (q = \Lambda) if (p) is the first node of the chain; otherwise (q) points to the node immediately preceding (p) in the chain.
  • All nodes before (p) in the chain have keys different from (K).

Proof of invariant: Initially at step R2, (p = \text{TABLE}[i]) and (q = \Lambda), so the invariant holds vacuously (no nodes before (p)). Each execution of step R5 moves (q) to the current (p) and (p) to (\text{LINK}(p)). Since the chain is singly linked and we only follow (\text{LINK}) pointers, the new (p) is the successor of the old (p), and (q) becomes its predecessor. The key of the old (p) was checked at step R4 and found not equal to (K), so the condition on keys before (p) remains true. Thus the invariant is preserved.

Termination: The chain is finite (it ends at (\Lambda)). Since (p) advances one node per iteration, step R3 will eventually encounter (p = \Lambda) if the key is not found, or step R4 will match the key if it is present. Hence the algorithm terminates.

Case 1: Key not found. If the search reaches (p = \Lambda), step R7 is executed. By the invariant, all nodes in the chain have been examined and none matched (K). The table is unmodified, and failure is correctly reported.

Case 2: Key found. Suppose (\text{KEY}(p) = K) at step R4. By the invariant, (q) is the predecessor of (p) (or (\Lambda) if (p) is the first node). Step R6 splices (p) out of the chain:

  • If (q = \Lambda), (p) was the first node; setting (\text{TABLE}[i] \leftarrow \text{LINK}(p)) makes the chain start at (p)'s successor.
  • If (q \ne \Lambda), setting (\text{LINK}(q) \leftarrow \text{LINK}(p)) links (q) directly to (p)'s successor. In both cases the resulting chain is exactly the original chain with the node (p) removed. The node (p) is then added to the available-space list by (\text{LINK}(p) \leftarrow \text{AVAIL}), (\text{AVAIL} \leftarrow p). The count (N) is decremented. No other nodes are affected. Hence the table now contains all original keys except (K), the chain structure is preserved, and the free list gains one node. This is precisely the state that would result if (K) had never been inserted.

Boundary cases: The algorithm handles all boundary cases correctly:

  • Empty chain ((\text{TABLE}[i] = \Lambda)): step R3 immediately goes to R7.
  • Only node in chain: (q = \Lambda), (\text{LINK}(p) = \Lambda); (\text{TABLE}[i]) becomes (\Lambda), chain becomes empty.
  • First node in a longer chain: (q = \Lambda), (\text{TABLE}[i]) updated to second node.
  • Last node: (\text{LINK}(p) = \Lambda); predecessor's (\text{LINK}) becomes (\Lambda).
  • Middle node: standard splicing.

All pointer manipulations are standard linked-list deletion and are correct.

This completes the proof. ∎

Notes

The analogy with Algorithm R (deletion for double hashing) is strong: both compute a hash address, search for the key, and upon finding it modify the table structure to remove the key while updating the count (N). In open addressing (Algorithm R) the slot is marked “deleted” because removing it would break probe sequences; in chaining we can physically unlink the node because each chain is independent.