Python hashing algorithm in default dict

Question

Simple question.

What hashing algorithm is used in python's default dict?

>>> g = { 'a' : 1, 'b' : 2, 'c' : 3 }
>>> g
{'a': 1, 'c': 3, 'b': 2}
>>> g.keys()
['a', 'c', 'b']
>>>

I expected ['a','b','c'] on g.keys() Linear probe (guess not)? double hash?

hg.python.org/cpython/file/tip/Objects/dictobject.c might contain something relevant. — riamse
– riamse, Commented Mar 28, 2013 at 23:46
Any hashing is size dependent. And the char/string hash is used. This should not be surprising. — Captain Giraffe
– Captain Giraffe, Commented Mar 28, 2013 at 23:46
It's impossible to know what the "order" will be without knowing the hash function, the bucket count at each insertion, the collision resolution, and the order of insertion .. at the very least. The linked source code says how a particular implementation does it. These same "unpredictable results" can be achieved through chaining, probing, double hashing, and extensible hashing - that is, the result is a compound factor and not directly related to the collision resolution. — user166390
– user166390, Commented Mar 28, 2013 at 23:49
Why did you expect a, b, c, knowing it was a hash? Linear probe is frowned upon. — Captain Giraffe
– Captain Giraffe, Commented Mar 28, 2013 at 23:51

Community · Accepted Answer · 2017-05-23 12:21:07Z

3

There is no guarantee that Python will use any particular method - different implementations could use any one they wish. dicts are unordered, so it doesn't matter how it's implemented (provided it fulfills certain obligations).

As to how CPython does it...

edited May 23, 2017 at 12:21

CommunityBot

11 silver badge

answered Mar 28, 2013 at 23:42

Gareth Latty

89.5k18 gold badges183 silver badges187 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

Python hashing algorithm in default dict

1 Answer 1

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related