Siv Scripts

Solving Problems Using Code

Fri 01 December 2017

Python Dictionaries Require Hashable Keys

Posted by Aly Sivji in Quick Hits   

I was floored when I discovered I could use tuples (and namedtuples) as Python dictionary keys.

Turns out this is not totally correct.

Started reading Fluent Python and learned that tuples are not always immutable. For instance, they can contain list elements...

In [1]:
my_tuple = ('a', 'b', [1, 2])
type(my_tuple)
Out[1]:
tuple

Let's try using my_tuple as a dictionary key.

In [2]:
# First we'll create a dictionary and insert a (key, value) pair
my_dict = {}
my_dict['test'] = 'foo'
my_dict
Out[2]:
{'test': 'foo'}
In [3]:
# Let's make sure that we cannot use a list element in the dictionary
my_dict[[1, 2]] = 'foo'

---------------------------------------------------------------------------
TypeError                                 Traceback (most recent call last)
<ipython-input-3-48c007026868> in <module>()
      1 # Let's make sure that we cannot use a list element in the dictionary
----> 2 my_dict[[1, 2]] = 'foo'

TypeError: unhashable type: 'list'
In [4]:
# Dictionary has not changed
my_dict
Out[4]:
{'test': 'foo'}
In [5]:
# Let's try inserting a tuple containing a list, as a key
my_dict[my_tuple] = 'bar'

---------------------------------------------------------------------------
TypeError                                 Traceback (most recent call last)
<ipython-input-5-5c6167bc5fe6> in <module>()
      1 # Let's try inserting a tuple, which contains a list, as a key
----> 2 my_dict[my_tuple] = 'bar'

TypeError: unhashable type: 'list'

This should be true for namedtuples as well.

In [6]:
from collections import namedtuple

TestTuple = namedtuple('TestTuple', ['field1', 'field2', 'field3'])
my_item = TestTuple('a', 'b', [1, 2])
type(my_item)
Out[6]:
__main__.TestTuple
In [7]:
isinstance(my_item, tuple)
Out[7]:
True
In [8]:
my_dict[my_item] = 'bar'

---------------------------------------------------------------------------
TypeError                                 Traceback (most recent call last)
<ipython-input-8-a4dfa91fcd88> in <module>()
----> 1 my_dict[my_item] = 'bar'

TypeError: unhashable type: 'list'

What's going on?

Python dictionaries leverage hash tables. When we use a key that contains an unhashable type, i.e. a list, the underlying hash map cannot guarantee the key will map to the same bucket every single time. If we can't hash our key, we can't use it in our dictionary.

Therefore, Python dictionaries require hashable dict keys. Having immutable keys is not enough.

Shoutout to Luciano Ramalho for writing Fluent Python. Only three chapters in and this kind of thinking is becoming second nature.

Tags python  how-to  pythonic 
 
    
 
 

Comments