views:

5804

answers:

4

One of the basic data structures in Python is the dictionary, which allows one to record "keys" for looking up "values" of any type. Is this implemented internally as a hashmap? If not, what is it?

+28  A: 

Yes, it is a hash mapping or hash table. You can read a description of python's dict implementation, as written by Tim Peters, here.

That's why you can't use something 'not hashable' as a dict key, like a list:

>>> a = {}
>>> b = ['some', 'list']
>>> hash(b)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: list objects are unhashable
>>> a[b] = 'some'
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: list objects are unhashable

You can read more about hash tables or check how it has been implemented in python.

nosklo
+7  A: 

Yes. Internally it is implemented as open hashing based on a primitive polynomial over Z/2 (source).

Ben Hoffstein
+11  A: 

If you're interested in the technical details, one article in Beautiful Code deals with the internals of Python's dict implementation.

Torsten Marek
That was one of my favorite chapters in Beautiful Code.
DGentry
+1  A: 

To expand upon nosklo's explanation:

a = {}
b = ['some', 'list']
a[b] = 'some' # this won't work
a[tuple(b)] = 'some' # this will, same as a['some', 'list']
Jeremy Cantrell