Python dictionary details

Question

I would like to know where the source code for python's Dictionary is located. I know the source code will probably difficult to read so I'm really just after a rough description of the implementation and the hash routine which is used.

Does anybody know what sort of algorithm is used and how they deal with collisions, if chaining is used or is the table rebuilt.

I know this question is a bit vague so just a point in the right direction would be helpful please. If anybody know of any good documentation on python's dictionary that would be great.

Answer 1

It's located in the Objects/dictobject.c file. There is a dictnotes.txt file there too, to guide you in understanding the source.

Python dictionaries use a hashtable with open addressing to map keys to slots. Conflicts are resolved by 'perturbing' the key; an algorithm that'll start with a large step, then use smaller and smaller steps until it scans the table for the next empty slot.

There are several articles on the web, including this blog post; you can also pick up the book Beautiful Code for an excellent exposure of the code.

Answer 2

The source tree has quite good docs on how dictionaries work: http://hg.python.org/cpython/file/ab4b8da79a5f/Objects/dictnotes.txt

Answer 3

also.. . here is a active state recipe of dict which is more efficiant(from 3 to 24 times more space efficient than regular dictionaries)!! .otherwise previous two answers are great!!
http://code.activestate.com/recipes/578375-proof-of-concept-for-a-more-space-efficient-faster/?in=user-178123