Swift字典按键删除时间复杂度为何是O(n)而非O(1)？

Great question! It’s totally reasonable to wonder why a hash-based structure would have an O(n) delete operation when put/get are O(1)—let’s unpack this with how Swift’s Dictionary works under the hood.

The Core Reason: Open Addressing vs. Chaining #

Most hash tables handle collisions in one of two ways:

• Chaining: Each bucket holds a linked list of elements that hash to the same index. Delete here is O(1) (find the node, unlink it from the list).
• Open Addressing: When a collision happens, the algorithm probes other buckets (via linear, quadratic, or double hashing) to find an empty spot. This is the approach Swift uses.

Why Open Addressing Makes Delete Tricky #

With open addressing, you can’t just mark a bucket as empty when you delete an element. Here’s why:

• Suppose you have elements A, B, C where B collided with A and was placed in the next bucket. If you delete A and leave that bucket empty, future lookups for C would stop at the empty bucket and incorrectly conclude C doesn’t exist.
• To fix this, Swift uses a "tombstone" marker to indicate a deleted element. But over time, tombstones accumulate and slow down lookups/inserts. When the hash table needs to clean up these tombstones (or resize), it has to rehash and reinsert surviving elements—this is the O(n) step.
• Even in non-resize scenarios, deleting an element might require shifting subsequent elements back to fill the gap (depending on the probing strategy), which can also lead to linear time in the worst case.

Tradeoffs Swift Makes #

Swift chooses open addressing over chaining because it offers better cache locality—elements are stored in contiguous memory, which makes access faster for most common operations (like get/put). The O(n) delete is a tradeoff for this overall performance gain in typical use cases.

It’s worth noting that average-case delete performance is much better than O(n)—the worst-case scenario only happens when the hash table is under heavy load or needs to perform a full cleanup of tombstones. But Apple’s official documentation lists the worst-case time complexity to be transparent about the upper bound.

内容的提问来源于stack exchange，提问作者davidchuyaya