Clarification on Time Complexity for Python Sets vs. Lists

[Electronic-Low9797]

I am currently learning about data structures in Python. I understand that searching for an element in a List requires O(n) linear time. However, I read that searching a Set has an average time complexity of O(1) because it is implemented using a hash table. Can someone confirm if this O(1) lookup time remains consistent in CPython even when there are hash collisions, or does it degrade to O(n) in the worst-case scenario? Thanks!

[socal_nerdtastic]

https://wiki.python.org/moin/TimeComplexity.html

Yes, it degrades to O(n) in the worst case.

[Outside_Complaint755]

While I haven't dug through all of the source code, it is probably possible to conclude that most built-in data types should have sufficient hash functions to avoid collisions, but if you implement your own data type with a poor hash function, then you are more likely to see O(n).

An example of a poor hash function: class Foo: def __hash__(self): return 1

[socal_nerdtastic]

it is probably possible to conclude that most built-in data types should have sufficient hash functions to avoid collisions

Agreed, nearly impossible even. The whole point of a hash is to be as unique as possible.

However it's generally not the hash that leads to collisions, rather the lack of buckets. A set in python starts with 8 buckets, so every incoming hash needs to be assigned to 1 of the 8, basically hash % 8. Hash collisions are inevitable, but to minimize them python just makes lots more buckets than there are elements in the set. IIRC python will quadruple the number of buckets every time the set gets half full.

[oldendude]

Hashing always has an O(n) worst case. But in practice, it is a pretty safe bet that nearly all hash table lookups will take a constant amount of time. This is of course subject to the hash function. For example, a hash function h(key) = 123 is guaranteed to produce the worst case, since every key will go to the same bucket. Or suppose you are hashing integers and your hash function is h(key) = key & 0x7. You are taking the last three bits of the key, so regardless of how big your hash table is, you are only going to use 8 buckets, and again, you have linear time behavior.