Card 08/ 10
A Key Whose Hash or Equality Can Change
A key that changes after insertion, or compares by identity, is a key the map cannot find.
A hash map finds a key by its hash code and then by equality, so a key whose hash code or equality changes after it is stored, or that is equal only to itself, is a key the map cannot find. This card covers the rule a key must follow, and what breaks it in Python, Java and TypeScript.
The symptom is a lookup that returns nothing for a key that is plainly in the map. The trigger is a key whose fields change after it is stored, or a lookup with a second object whose fields match the stored one. The mechanism is the two steps of every lookup: hash the key to choose a bucket, then compare it by equality with the keys there. Both steps must give the answers they gave when the key was stored, and two equal keys must have the same hash code, or the lookup searches the wrong bucket.
Python refuses a list as a key with a TypeError, because a list can change; a tuple, which cannot, is the fix. A class can define its own hash and equality from its fields, as Point does here, and then changing a field strands the key. In Java, a class that overrides equals without hashCode keeps the default hashCode, which is tied to each object rather than its fields, so an equal Point almost always lands in another bucket; a record, whose fields cannot change and which writes both methods from them, is the fix. A TypeScript Map compares object keys by reference, meaning two objects are the same key only when they are one object, so a second object with the same fields is a different key. The highlighted lines are each cause and fix.
A key the map cannot find, and the fix, in each language
class Point:
def __init__(self, x: int, y: int) -> None:
self.x = x
self.y = y
def __eq__(self, other: object) -> bool:
return isinstance(other, Point) and (self.x, self.y) == (other.x, other.y)
def __hash__(self) -> int:
return hash((self.x, self.y))
shelves: dict[object, str] = {}
try:
shelves[[1, 2]] = "shelf A"
except TypeError as error:
print(f"list key: TypeError: {error}")
point = Point(1, 2)
shelves[point] = "shelf B"
point.x = 9
print(f"after moving the key: Point(9, 2) found {Point(9, 2) in shelves}, Point(1, 2) found {Point(1, 2) in shelves}")
shelves[(1, 2)] = "shelf A"
print(f"tuple key: {shelves[(1, 2)]}")list key: TypeError: cannot use 'list' as a dict key (unhashable type: 'list')
after moving the key: Point(9, 2) found False, Point(1, 2) found False
tuple key: shelf Aimport java.util.HashMap;
import java.util.Map;
public class KeysThatChange {
static final class Point {
final int x;
final int y;
Point(int x, int y) {
this.x = x;
this.y = y;
}
@Override
public boolean equals(Object other) {
return other instanceof Point point && point.x == x && point.y == y;
}
}
record FixedPoint(int x, int y) {}
public static void main(String[] args) {
Map<Point, String> shelves = new HashMap<>();
shelves.put(new Point(1, 2), "shelf A");
System.out.println("equals says equal: " + new Point(1, 2).equals(new Point(1, 2)));
System.out.println("equals without hashCode: " + shelves.get(new Point(1, 2)));
Map<FixedPoint, String> fixed = new HashMap<>();
fixed.put(new FixedPoint(1, 2), "shelf A");
System.out.println("record key: " + fixed.get(new FixedPoint(1, 2)));
}
}equals says equal: true
equals without hashCode: null
record key: shelf Atype Point = { x: number; y: number };
const shelves = new Map<Point, string>();
const stored: Point = { x: 1, y: 2 };
shelves.set(stored, "shelf A");
console.log(`a new object with the same fields: ${shelves.get({ x: 1, y: 2 })}`);
console.log(`the same object: ${shelves.get(stored)}`);
const keyOf = (point: Point): string => `${point.x},${point.y}`;
const byValue = new Map<string, string>();
byValue.set(keyOf({ x: 1, y: 2 }), "shelf A");
console.log(`a string key built from the fields: ${byValue.get(keyOf({ x: 1, y: 2 }))}`);a new object with the same fields: undefined
the same object: shelf A
a string key built from the fields: shelf AThe two failed lookups in Python show both steps going wrong. Point(9, 2) hashes to a different bucket from the one the key was stored in, and Point(1, 2) reaches the right bucket but is no longer equal to the key there. The cost is silent: the entry stays in the map and appears when it is listed, yet no lookup can reach it.
The rule in every language: a key's hash code and equality must depend only on fields that never change, and equal keys must have equal hash codes. Use values that cannot change, such as strings, numbers, tuples and records, or build a string from the fields, as the TypeScript fix does.
← → move through sections and cards