7.5. Dictionary Keys

Dictionary values have no restrictions. They can be any arbitrary Python object, i.e., from standard objects to user-defined objects. However, the same cannot be said of keys.

7.5.1. More Than One Entry per Key Not Allowed

One rule is that you are constrained to having only one entry per key. In other words, multiple values per the same key are not allowed. (Container objects such as lists, tuples, and other dictionaries are fine.) When key collisions are detected (meaning duplicate keys encountered during assignment), the last assignment wins.

>>> dict1 = {' foo':789, 'foo': 'xyz'}
>>> dict1
{'foo': 'xyz'}
>>>
>>> dict1['foo'] = 123
>>> dict1
{'foo': 123}

Rather than producing an error, Python does not check for key collisions because that would involve taking up memory for each key-value pair assigned. In the above example where the key 'foo' is given twice on the same line, Python applies the key-value pairs from left to right. The value 789 may have been set at first, but is quickly replaced by the string 'xyz'. When assigning a value to a non-existent key, the key is created for the dictionary and value added, but if the key does exist (a collision), then its current value is replaced. In the above example, the value for the key 'foo' is replaced twice; in the final assignment, 'xyz' is replaced by 123.

7.5.2. Keys Must Be Immutable

As we mentioned earlier in Section 7.1, most Python objects can serve as keys—only mutable types such as lists and dictionaries are disallowed. In other words, types that compare by value rather than by identity cannot be used as dictionary keys. A TypeError will occur if a mutable type is given as the key:

>>> dict[[3]] = 14
Traceback (innermost last):
  File "<stdin>," line 1, in ?
TypeError: unhashable type

Why must keys be immutable? The hash function used by the interpreter to calculate where to store your data is based on the value of your key. If the key was a mutable object, its value could be changed. If a key changes, the hash function will map to a different place to store the data. If that was the case, then the hash function could never reliably store or retrieve the associated value. Immutable keys were chosen for the very fact that their values cannot change. (Also see the Python FAQ question 6.18.)

We know that numbers and strings are allowed as keys, but what about tuples? We know they are immutable, but in Section 6.17.2, we hinted that they might not be as immutable as they can be. The clearest example of that was when we modified a list object which was one of our tuple elements. To allow tuples as valid keys, one more restriction must be enacted: Tuples are valid keys only if they only contain immutable arguments like numbers and strings.

We conclude this chapter on dictionaries by presenting a program (userpw.py as in Example 7.1), which manages user name and passwords in a mock login entry database system. This script accepts new users given that they provide a login name and a password. Once an “account” has been set up, an existing user can return as long as they give their login and correct password. New users cannot create an entry with an existing login name.

Listing 7.1. Dictionary Example (userpw.py)

1  #!/usr/bin/env python
2
3  db = {}
4
5  def newuser():
6      prompt = 'login desired: '
7      while 1:
8          name = raw_input(prompt)
9          if db.has_key(name):
10             prompt = 'name taken, try another: '
11             continue
12         else:
13             break
14     pwd = raw_input('passwd: ')
15     db[name] = pwd
16
17 def olduser():
18     name = raw_input('login: ')
19     pwd = raw_input('passwd: ')
20     passwd = db.get(name)
21     if passwd == pwd:
22         pass
23     else:
24         print 'login incorrect'
25         return
26
27     print 'welcome back', name
28
29 def showmenu():
30     prompt = """
31 (N)ew User Login
32 (E)xisting User Login
33 (Q)uit
34
35 Enter choice: """
36
37     done = 0
38     while not done:
39
40         chosen  = 0
41         while not chosen:
42             try:
43                 choice = raw_input(prompt)[0]
44             except (EOFError, KeyboardInterrupt):
45                 choice = 'q'
46             print '
You picked: [%s]' % choice
47             if choice not in 'neq':
48                 print 'invalid option, try again'
49             else:
50                 chosen = 1
51
52         if choice == 'q': done = 1
53         if choice == 'n': newuser()
54         if choice == 'e': olduser()
55
56 if __name__ == '__main__':
57     showmenu()

Lines 1 – 3

After the UNIX-startup line, we initialize the program with an empty user database. Because we are not storing the data anywhere, a new user database is created every time this program is executed.

Lines 5 – 15

The newuser() function is the code that serves new users. It checks to see if a name has already been taken, and once a new name is verified, the user is prompted for his or her password (no encryption exists in our simple program), and his or her password is stored in the dictionary with his or her user name as the key.

Lines 17 – 27

The olduser() function handles returning users. If a user returns with the correct login and password, a welcome message is issued. Otherwise, the user is notified of an invalid login and returned to the menu. We do not want an infinite loop here to prompt for the correct password because the user may have inadvertently entered the incorrect menu option.

Lines 29 – 54

The real controller of this script is the showmenu() function. The user is presented with a friendly menu. The prompt string is given using triple quotes because it takes place over multiple lines and is easier to manage on multiple lines than on a single line with embedded ' ' symbols. Once the menu is displayed, it waits for valid input from the user and chooses which mode of operation to follow based on the menu choice. The try-except statements we describe here are the same as for the stack.py and queue.py examples from the last chapter (see Section 6.14.1).

Lines 56 – 57

Here is the familiar code which will only call showmenu() to start the application if the script was involved directly (not imported).

Here is a sample execution of our script:

% userpw.py

(N)ew User Login
(E)xisting User Login
(Q)uit

Enter choice: n

You picked: [n]
login desired: king arthur
passwd: grail

(N)ew User Login
(E)xisting User Login
(Q)uit

Enter choice: e

You picked: [e]
login: sir knight
passwd: flesh wound
login incorrect

(N)ew User Login
(E)xisting User Login
(Q)uit

Enter choice: e

You picked: [e]
login: king arthur
passwd: grail
welcome back king arthur

(N)ew User Login
(E)xisting User Login
(Q)uit

Enter choice: ^D
You picked: [q]