According to the official Python page for the complexity of algorithms over time, the sequences list and set have the following characteristics:
Highlight for the in operator, which checks for the presence of an element in the sequence, which in list has complexity O (n) and in set has O (1).
How can the in operator have complexity O (1) in a sequence?
The set sets 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 dictionary-like implementation - but only the key side: internally, a data structure containing hash of objects is used, and this maps to a real reference to the object. So the "bulk" of the search is by the hash of the object in that structure.
And, hash searches are just made to be O (1).
If the hash is found, the object reference is retrieved - if it is the same object (id's are same), if the match is given, otherwise an equality comparison is made. These other checks, and even in the case of a hash collision, when a sequential search is performed between the objects of the same hash, do not count for the algorithmic complexity.
Of course, the limitation is that "unhashable" objects (in general, mutable objects) can not be placed in sets, just as they can not be dictionary keys. If this is necessary, it is necessary to implement a class that responds to the same interface of the sets (see collections.abc ), but with other internal algorithms, which can hardly be O (1), unless they use a similar technique. p>
