Is a Python dictionary an example of a hash table?

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 hash table? If not, what is it?

Asked by: Catherine612 | Posted: 28-01-2022

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

Answered by: Melissa683 | Posted: 01-03-2022

Answer 2

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 doesn't 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 there's 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 haven't 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 I'll get back to you on this.)

Answered by: Briony833 | Posted: 01-03-2022

Answer 3

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

Answered by: Kellan620 | Posted: 01-03-2022

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

Answered by: Kelvin642 | Posted: 01-03-2022

Similar questions

dictionary - Dict Same Key - Example 39 Learn Python the Hard Way

new to coding and working through Zed Shaw's Learn Python3 the Hard way. I wanted to make a dict that maps a key to multiple cities but quickly found out that each key has to be unique and reusing the same key simply overwrites the previous value. Here is my original code: states = { 'Pennsylvania': 'PA', 'Maryland': 'MD', 'Texas': 'TX'} cities = { 'PA': 'State College', 'P...

Python Dictionary example

I am new to python and need help to understand this piece of code used to create a dictionary new_key_lis = [18,23,45] b= dict([(23,18)]) c = dict(zip(new_key_lis, [None]*len(new_key_lis))) print(c) I would like to know about the difference between [None] and None ?

How can I count each dictionary value output in Python in the following code example?

I'm learning to play with lists, tuples and dictionaries in Python (2.7), and to convert dictionaries to lists and to reference them, but am experiencing some difficulties in understanding how I might add a count number to specific values that I am retrieving from dictionaries. I start with this code as follows: users = { 'Participants': [ {'first_name': 'Jerry', 'last_name' : 'Johnson...

sorting - In Python, how can you easily retrieve sorted items from a dictionary?

Dictionaries unlike lists are not ordered (and do not have the 'sort' attribute). Therefore, you can not rely on getting the items in the same order when first added. What is the easiest way to loop through a dictionary containing strings as the key value and retrieving them in ascending order by key? For example, you had this: d = {'b' : 'this is b', 'a': 'this is a' , 'c' : 'this is c'}

Python dictionary from an object's fields

Do you know if there is a built-in function to build a dictionary from an arbitrary object? I'd like to do something like this: >>> class Foo: ... bar = 'hello' ... baz = 'world' ... >>> f = Foo() >>> props(f) { 'bar' : 'hello', 'baz' : 'world' } NOTE: It should not include methods. Only fields.

python - How do you retrieve items from a dictionary in the order that they're inserted?

Is it possible to retrieve items from a Python dictionary in the order that they were inserted?

python - How can I make a dictionary from separate lists of keys and values?

I want to combine these: keys = ['name', 'age', 'food'] values = ['Monty', 42, 'spam'] Into a single dictionary: {'name': 'Monty', 'age': 42, 'food': 'spam'}

python - Dictionary or If statements, Jython

I am writing a script at the moment that will grab certain information from HTML using dom4j. Since Python/Jython does not have a native switch statement I decided to use a whole bunch of if statements that call the appropriate method, like below: if type == 'extractTitle': extractTitle(dom) if type == 'extractMetaTags': extractMetaTags(dom)

python - Is there a "one-liner" way to get a list of keys from a dictionary in sorted order?

The list sort() method is a modifier function that returns None. So if I want to iterate through all of the keys in a dictionary I cannot do: for k in somedictionary.keys().sort(): dosomething() Instead, I must: keys = somedictionary.keys() keys.sort() for k in keys: dosomething() Is there a pretty way to iterate t...

python - Interface to versioned dictionary

I have an versioned document store which I want to access through an dict like interface. Common usage is to access the latest revision (get, set, del), but one should be able to access specific revisions too (keys are always str/unicode or int). from UserDict import DictMixin class VDict(DictMixin): def __getitem__(self, key): if isinstance(key, tuple): docid, rev = key e...

python - List all words in a dictionary that start with <user input>

How would a go about making a program where the user enters a string, and the program generates a list of words beginning with that string? Ex: User: "abd" Program:abdicate, abdomen, abduct... Thanks! Edit: I'm using python, but I assume that this is a fairly language-independent problem.

python - Check if a given key already exists in a dictionary and increment it

How do I find out if a key in a dictionary has already been set to a non-None value? I want to increment the value if there's already one there, or set it to 1 otherwise: my_dict = {} if my_dict[key] is not None: my_dict[key] = 1 else: my_dict[key] += 1

Given a list of variable names in Python, how do I a create a dictionary with the variable names as keys (to the variables' values)?

I have a list of variable names, like this: ['foo', 'bar', 'baz'] (I originally asked how I convert a list of variables. See Greg Hewgill's answer below.) How do I convert this to a dictionary where the keys are the variable names (as strings) and the values are the values of the variables? {'foo': foo, 'bar': bar, 'baz': baz} Now that I'm re-aski...

Still can't find your answer? Check out these communities...

top