Hash Table Collisions: Chaining vs Open Addressing in Python

Why Python's dict is Fast (and When It Isn't) Python's built-in dict uses open addressing with a twist — it's not the simple linear or quadratic probing you see in textbooks. Yet most coding interview questions about hash tables still ask you to implement collision resolution from scratch, usually chaining with linked lists. I wanted to see the actual performance gap between these approaches, not just the theoretical complexity. So I built both. A chaining-based hash table using Python lists (because linked lists in Python are painfully slow) and an open addressing table with linear probing. Then I threw 100k operations at them: inserts, lookups, deletes. The results weren't what I expected. The Core Problem: Two Items, One Bucket Hash collisions happen when two keys hash to the same index. If you're inserting ("apple", 5) and ("banana", 3) and both hash to index 7, you need a tiebreaker. Chaining says: keep a list at each bucket. When collision happens, append to the list. Lookup beco