Are dictionaries the same as hashtables?

John Machin sjmachin at lexicon.net
Tue Aug 26 13:28:33 CEST 2008


On Aug 26, 7:36 pm, "Diez B. Roggisch" <de... at nospam.web.de> wrote:
> Martin Marcher wrote:
> > On 2008-08-26 00:32:20, cnb wrote:
> >> Are dictionaries the same as hashtables?
>
> > Yes, but there is nothing in there that does sane collision handling
> > like making a list instead of simply overwriting.
>
> The term "collision" is rather well defined when talking about associative
> arrays using hashing (which python's dicts are): it means that two distinct
> keys produce the same hash-value, leading to a bucket collision. And of
> course python deals with that sanely, and creates a list of objects inside
> the bucket which is traversed and comparison is used to determine which
> actual value to retrieve.

I see neither buckets nor lists in the CPython svn trunk version of
dictobject.c and IIRC it's been using open addressing for a very long
time.



More information about the Python-list mailing list