python dict implementation details

Question

I have a question about python dictionary implementation.

Looks like python will maintain a search order for all keys, e.g if you do the following operation

a = {}
a[3] = 1
a[0] = 2

a = {0:2, 3:1}

python will automatically change my insertion order. As python claims that dict is unordered set, I don't quite understand why python will maintain such a search order. Does python implement dict by a hash table and store another set for index ordering?

Hopefully I make the question clear.

Thank you

unrelated: [PyPy's dicts may be ordered](http://morepypy.blogspot.ru/2015/01/faster-more-memory-efficient-and-more.html) — jfs, Feb 21 '15 at 07:13
I'm closing as duplicate because your specific questions should be fully answered by the responses, although I realize the questions don't match 100%. See the "linked questions" in the side-bar of the duplicate for more. — Veedrac, Feb 22 '15 at 16:06

mgilson · Answer 1 · 2015-02-22T05:25:40.677

The order of a dict is completely determined by the hashing function of the object (and insertion order if there are hash collisions). Integers hash to themselves (at least up to sys.maxint):

>>> hash(1)
1

The (C)python implementation takes the hash value of the object and takes a few bits to determine the index in the table. How many bits it takes depends on the length of the dictionary. By default, the dict has 8 available slots, so the numbers 0 and 8 will collide. We can see this as follows:

>>> d1 = {}
>>> d1[0] = 'foo'
>>> d1[8] = 'bar'
>>> d1
{0: 'foo', 8: 'bar'}
>>>
>>> d2 = {}
>>> d2[8] = 'bar'
>>> d2[0] = 'foo'
>>> d2
{8: 'bar', 0: 'foo'}

Since 0 and 8 collided in our dictionary, insertion order appears to have been maintained. 0 takes the first available slot (after all, no matter how many bits you take from 0, you'll get 0). 8 tries to take that slot as well. If that slot is taken, however, collision resolution takes over and python inserts that value in some later slot.

Of course, if your dictionary happens to have more than ~5 elements, it will be resized (I think to 16, but don't quote me on that) and 0 and 8 will no longer collide...

>>> d1 = {x:x for x in range(1, 6)}
>>> d1[0] = 0
>>> d1[8] = 8
>>> d1
{0: 0, 1: 1, 2: 2, 3: 3, 4: 4, 5: 5, 8: 8}
>>> d2 = {x:x for x in range(1, 6)}
>>> d2[8] = 8
>>> d2[0] = 0
>>> d2
{0: 0, 1: 1, 2: 2, 3: 3, 4: 4, 5: 5, 8: 8}

Note, the (sorted) order is preserved (not insertion order) which means that every integer got it's preferred spot in the hash table (no collisions). I think that the dict gets resized when it is about 2/3rds full.

Note, this is purely academic -- the python specification doesn't say this is how it works and so it could change at any time. Please don't rely on this behavior. Most of this can be gleaned from comments in the source code and documentation that sits next to it...

hmm..just checked your profile .. you're too young to be a Fortran programmer ;-) — iruvar, Feb 21 '15 at 06:10
@1_CR -- I spent 7 years doing High performance computing and space science research :-) — mgilson, Feb 21 '15 at 06:11
Minor note: When you say *"Integers hash to themselves"*, that is only true for moderately sized integers. Get out to a dozen or so digits, and they'll hash to something else. — , Feb 21 '15 at 06:14
@iCodez -- `hash(123456789101112)` -- I think this only starts changing once you get above `sys.maxint` (in Cpython)... — mgilson, Feb 21 '15 at 06:19
@AnttiHaapala -- Very interesting. I didn't know about that one! — mgilson, Feb 22 '15 at 02:28

score 1 · Answer 2 · answered Feb 21 '15 at 06:06

Dict index ordering is just a consequence of how the dict is implemented, and should not be relied on.

To be precise, Python doesn't change your insertion order (since that is just defined to be the order you insert items into the dict), but the iteration order has no guarantees.

When Python creates a dict, it creates enough space for 8 key, value pairs (I think). For an empty dict, none of them are filled. Whenever you put an item into a dict, Python takes a hash of the key and the key's hash decides on what the index will be.

If you do want the iteration order to be the same as the insertion order, check out an ordereddict.

python dict implementation details

2 Answers2