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.
kguest3,88433 gold badges3131 silver badges3232 bronze badges
asked Feb 2, 2013 at 17:44
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.
answered Feb 2, 2013 at 17:45
Martijn PietersMartijn Pieters1.1m324324 gold badges4.2k4.2k silver badges3.4k3.4k bronze badges
1Start asking to get answers
Find the answer to your question by asking.
Ask questionExplore related questions
See similar questions with these tags.
RetroSearch is an open source project built by @garambo | Open a GitHub Issue
Search and Browse the WWW like it's 1997 | Search results from DuckDuckGo
HTML:
3.2
| Encoding:
UTF-8
| Version:
0.7.4