--- title: 'Collision Resolution' source: 'https://academia.sh/en/courses/data-structures/collision-resolution' course: 'Data Structures' language: en updated: '2026-08-17T18:07:49+00:00' license: 'CC BY-SA 4.0' --- # Collision Resolution Chaining and open addressing, probing strategies, clustering, the deletion problem, and a comparison of the two families. The previous lesson showed that collisions are unavoidable: if the key space is larger than the table, at least two keys fall into the same bucket. This lesson covers what to do when they do. There are two families of solutions, and both are widely used. The distinction comes down to a single question: is the colliding element stored **inside the bucket**, or **at another location in the table**? ## Chaining In **chaining**, every bucket holds a list of the elements that fall into it. The table is an array of lists; inserting means appending to the relevant list. ```python class ChainedTable: def __init__(self, bucket_count: int = 8) -> None: self._buckets: list[list] = [[] for _ in range(bucket_count)] self.comparisons = 0 # for measurement def _location(self, key) -> int: return hash(key) % len(self._buckets) def put(self, key, value) -> None: bucket = self._buckets[self._location(key)] for i, (existing, _) in enumerate(bucket): if existing == key: bucket[i] = (key, value) # existing key is updated return bucket.append((key, value)) def get(self, key): bucket = self._buckets[self._location(key)] for existing, value in bucket: self.comparisons += 1 if existing == key: return value raise KeyError(key) def delete(self, key) -> None: bucket = self._buckets[self._location(key)] for i, (existing, _) in enumerate(bucket): if existing == key: bucket.pop(i) # removing from the list is enough return raise KeyError(key) table = ChainedTable() for name, measurement in [("north", 12), ("south", 18), ("east", 7), ("west", 25)]: table.put(name, measurement) print(table.get("east")) # 7 table.delete("east") print(table.get("west")) # 25 ``` Notice that deletion is simple: the element is removed from the list, and nothing else is affected. The cost of chaining is the average number of elements per bucket — that is, the load factor. Search is finding the bucket (constant) plus scanning the list in the bucket ($O(\alpha)$). As long as the load factor is kept constant, average cost is constant. In chaining, the load factor can exceed $1$: because buckets hold lists, the table never "fills up". This flexibility allows resizing to be delayed. ## Open Addressing In **open addressing**, every element sits in the table's own slots. When a collision occurs, another slot is tried according to a fixed rule; these attempts are called **probing**. The plainest rule is **linear probing**: look at the next slot; if it is full, the one after that; wrap around to the beginning once the end of the table is reached. ```python EMPTY = object() # a slot that has never been used DELETED = object() # a deleted slot (tombstone) class OpenTable: def __init__(self, capacity: int = 8) -> None: self._slots: list = [EMPTY] * capacity self.probes = 0 def _location(self, key) -> int: return hash(key) % len(self._slots) def put(self, key, value) -> None: i = self._location(key) while self._slots[i] is not EMPTY and self._slots[i] is not DELETED: if self._slots[i][0] == key: break # update i = (i + 1) % len(self._slots) # linear probing self.probes += 1 self._slots[i] = (key, value) def get(self, key): i = self._location(key) while self._slots[i] is not EMPTY: # search ends on seeing EMPTY self.probes += 1 if self._slots[i] is not DELETED and self._slots[i][0] == key: return self._slots[i][1] i = (i + 1) % len(self._slots) raise KeyError(key) def delete(self, key) -> None: i = self._location(key) while self._slots[i] is not EMPTY: if self._slots[i] is not DELETED and self._slots[i][0] == key: self._slots[i] = DELETED # a tombstone is left return i = (i + 1) % len(self._slots) raise KeyError(key) table = OpenTable() for name, measurement in [("north", 12), ("south", 18), ("east", 7)]: table.put(name, measurement) print(table.get("south")) # 18 table.delete("south") print(table.get("east")) # 7 ``` ## The Deletion Problem In open addressing, deletion cannot be done by merely marking the slot "empty". Because search stops upon seeing the first empty slot, a deleted slot cuts off the search path: elements further along the same chain become unreachable. The solution is to fill the deleted slot with a separate marker — a **tombstone**. Search continues past a tombstone, while insertion may write into it. The cost is accumulation: after many deletions, the table fills with tombstones and searches grow longer. Implementations rebuild the table once the tombstone ratio exceeds a threshold. ## Clustering Linear probing's well-known weakness is **primary clustering**: consecutive blocks of full slots form, and every new collision extends the block. As a block grows, the number of probes for every key that lands in that region increases; the growth feeds on itself. Two alternative rules reduce this: - **Quadratic probing:** The step size is not fixed but an increasing sequence of squares. Consecutive blocks do not form; however, keys starting from the same location follow the same sequence (secondary clustering). - **Double hashing:** The step size is computed from a second hash function. Every key follows a different sequence; clustering is minimized, at the cost of a second hash computation. Linear probing has one advantage, and it is not negligible: looking at consecutive slots means staying within a cache line. The locality observation from the How Computers Work course makes linear probing competitive here against alternatives that are theoretically better. ## Comparing the Two Families | Criterion | Chaining | Open addressing | |---|---|---| | Load factor limit | Can exceed $1$ | Cannot exceed $1$; threshold kept lower | | Memory | Node/list overhead | No extra structure, but has empty slots | | Cache behavior | Weak (scattered list) | Good (contiguous slots) | | Deletion | Direct | Requires a tombstone | | Worst case | Long list in one bucket | Long probe traversing the table | | Structure inside bucket can be changed | Yes (tree instead of list) | No | The last row opens the door to a practical security measure: if a bucket's length exceeds a threshold, a balanced tree is used instead of a list, and the worst case becomes $O(\log n)$ instead of $O(n)$. This design has become widespread as a defense against deliberate collision attacks. ## Cost Table | Structure | Average search | Worst-case search | Deletion | |---|---|---|---| | Chaining | $O(1 + \alpha)$ | $O(n)$ | $O(1 + \alpha)$ | | Chaining (tree bucket) | $O(1 + \alpha)$ | $O(\log n)$ | $O(\log n)$ | | Open addressing | $O\left(\frac{1}{1-\alpha}\right)$ | $O(n)$ | $O(1)$ with a tombstone* | \* Degrades as tombstone accumulation grows. The expression in the third row shows why cost rises sharply as the load factor approaches $1$: for $\alpha = 0.9$, about ten probes are needed on average. This is why the threshold in open addressing is kept lower. ## Summary - In chaining, colliding elements are stored in a list within the bucket; in open addressing, they are stored in other slots of the table. - In chaining, average cost depends on the load factor, and the load factor can exceed $1$. - In open addressing, deletion requires a tombstone; otherwise the search path is cut off. - Linear probing produces primary clustering; quadratic probing and double hashing reduce it. - Linear probing's cache behavior compensates in practice for its theoretical disadvantage. - Converting the structure inside a bucket to a tree makes the worst case logarithmic and defends against collision attacks. ## Next Step A hash table establishes a key–value mapping. Some problems do not need a value; only the question "does this element exist" is asked. The next lesson covers set structures built around this question, and a highly efficient implementation built with bit-level operations for small universes.