How can the search for an element in a set be O(1)?

Question

In accordance with the official Python page as to the complexity of time algorithms, sequences list and set have the following characteristics::

List

Set

Highlight for the operator in, which verifies the presence of an element in the sequence, which in list has complexity O(n) and in set has O(1).

How can the operator in have complexity O(1) in a sequence?

Answer 1

The sets set are not "sequences" - neither in the internal organization of the data, nor in the interface they implement, since they do not guarantee any order.

Sets actually have the implementation similar to dictionaries - but only the key side: internally, a data structure containing the hash of objects is used, and this maps to a real reference to the object. So, the "thick" of the search is the hash of the object in that structure.

And, hash searches are rightly made to be O(1).

If the hash is found, the object reference is retrieved - if it is the same object (id’s are the same), the match is given, otherwise an equality comparison is made. These other checks, and even in the case of hash collision, when a sequential search is made between objects of the same hash, do not count for algorithmic complexity.

Of course, the limitation is that "unhashable" objects (in general, mutable objects), cannot be placed in sets (sets), just as they cannot be dictionary keys. If this is necessary, it is necessary to implement a class that responds to the same set interface(see collections.abc), but with other internal algorithms, which can hardly be O(1), unless they use a similar technique.