Why map delete is expected O(1)
Updated
Delete hashes, finds the pair in that bucket, and unlinks it. Expected O(1) under the same assumptions as get. Worst case is walking a long collision chain.
What to focus on
Some implementations leave a tombstone so probes still work. Size still drops. Amortized resize-down is optional.
Worked examples
present
a = [4, 1, 9] as {4:2,1:8,9:3}, delete 1- hash 1, unlink
Result: expected O(1)
absent
a = [4, 1, 9], delete 8- hash 8, miss the bucket
Result: expected O(1) miss
worst chain
a = [4, 1, 9] all in one bucket, delete 9- walk the chain
Result: O(chain length), up to O(n)
Try it
Write deleteCost(m, k). m is the hash map. k is the key being deleted. Return expected O(1) for a hit or a miss on a short chain. Name the O(n) chain case. a = [4, 1, 9] as {4:2,1:8,9:3}, delete 1 → expected O(1). a = [4, 1, 9], delete 8 → expected O(1) miss. a = [4, 1, 9] all in one bucket, delete 9 → O(chain length), up to O(n).
keys are integers. The map is non-empty.