Set builtin lookups

[Alex Martelli]

Steve Holden <steve at holdenweb.com> wrote:

> Marc 'BlackJack' Rintsch wrote:
> > In <mailman.109.1182926621.22759.python-list at python.org>, Evan Klitzke
> > wrote:
> > 
> >> I have a question about the internal representation of sets in Python.
> >> If I write some code like
> >>
> >> if x in some_list:
> >>     do_something()
> >>
> >> the lookup for the in statement is O(n), where n is the number of
> >> elements in the list. Is this also true if I am using a set or are
> >> sets represented by a hash table?
> > 
> > Sets are implemented as hash tables.
> > 
> > Ciao,
> >     Marc 'BlackJack' Rintsch
> 
> More importantly, no, neither sets nor dictionaries have O(N) lookup 
> costs. As an experiment or two can show.

The exception would be for objects with a bad or unlucky __hash__ that
happens to return the same value for every object:

class oops(object):
  def __hash__(self): return 123456

this one you might expect to produce O(N) behavior:-).


Alex