The thing everyone knows without necessarily knowing why

"Dict and set lookups are fast, roughly constant time, regardless of how big they get" is one of the first real performance facts anyone learns. Checking whether a value exists in a list gets slower as the list grows. Checking whether it exists in a set barely changes at all:

target = -1  # deliberately absent, so both checks do a real, full search

target in some_list   # gets slower as len(some_list) grows
target in some_set    # stays roughly constant

n=  1000: list 'in' =      6.41 us   set 'in' =   0.047 us   ratio =     136x
n=  4000: list 'in' =     26.98 us   set 'in' =   0.048 us   ratio =     562x
n= 16000: list 'in' =    106.06 us   set 'in' =   0.059 us   ratio =    1783x
n= 64000: list 'in' =    437.25 us   set 'in' =   0.060 us   ratio =    7227x

The list's lookup time grows in a straight line with its size, because a list has no better option than checking elements one at a time until it finds a match or runs out. The set's lookup time barely moves at all, even at 64x the size. That's the real, measured behavior "hash tables give O(1) lookup" is describing.

What's actually happening

A set (and a dict, built on the same mechanism) doesn't search for a value. It computes hash(value), a number, uses that number to jump directly to roughly the right location internally, and checks only the handful of items that landed in that same location. No scanning the whole structure, just: hash the value, jump to a location, check a small number of candidates there. That's the entire reason it doesn't slow down as the set grows: the number of items to check at any single location stays small regardless of how many total items exist, as long as the hash values are spread out well.

"As long as the hash values are spread out well" is the part usually left out, and it's not a minor caveat.

Breaking it on purpose

class BadKey:
    def __init__(self, value):
        self.value = value
    def __hash__(self):
        return 1  # every single instance hashes to the same value
    def __eq__(self, other):
        return self.value == other.value

A custom class where __hash__ always returns 1, regardless of what the object actually holds. Every single BadKey instance, no matter its value, computes the same hash, and lands in the same internal location. Put a few thousand of them in a set and check membership the same way as before:

n=  500: well-hashed =     0.17 us   all-collide = 33.6 us     ratio =    195x
n= 1000: well-hashed =     0.22 us   all-collide = 78.8 us     ratio =    355x
n= 2000: well-hashed =     0.21 us   all-collide = 132.4 us    ratio =    630x
n= 4000: well-hashed =     0.22 us   all-collide = 304.6 us    ratio =   1385x

The well-hashed version stays flat, same as before. The BadKey version's lookup time grows roughly in a straight line with the number of items, the exact same shape as a plain list's linear search. That's not a coincidence: with every item landing in the same location, the set has been reduced to checking candidates one at a time again, all the real structure a hash table provides has been defeated by one method that doesn't do its job.

Why this is worth knowing, not just interesting

Most code never defines a custom __hash__ at all, Python's built-in types (strings, numbers, tuples) already hash well, and the vast majority of real dict and set usage never runs into this. But the moment a custom class goes into a set or becomes a dict key, and someone writes a __hash__ that's technically valid (consistent with __eq__, as Python requires) but poorly distributed, hashing on only one field of a mostly-uniform object, or something equally coarse, the real performance characteristics quietly degrade from "the reason dicts are fast" back to "a slow list in disguise," with no error, no warning, and code that still returns correct answers the entire time.

The takeaway

A dict or set's speed isn't a property of the data structure alone, it's a property of the data structure combined with a hash function that actually spreads values out. Built-in types already do this well. A custom __hash__ is a real, direct lever on real performance, not just a technical requirement to satisfy, and it's worth checking, the same way it was checked here, rather than assumed.