Is a Python dictionary an example of a hash table?
Is a Python dictionary an example of a hash table?
Yes, it is a hash mapping or hash table. You can read a description of pythons dict implementation, as written by Tim Peters, here.
Thats why you cant 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 and why it is implemented that way.
There must be more to a Python dictionary than a table lookup on hash(). By brute experimentation I found this hash collision:
>>> hash(1.1)
2040142438
>>> hash(4504.1)
2040142438
Yet it doesnt break the dictionary:
>>> d = { 1.1: a, 4504.1: b }
>>> d[1.1]
a
>>> d[4504.1]
b
Sanity check:
>>> for k,v in d.items(): print(hash(k))
2040142438
2040142438
Possibly theres another lookup level beyond hash() that avoids collisions between dictionary keys. Or maybe dict() uses a different hash.
(By the way, this in Python 2.7.10. Same story in Python 3.4.3 and 3.5.0 with a collision at hash(1.1) == hash(214748749.8).)
(I havent found any collisions in Python 3.9.6. Since the hashes are bigger — hash(1.1) == 230584300921369601 — I estimate it would take my desktop a thousand years to find one. So Ill get back to you on this.)
Is a Python dictionary an example of a hash table?
Yes. Internally it is implemented as open hashing based on a primitive polynomial over Z/2 (source).