Lesson 11: Dictionaries (hash tables)

This tutorial was generated from a Jupyter notebook. You can download the notebook here.

A mapping object allows an arbitrary collection of objects to be indexed by an arbtrary collection of values. That's a mouthful. It is easier to understand instead by comparing to a sequence.

Let's take a sequence of two strings, say a tuple containing a first and last name.

name = ('jane', 'doe')

We are restricted on how we reference the sequence. I.e., the first name is name[0], and the last name is name[1]. A mapping object could instead be indexed like name['first name'] and name['last name']. You can imagine this would be very useful!

Dictionaries are the only built-in mapping type in Python. You might imagine that the Oxford English Dictionary might conveniently be stored as a dictionary. I.e., you would not want to store definitions that have to be referenced like


Rather, you would like to get definitions like this:


Importantly, note that Python dictionaries have no sense of order. Unlike lists and tuples, which are ordered collections, dictionaries have no order. The key is used to fetch the values from memory.

The only exception to this rule is if you use integers as your key values. If integers are used as the key values, then Python will automatically sort the dictionary such that key:value pairs are listed in ascending order with respect to the key.

Dictionary syntax

The syntax for creating a dictionary, as usual, is best seen through example.

In [18]:
my_dict = {'a': 6, 'b': 7, 'c': 27.6}
{'a': 6, 'b': 7, 'c': 27.6}

A dictionary is created using curly braces ({}). Each entry has a key, followed by a color, and then the value associated with the key. In the example above, the keys are all strings, which is the most common use case. Note that the items can be of any type; in the above example, they are ints and a float.

We could also create the dictionary using the built-in dict() function, which expects a tuple of 2-tuples, each one containing a key-value pair.

In [15]:
dict((('a', 6), ('b', 7), ('c', 27.6)))
{'a': 6, 'b': 7, 'c': 27.6}

Finally, we can make a dictionary with keyword arguments to the dict() function.

In [37]:
dict(a='yes', b='no', c='maybe')
{'a': 'yes', 'b': 'no', 'c': 'maybe'}

We do not need to have strings as the keys. In fact, any immutable object can be a key.

In [1]:
my_dict = {0: 'zero',
           1.7: [1, 2, 3],
           (5, 6, 'dummy string'): 3.14,
           'strings are immutable': 42}
{0: 'zero',
 1.7: [1, 2, 3],
 'strings are immutable': 42,
 (5, 6, 'dummy string'): 3.14}

However, mutable objects cannot be used as keys.

In [24]:
my_dict = {'mutable is ok': 1,
           ['immutable', 'not', 'ok']: 5}
TypeError                                 Traceback (most recent call last)
<ipython-input-24-13687bbbeeaa> in <module>()
      1 my_dict = {'mutable is ok': 1,
----> 2            ['immutable', 'not', 'ok']: 5}

TypeError: unhashable type: 'list'

Useful dictionaries in bioinformatics

It might be useful to quickly look up 3-letter amino acid codes. Dictionaries are particularly useful for this.

In [5]:
aa_dict = {'A': 'Ala',
           'R': 'Arg',
           'N': 'Asn',
           'D': 'Asp',
           'C': 'Cys',
           'Q': 'Gln',
           'E': 'Glu',
           'G': 'Gly',
           'H': 'His',
           'I': 'Ile',
           'L': 'Leu',
           'K': 'Lys',
           'M': 'Met',
           'F': 'Phe',
           'P': 'Pro',
           'S': 'Ser',
           'T': 'Thr',
           'W': 'Trp',
           'Y': 'Tyr',
           'V': 'Val'}

Another useful dictionary would contain the set of codons and the amino acids they code for. This is build in the code below using the zip() function we learned before. To see the logic on how this is constructed, see the codon table here.

In [8]:
# The set of DNA bases
bases = ['T', 'C', 'A', 'G']

# Build list of codons
codons = []
for first_base in bases:
    for second_base in bases:
        for third_base in bases:
            codons += [first_base + second_base + third_base]

# The amino acids that are coded for (* = STOP codon)

# Build dictionary from tuple of 2-tuples (technically an iterator, but it works)
codon_dict = dict(zip(codons, amino_acids))

# Show that we did it
{'GGT': 'G', 'CTT': 'L', 'TCT': 'S', 'AGA': 'R', 'TTG': 'L', 'GTC': 'V', 'ATG': 'M', 'TCC': 'S', 'ACA': 'T', 'GTT': 'V', 'AAC': 'N', 'TAT': 'Y', 'GTG': 'V', 'GCC': 'A', 'GGC': 'G', 'TTC': 'F', 'AGG': 'R', 'CGC': 'R', 'TGC': 'C', 'TCA': 'S', 'TTA': 'L', 'ATA': 'I', 'TGT': 'C', 'GAT': 'D', 'TGA': '*', 'AGT': 'S', 'CTA': 'L', 'GCG': 'A', 'ACC': 'T', 'CAA': 'Q', 'AAG': 'K', 'TAC': 'Y', 'ATC': 'I', 'TAG': '*', 'ATT': 'I', 'CTC': 'L', 'CTG': 'L', 'TGG': 'W', 'TTT': 'F', 'AAT': 'N', 'GCA': 'A', 'CAT': 'H', 'CCT': 'P', 'CAC': 'H', 'GAA': 'E', 'GAC': 'D', 'TAA': '*', 'GCT': 'A', 'CCA': 'P', 'GGA': 'G', 'CGG': 'R', 'TCG': 'S', 'AGC': 'S', 'CGT': 'R', 'ACT': 'T', 'CAG': 'Q', 'CCG': 'P', 'GTA': 'V', 'AAA': 'K', 'GAG': 'E', 'CCC': 'P', 'GGG': 'G', 'CGA': 'R', 'ACG': 'T'}

A dictionary is an implementation of a hash table

It is useful to stop and think about how a dictionary works. Let's create a dictionary and look at where the values are stored in memory.

In [34]:
# Create dictionary
my_dict = {'a': 6, 'b': 7, 'c':12.6}

# Find where they are stored

So, each entry in the dictionary is stored at a different location in memory. The dictionary itself also have its own address. So, when I index a dictionary with a key, how does the dictionary know which address in memory to use to fetch the value I am interested in?

Dictionaries use a hash function to do this. A hash function converts its input to an integer. For example, we can use Python's built-in hash function to convert the keys to integers.

In [35]:
hash('a'), hash('b'), hash('c')
(-6270946236321725506, 7139134932933917989, 3648969169057735723)

Under the hood, Python then converts these integers to integers that could correspond to locations in memory. A collection of elements that can be indexed this way is called a hash table. This is a very common data structure in computing. Wikipedia has a pretty good discussion on them.

Now, given what you know about how dictionaries work, why do you think immutable objects are not acceptable as keys?

Dictionaries are mutable

The title says it all! Dictionaries are mutable. This means that they can be changed in place. For example, if we want to add an element to a dictionary, we use simple syntax.

In [36]:
# Remind ourselves what the dictionary is

# Add an entry
my_dict['d'] = 'Bootcamp is so much fun!'

# Look at dictionary again

# Change an entry
my_dict['a'] = 'I was not satisfied with entry a.'

# Look at it again
{'c': 12.6, 'b': 7, 'a': 6}
{'d': 'Bootcamp is so much fun!', 'c': 12.6, 'b': 7, 'a': 6}
{'d': 'Bootcamp is so much fun!', 'c': 12.6, 'b': 7, 'a': 'I was not satisfied with entry a.'}

Membership operators with dictionaries

The in and not in operators work with dictionaries, but both only query keys. We see this again by example.

In [40]:
# Make a fresh my_dict
my_dict = {'a': 1, 'b': 2, 'c': 3}

# in works with keys
'b' in my_dict, 'd' in my_dict, 'e' not in my_dict
(True, False, True)
In [41]:
# Try it with values
2 in my_dict

Yup! We get False. Why? Because 2 is not a key in my_dict.

We can also iterate over the keys in a dictionary.

In [51]:
for key in my_dict:
    print(key, ':', my_dict[key])
c : 3
d : 4
a : 1

Notice, again, that there is no sense of order in dictionaries. We can use enumerate() on dictionaries, but the numbers given by enumerate() don't really mean anything.

In [53]:
for i, key in enumerate(my_dict):
    print(i, '   ', key, ':', my_dict[key])
0     c : 3
1     d : 4
2     a : 1

Built-in functions for dictionaries

The built-in len() and del() functions work on dictionaries.

  • len(d) gives the number of entries in dictionary d
  • del d[k] deletes entry with key k from dictionary d

This is the first time we've encountered the del keyword. This keyword is used to delete variables and their values from memory. Just like len() can be used to get the length of lists, the del keyword can also be to delete items from lists. Let's see things in practice.

In [49]:
# Create my_list and my_dict for reference
my_dict = dict(a=1, b=2, c=3, d=4)
my_list = [1, 2, 3, 4]

# Print them
print('my_dict:', my_dict)
print('my_list:', my_list)

# Get lengths
print('length of my_dict:', len(my_dict))
print('length of my_list:', len(my_list))

# Delete a key from my_dict
del my_dict['b']

# Delete entry from my_list
del my_list[1]

# Show post-deleted objects
print('post-deleted my_dict:', my_dict)
print('post-deleted my_list:', my_list)
my_dict: {'c': 3, 'b': 2, 'd': 4, 'a': 1}
my_list: [1, 2, 3, 4]
length of my_dict: 4
length of my_list: 4
post-deleted my_dict: {'c': 3, 'd': 4, 'a': 1}
post-deleted my_list: [1, 3, 4]

Note, though, that you cannot delete an item from a tuple.

In [46]:
my_tuple = (1, 2, 3, 4)
del my_tuple[1]
TypeError                                 Traceback (most recent call last)
<ipython-input-46-477cc61ded22> in <module>()
      1 my_tuple = (1, 2, 3, 4)
----> 2 del my_tuple[1]

TypeError: 'tuple' object doesn't support item deletion

Dictionary methods

Dictionaries have several built-in methods. Following are a few of them, assuming the dictionary is d.

method effect
d.keys() return keys as a tuple
d.pop(key) return value associated with key and delete key from d
d.values() return the (key, value) pairs in d as a tuple

Let's try these out.

In [61]:
my_dict = dict(a=1, b=2, c=3, d=4)
dict_keys(['c', 'b', 'd', 'a'])

Note that this is a dict_keys object. We cannot index it. If, say, we wanted to sort the keys and have them index-able, we would have to convert them to a list.

In [59]:
['a', 'b', 'c', 'd']

Now let's try popping an entry out of the dictionary.

In [62]:
In [63]:
{'a': 1, 'b': 2, 'd': 4}

...and, as we expect, key 'c' is now deleted, and its value was returned in the call to my_dict.pop('c'). Finally, we can look at the values.

In [64]:
dict_values([2, 4, 1])

We get a dict_values object, similar to the dict_keys object we got with the my_dict.keys() method.

You can get more information about build-in methods from the Python documentation.

List methods

As you may guess, the dictionary method pop() has an analog that works for lists. (Why don't the dictionary key() and values() methods work for lists?) We take this opportunity to instroduce a few more useful list methods. Imagine the list is called s.

method effect
s.pop(i) return value at index i and delete it from the list
s.append(x) Put x at the end of the list
s.insert(i, x) Insert x at index i in the list
s.remove(x) Remove the first occurance of x from the list
s.reverse() Reverse the order of items in the list

Using dictionaries as kwargs

A nifty feature of dictionaries is that they can be passed into functions as keyword arguments. We covered named keyword arguments in the Intro to functions lesson. In addition to the named keyword arguments, a function can take in arbitrary keyword arguments (not arbitrary non-keyword arguments). This is specified in the function definition by including a last argument with a double-asterisk, **.

In [71]:
def my_fun(a, b, **kwargs):
    """Concatenate sequences."""
    seq = a + b

    for key in kwargs:
        seq += kwargs[key]
    return seq

Note that kwargs ends up being passed in as a dictionary. Let's try it.

In [72]:

Now, imagine we have a dictionary that contains our values.

In [74]:
my_dict = {'a': 'TGACAC', 
           'b': 'CAGGGA', 
           'c': 'GGGGGGGGG', 
           'd': 'AAAATTTTT'}

We can now pass this directly into the function by preceding it with a double asterisk.

In [75]:

Beautiful! This example is kind of trivial, but you can imagine that it can come in handy, e.g. with large sets of sequence fragments that you read in from a file.