Keys That Compare Equal

Concepts covered: Collections, Frequency Counting

Predict what this prints before you open the output: 3 keys, 3 different types.

d = {1: "int", 1.0: "float", True: "bool"}
print(d)
print(len(d))

Output:

{1: 'bool'}
1

The dict saw 3 writes to 1 key. The first key object, the int 1, stays in place. Each later write found an equal key already stored and replaced only the value, so the last value, 'bool', wins. 1.0 and True land on the same key as 1 because they compare equal to it with == and produce the same hash.

Hash first, then equality

A dict decides whether 2 keys are the same in 2 steps. First it calls hash(key), a built-in that turns the key into an integer, and uses that integer to choose where in its internal table to look. Then it compares the key stored there with ==. Python guarantees that values which compare equal have equal hashes. Ints and floats keep that promise with each other, and so does bool:

print(hash(1), hash(1.0), hash(True))
print(hash(0), hash(0.0), hash(False))
print(1 == 1.0 == True, "1" == 1)
print(hash(2.5) == hash(2))

Output:

1 1 1
0 0 0
True False
False

The string "1" and the int 1 are unequal, so they stay 2 keys whatever their hashes. The animation below runs a simplified dict with 8 slots: put stores a key in the slot its hash picks, stepping right past slots that hold other keys, and get counts the slots it checks.

slots = [None] * 8

def put(key, value):
    i = hash(key) % 8
    while slots[i] is not None:
        if slots[i][0] == key:
            slots[i][1] = value
            return
        i = (i + 1) % 8
    slots[i] = [key, value]

def get(key):
    i = hash(key) % 8
    checks = 0
    while slots[i] is not None:
        checks += 1
        if slots[i][0] == key:
            return slots[i][1], checks
        i = (i + 1) % 8
    return None, checks

put(3, "red")
put(1, "one")
put(11, "blue")
put(1.0, "uno")
put(True, "yes")
print(slots)
print(get(11))
print(get(1))
print(get(19))

[None, [1, 'yes'], None, [3, 'red'], [11, 'blue'], None, None, None]
('blue', 2)
('yes', 1)
(None, 2)

Key 11 hashed to slot 3, found 3 already there, and stepped on to slot 4, which is why get(11) needed 2 checks. Keys 1.0 and True both landed on slot 1, compared equal to the stored 1, and replaced its value while the key stayed 1. A miss such as get(19) stops at the first empty slot. A real dict also stores each key's hash and compares hashes before calling ==, so stepping past a slot that holds a different key rarely costs an == call.

Where equal keys meet in real data

The collapse appears when 2 sources describe the same ID in different types. Here one feed delivers user IDs as ints, another as floats, a third as text:

totals = {}
for user_id, amount in [[101, 20], [101.0, 5], ["101", 7]]:
    totals[user_id] = totals.get(user_id, 0) + amount
print(totals)

Output:

{101: 25, '101': 7}

The float row merged into the int key, which is what you want here. The string row became a separate entry, a silent split in the totals. Convert IDs to 1 type where data comes in, before they become keys; int() or str() will do it.

Floats add 2 more traps. float("nan") is unequal to itself, so a fresh NaN never matches a stored one, and 0.1 + 0.2 is a different float from 0.3. A dict finds a NaN key only when you look it up with the very same object, through an identity check Python runs before ==:

nan = float("nan")
d = {nan: "missing", 0.3: "thirty"}
print(nan == nan)
print(nan in d, float("nan") in d)
print((0.1 + 0.2) in d)
d[float("nan")] = "again"
print(len(d))

Output:

False
True False
False
3

What does this program print?

d = {}
d[0] = "zero"
d[False] = "no"
d[0.0] = "none"
d["0"] = "text"
print(len(d), d[0])

• 2 none
• 4 zero
• 2 zero
• 3 none

Your own classes as keys

An object of your own class equals only itself unless the class defines __eq__, and its default hash comes from its identity. To make 2 objects with the same field act as 1 key, define __eq__ and base __hash__ on the same fields it compares. A class that defines __eq__ alone gets __hash__ set to None, so its objects can no longer be keys:

class Sku:
    def __init__(self, code):
        self.code = code

    def __eq__(self, other):
        return isinstance(other, Sku) and self.code == other.code

    def __hash__(self):
        return hash(self.code)

class Plain:
    def __init__(self, code):
        self.code = code

    def __eq__(self, other):
        return self.code == other.code

stock = {Sku("A-100"): 4}
print(stock[Sku("A-100")])
print(Sku("A-100") in stock, Sku("B-200") in stock)

try:
    {Plain("A-100"): 4}
except TypeError as err:
    print("cannot be a key:", err)

Output:

4
True False
cannot be a key: unhashable type: 'Plain'

About this lesson

This section is part of the Dictionaries: Advanced lesson on DataDriven, the home of data engineering. Lessons cover SQL, Python, Spark, data modeling and pipeline architecture, and each section pairs its explanation with worked examples and practice you run as you go.