Section 7.5. Dictionary Keys

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 (most recent) 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 nonexistent 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 Hashable

As we mentioned earlier in Section 7.1, most Python objects can serve as keys; however they have to be hashable objectsmutable types such as lists and dictionaries are disallowed because they cannot be hashed.

All immutable types are hashable, so they can definitely be used as keys. One caveat is numbers: Numbers of the same value represent the same key. In other words, the integer 1 and the float 1.0 hash to the same value, meaning that they are identical as keys.

Also, there are some mutable objects that are (barely) hashable, so they are eligible as keys, but there are very few of them. One example would be a class that has implemented the __hash__() special method. In the end, an immutable value is used anyway as __hash__() must return an integer.

Why must keys be hashable? 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. Hashable keys were chosen for the very fact that their values cannot change. (This question can also be found in the Python FAQ.)

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 could be. The clearest example of that was when we modified a list object that 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) that manages usernames 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 the user gives the login and correct password. New users cannot create an entry with an existing login name.

Example 7.1. Dictionary Example (userpw.py)

This application manages a set of users who join the system with a login name and a password. Once established, existing users can return as long as they remember their login and password. New users cannot create an entry with someone else's login name.

1  #!/usr/bin/env python 2 3  db = {} 4 5  def newuser(): 6      prompt = 'login desired: ' 7      while True: 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         print 'welcome back', name 23     else: 24         print 'login incorrect' 25 26 def showmenu(): 27     prompt = """ 28 (N)ew User Login 29 (E)xisting User Login 30 (Q)uit 31 32 Enter choice: """ 33 34 done = False 35     while not done: 36 37         chosen = False 38         while not chosen: 39             try: 40                choice =    raw_input(prompt).strip()[0].lower() 41            except (EOFError, KeyboardInterrupt): 42                choice = 'q' 43            print '\nYou picked: [%s]' % choice 44            if choice not in 'neq': 45                print 'invalid option, try again' 46            else: 47                chosen = True 48 49       if choice == 'q': done = True 50       if choice == 'n': newuser() 51       if choice == 'e': olduser() 52 53 if __name__ == '__main__': 54     showmenu()

Line-by-Line Explanation

Lines 13

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 515

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 1724

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 2651

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 '\n' 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 5354

This is the familiar code that 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]