Dictionary in Python

[Aahz Maruch]

In article <K9az4.12452$WI1.277622 at news1.frmt1.sfba.home.com>,
Jijun Wang <jwang at new-access.com> wrote:
>
>Does anyone know how dictionary is implemented in Python(such as hash table,
>heap, linked list)? If my dictionary increases in size, how much is the
>impact on performace?

I had a discussion about this with Tim Peters a while back, so I think I
can answer your questions correctly:

A Python dict uses an expanding hash table, so that the number of hash
entries increases as you add keys.  In general, the performance should
stay near O(1), because Python's hashing algorithm is well distributed
over the key space.  Python does not actually hash on the object;
instead, it hashes on the reference to the object (sort of, this isn't
quite technically accurate, but I'm not familiar enough with the
internals to make it more accurate) -- this is the reason why Python
requires immutables as keys.
--
                      --- Aahz (Copyright 2000 by aahz at netcom.com)

Androgynous poly kinky vanilla queer het    <*>     http://www.rahul.net/aahz/
Hugs and backrubs -- I break Rule 6

"Along the lines of getting a massage, taking a hot bubble bath, and
swimming in a pool of warm, melted chocolate, can you give me some
innovative ways that you pamper yourself?"
"Spend three hours flaming stupid people on the Net."  --Aahz