0

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?

The Internet
  • 7,959
  • 10
  • 54
  • 89
  • 4
    http://hg.python.org/cpython/file/tip/Objects/dictobject.c might contain something relevant. – riamse Mar 28 '13 at 23:46
  • Any hashing is size dependent. And the char/string hash is used. This should not be surprising. – Captain Giraffe Mar 28 '13 at 23:46
  • @riamse That code is well commented. – Captain Giraffe Mar 28 '13 at 23:48
  • 2
    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. –  Mar 28 '13 at 23:49
  • Why did you expect a, b, c, knowing it was a hash? Linear probe is frowned upon. – Captain Giraffe Mar 28 '13 at 23:51

1 Answers1

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...

Community
  • 1
  • 1
Gareth Latty
  • 86,389
  • 17
  • 178
  • 183