Is a Python dictionary an example of a hashmap?

Question

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?

Answer 1

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.

Answer 2

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

Answer 3

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

Answer 4

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']