Choice made by Python 3.5 to choose the keys when comparing them in a dictionary

When constructing a dictionary as follows:

    dict = { True: 'yes', 1: 'No'}

When I run it in the interactive Python interpreter the dict is represented this way:

    dict = {True: 'No'}

I understand that the values True and 1 are equal due to the type coercion because when comparing numeric types, the narrowed type is widened to the other type (boolean is a child of integer). So as I understood from the documentation, when we enter True == 1 Python converts True to 1 and compares them.

What I don't understand is why the True is selected as a key instead of 1.

I am missing something?

Dictionaries are implemented as hash tables and there are two important concepts when adding keys/values here: hashing and equality.

To insert a particular key/value, Python first computes the hash value of the key. This hash value is used to determine the row of the table where Python should first attempt to put the key/value.

If the row of the hash table is empty, great: the new key/value can inserted into the dictionary, filling the empty row.

However, if there's already something in that row, Python needs to test the keys for equality. If the keys are equal (using ==) then they're deemed to be the same key and Python just needs to update the corresponding value on that row.

(If the keys are not equal Python looks at other rows in the table until it finds the key or reaches an empty row, but that's not relevant for this question.)

When you write {True: 'yes', 1: 'No'}, you are telling Python to create a new dictionary and then fill it with two key/value pairs. These are processed left to right: True: 'yes' then 1: 'No'.

We have hash(True) equals 1. The key True goes in at row 1 in the hash table and the string 'yes' is its value.

For the next pair, Python sees that hash(1) is also 1 and so looks at row 1 of the table. There's something already there, so now Python checks the keys for equality. We have 1 == True so 1 is deemed to be the same key as True and so its corresponding value is changed to the string 'No'.

This results in a dictionary with one entry: {True: 'No'}.

If you want to peer at the guts of CPython 3.5 to see what creating a dictionary looks below the surface-Python level, here's more detail.

  • The Python code {True: 'yes', 1: 'No'} is parsed into tokens and given to the compiler. Given the syntax, Python knows that a dictionary must be created using the values inside the braces. Byte code to load the four values onto the virtual machine's stack (LOAD_CONST) and then build the dictionary (BUILD_MAP) is queued up.

  • The four constant values are pushed onto the top of the stack in the order that they're seen:

     'No'
    1
    'yes'
    True
  • The opcode BUILD_MAP is then called with the argument 2 (Python counted two key/value pairs). This opcode is responsible for actually creating dictionary from the items on the stack. It looks like this:
     TARGET(BUILD_MAP) {
        int i;
        PyObject *map = _PyDict_NewPresized((Py_ssize_t)oparg);
        if (map == NULL)
            goto error;
        for (i = oparg; i > 0; i--) {
            int err;
            PyObject *key = PEEK(2*i);
            PyObject *value = PEEK(2*i - 1);
            err = PyDict_SetItem(map, key, value);
            if (err != 0) {
                Py_DECREF(map);
                goto error;
            }
        }

        while (oparg--) {
            Py_DECREF(POP());
            Py_DECREF(POP());
        }
        PUSH(map);
        DISPATCH();
    }

The three key steps here are as follows:

  1. An empty hashtable is created using _PyDict_NewPresized. Small dictionaries (of just a few items, like 2 in this case) need a table with eight rows.

  2. The for loop is entered, starting at 2 (in this case) and counting down to 0. PEEK(n) is a macro that points to the nth item down the stack. Therefore on the first iteration of the loop, we'll have

    PyObject *key = PEEK(2*2);       /* item 4 down the stack */  
    PyObject *value = PEEK(2*2 - 1); /* item 3 down the stack */

This means that *key will be True and *value will be 'yes' on the first loop through. On the second it will be 1 and 'No'.

  1. PyDict_SetItem is called in each loop to put the current *key and *value into the dictionary. This is the same function that is called when you write dictionary[key] = value. It computes the hash of the key to work out where to look first in the hash table and then, if needed, compare the key to any existing key on that row (as discussed above).

From: stackoverflow.com/q/37164127

Back to homepage or read more recommendations: