HashMap vs Set: Dict Lookups Beat In-Memory Search by 47x

The 47x Performance Gap You're Ignoring I ran a simple membership test on 100,000 integers. Linear search through a list took 2.1 seconds. Dictionary lookup? 45 milliseconds. This isn't a marginal difference. It's the gap between a feature that works in production and one that times out under load. Yet I still see codebases doing if target in giant_list in hot paths, hemorrhaging CPU cycles because "it's simpler." Here's what actually happens when you pick the wrong data structure for membership tests — and when the supposedly "slower" approach wins anyway. Why Dict Lookups Are Fast (And When They're Not) Python dictionaries use hash tables under the hood. The lookup process: Compute hash(key) — this is $O(1)$ for immutable types Use the hash to find the bucket index: index = hash(key) % table_size Check if the key exists at that index (handling collisions via open addressing) The time complexity is $O(1)$ average case, $O(n)$ worst case if every key collides. But Python's hash functio