GoKawiilIn Python, the dict data structure is the conventional key-value structure. E.g., you might store a list of names as keys and have their phone numbers as values. Valentin Ignatev wrote this amusing post on X:
It is indeed widely believed that, in the strict sense, the dict data structure and its companion, the set data structure, are O(1), meaning that as you increase the size of the data structure, the time to insert or query a key remains constant.
Let us examine the claim.
A hash function is a function from objects (like strings, integers, etc.) to integer values. We typically expect hash functions to be random-like, although they should always map the same object to the same integer within the current program execution. From hash functions, we construct hash tables:
Create an array of buckets. Given an object, apply the hash function to map it to a bucket. Store the object in the bucket. When the bucket is already occupied, use some other trick (such as using a nearby bucket).
If everything goes well, access and insertion in a hash table take nearly constant time, meaning that the time they take is independent of the size of the hash table.
This can be almost true in many instances. However, it is not formally true. There are many reasons why it is false. For example, if your data structure grows, it might be necessary to reallocate, which will typically take time proportional to the size of the data structure. But we also have the issue of collisions. A collision is what happens when two objects have the same hash value. When we use hash tables, we assume that collisions are uncommon. But it is not difficult to create many of them by picking our objects carefully.
In Python, set and dict are hash tables. I can ‘easily’ make my version of Python crumble:
M = ( 1 << 61 ) - 1 values = [ i * M for i in range ( 1 , n + 1 )] s = set ( values ) # insertions count = sum ( v in s for v in values ) # checks
If the insertions and the checks are constant-time operations, then the whole construction and the entire check should take linear time. I ran this on an Apple M4 Max with Python 3.14, reporting the median of three runs.
... continue reading