TAOCP 6.4 Exercise 21
No, the variable \(N\) should not be decreased.
Exercise 21. ▶ [20] Suppose that we wish to delete a record from a table constructed by Algorithm D, marking it “deleted” as suggested in the text. Should we also decrease the variable $N$ that is used to govern Algorithm D?
Verified: no
Solve time: 1m46s
Solution
No, the variable (N) should not be decreased.
In Algorithm D (double hashing), the probe sequence for a key (K) is
(h_1(K),; (h_1(K)+h_2(K))\bmod M,; (h_1(K)+2h_2(K))\bmod M,;\ldots)
and the search continues until an empty slot is encountered.
A slot that has been marked “deleted” is not empty; it must be treated as occupied during the search because the desired key might reside further along the probe chain.
Therefore, the number of non‑empty slots (those that are either occupied by an active record or marked “deleted”) is the quantity that determines the length of probe sequences and the effective load factor of the table.
The variable (N) in Algorithm D is used to govern the algorithm,it represents this count of non‑empty slots. When a record is marked “deleted,” the slot remains non‑empty, so (N) must remain unchanged. Decreasing (N) would make the load factor (N/M) smaller than the true occupancy, leading to incorrect performance estimates and potentially causing the algorithm to behave as if the table were less full than it actually is.
\boxed{\text{No}}
This completes the proof. ∎