Why Can't the Dictionary Find Card 1042? Good Keys
Find a member's locker from the card scanned this morning, when both of the gym's branches have a member 1042: why the card object, the member number alone and equality on its own each fail, and how to make your own type a key that works in your language.
Journeyman · Data Structures · Updated
After this lesson you can
- Explain why two equal keys must have the same hash code, and the bug when they don't
- Make your own type a safe dictionary key in your language: a record, a frozen dataclass, or a string key
Key takeaways
- A plain object as a key isn't found again with a new, equal object, and a key made from part of the data, such as the member number alone, mixes two members up.
- A dictionary finds a key by its hash code first and checks equality second, so two equal keys must always have the same hash code.
- By default, an object of your own class is equal only to itself, so a new object with the same data isn't found.
- A C# or Java record and a frozen Python dataclass give value equality and a matching hash code for you; in JavaScript, use a string made from the object's data as the key.
- Never change a key while it's in a dictionary: it stays in the bucket of its old hash code, where lookups no longer go.
Before this: The Front Desk Finds You in One Scan: Dictionaries, where a name or a number was the key. Now the key is a type of your own.
The gym on Maple Street has opened a second branch uptown, and both branches number their members from 1. So a member card now says two things: which gym, and which member. Maya's card says Downtown, member 1042, and there's also an Uptown member 1042.
Every member gets a locker, and the app keeps a dictionary from card to locker. Yesterday it stored Maya's: locker 17. This morning she scans her card, the app makes a new card object from the scan, and asks the dictionary for her locker:
Dictionary<MemberCard, int> lockers = new Dictionary<MemberCard, int>();
lockers[new MemberCard("Downtown", 1042)] = 17;
MemberCard scanned = new MemberCard("Downtown", 1042);
bool found = lockers.TryGetValue(scanned, out int locker);
Console.WriteLine("Lockers stored: " + lockers.Count);
Console.WriteLine("Downtown 1042's locker: " + (found ? locker.ToString() : "not found"));
class MemberCard
{
public string Gym;
public int Number;
public MemberCard(string gym, int number)
{
Gym = gym;
Number = number;
}
}
Lockers stored: 1
Downtown 1042's locker: not found
class MemberCard {
String gym;
int number;
MemberCard(String gym, int number) {
this.gym = gym;
this.number = number;
}
}
void main() {
Map<MemberCard, Integer> lockers = new HashMap<>();
lockers.put(new MemberCard("Downtown", 1042), 17);
MemberCard scanned = new MemberCard("Downtown", 1042);
Integer locker = lockers.get(scanned);
IO.println("Lockers stored: " + lockers.size());
IO.println("Downtown 1042's locker: " + (locker == null ? "not found" : locker));
}
Lockers stored: 1
Downtown 1042's locker: not found
class MemberCard:
def __init__(self, gym, number):
self.gym = gym
self.number = number
lockers = {MemberCard("Downtown", 1042): 17}
scanned = MemberCard("Downtown", 1042)
locker = lockers.get(scanned)
print(f"Lockers stored: {len(lockers)}")
print(f"Downtown 1042's locker: {'not found' if locker is None else locker}")
Lockers stored: 1
Downtown 1042's locker: not found
class MemberCard {
constructor(gym, number) {
this.gym = gym;
this.number = number;
}
}
const lockers = new Map();
lockers.set(new MemberCard("Downtown", 1042), 17);
const scanned = new MemberCard("Downtown", 1042);
const locker = lockers.get(scanned);
console.log(`Lockers stored: ${lockers.size}`);
console.log(`Downtown 1042's locker: ${locker ?? "not found"}`);
Lockers stored: 1
Downtown 1042's locker: not found
class MemberCard {
gym: string;
number: number;
constructor(gym: string, number: number) {
this.gym = gym;
this.number = number;
}
}
const lockers = new Map<MemberCard, number>();
lockers.set(new MemberCard("Downtown", 1042), 17);
const scanned = new MemberCard("Downtown", 1042);
const locker = lockers.get(scanned);
console.log(`Lockers stored: ${lockers.size}`);
console.log(`Downtown 1042's locker: ${locker ?? "not found"}`);
Lockers stored: 1
Downtown 1042's locker: not found
The locker is right there, the one entry in the dictionary, and the lookup says "not found". This bug turns up whenever your own objects become keys: an order line keyed by product and size, a seat keyed by row and number, a square on a game board keyed by its column and row.
What would you try?
Tell the class when two cards are equal. Write Equals (equals in Java, __eq__ in Python) to compare the gym and the number. It sounds like the fix, and it isn't. In C# and Java the lookup still says "not found" (C# at least warns you). Python refuses to run it: TypeError: unhashable type: 'MemberCard'. JavaScript has no way to say it at all: a Map compares object keys only by reference.
Use the member number alone as the key. Every dictionary understands numbers, so the lookup works. But both branches have a member 1042:
Dictionary<int, int> lockers = new Dictionary<int, int>();
lockers[1042] = 17;
lockers[1042] = 31;
Console.WriteLine("Lockers stored: " + lockers.Count);
Console.WriteLine("Downtown 1042's locker: " + lockers[1042]);
Lockers stored: 1
Downtown 1042's locker: 31
void main() {
Map<Integer, Integer> lockers = new HashMap<>();
lockers.put(1042, 17);
lockers.put(1042, 31);
IO.println("Lockers stored: " + lockers.size());
IO.println("Downtown 1042's locker: " + lockers.get(1042));
}
Lockers stored: 1
Downtown 1042's locker: 31
lockers = {}
lockers[1042] = 17
lockers[1042] = 31
print(f"Lockers stored: {len(lockers)}")
print(f"Downtown 1042's locker: {lockers[1042]}")
Lockers stored: 1
Downtown 1042's locker: 31
const lockers = new Map();
lockers.set(1042, 17);
lockers.set(1042, 31);
console.log(`Lockers stored: ${lockers.size}`);
console.log(`Downtown 1042's locker: ${lockers.get(1042)}`);
Lockers stored: 1
Downtown 1042's locker: 31
const lockers = new Map<number, number>();
lockers.set(1042, 17);
lockers.set(1042, 31);
console.log(`Lockers stored: ${lockers.size}`);
console.log(`Downtown 1042's locker: ${lockers.get(1042)}`);
Lockers stored: 1
Downtown 1042's locker: 31
Uptown's member 1042 was given locker 31, and that replaced Maya's: two members, one key. The member's name has the same problem the day a second Maya joins.
Glue the two parts into a string, "Downtown-1042". This works in every language: two strings with the same letters are equal, and they hash the same. But it's done by hand, and every place that builds the key has to build it exactly the same way. One screen that writes "downtown-1042" or "Downtown 1042" looks in the wrong place, and nothing warns you.
| What we tried | Maya's locker | Where it breaks |
|---|---|---|
| The card object as it is | not found | a new card is a different object |
The card, with only Equals written |
not found (Python won't run it) | equality is never asked |
| The member number alone | 31, Uptown's | two branches, one number |
A string, "Downtown-1042" |
17 | works, if every screen builds it the same way |
The questions that lead to it
Which bucket did this morning's card go to? Remember how a lookup works, from Collisions: Two Coats, One Hook: hash the key to pick a bucket, then compare the keys in that bucket. A class you write yourself gets a hash code made from the object, not from its data. Yesterday's card and today's are two objects, so they get two different hash codes, and the lookup goes to a bucket where nothing is stored. Equals is only asked inside that bucket, which is why writing it alone changed nothing.
So what would two equal cards need to share? The same hash code, made from the same data the equality compares: the gym and the number.

How it got its name
There are two ways two cards can be "the same", and each has a name:
- The same object: both names point at one card in memory, as in References: Two Names, One Object. That's reference equality, and it's the default for a class you write yourself.
- Equal data: two separate card objects that both say Downtown, 1042. That's value equality, and it's what a key needs.
The rule every language states, and the one the plain card broke: two equal objects must have the same hash code. Two different objects may share a hash code; that's a collision, and chaining handles it.
The fix
This code stores a locker under a card twice: once with a plain class as the key, and once with a type that has value equality built in:
Dictionary<PlainCard, int> plainLockers = new Dictionary<PlainCard, int>();
plainLockers[new PlainCard("Downtown", 1042)] = 17;
bool plainFound = plainLockers.ContainsKey(new PlainCard("Downtown", 1042));
Console.WriteLine("Plain object as the key: " + (plainFound ? "found" : "not found"));
Dictionary<Card, int> lockers = new Dictionary<Card, int>();
lockers[new Card("Downtown", 1042)] = 17;
bool found = lockers.TryGetValue(new Card("Downtown", 1042), out int locker);
Console.WriteLine("Key with value equality: " + (found ? "found locker " + locker : "not found"));
class PlainCard
{
public string Gym;
public int Number;
public PlainCard(string gym, int number)
{
Gym = gym;
Number = number;
}
}
record Card(string Gym, int Number);
Plain object as the key: not found
Key with value equality: found locker 17
class PlainCard {
String gym;
int number;
PlainCard(String gym, int number) {
this.gym = gym;
this.number = number;
}
}
record Card(String gym, int number) {}
void main() {
Map<PlainCard, Integer> plainLockers = new HashMap<>();
plainLockers.put(new PlainCard("Downtown", 1042), 17);
boolean plainFound = plainLockers.containsKey(new PlainCard("Downtown", 1042));
IO.println("Plain object as the key: " + (plainFound ? "found" : "not found"));
Map<Card, Integer> lockers = new HashMap<>();
lockers.put(new Card("Downtown", 1042), 17);
Integer locker = lockers.get(new Card("Downtown", 1042));
IO.println("Key with value equality: " + (locker != null ? "found locker " + locker : "not found"));
}
Plain object as the key: not found
Key with value equality: found locker 17
from dataclasses import dataclass
class PlainCard:
def __init__(self, gym, number):
self.gym = gym
self.number = number
@dataclass(frozen=True)
class Card:
gym: str
number: int
plain_lockers = {PlainCard("Downtown", 1042): 17}
plain_found = PlainCard("Downtown", 1042) in plain_lockers
print(f"Plain object as the key: {'found' if plain_found else 'not found'}")
lockers = {Card("Downtown", 1042): 17}
locker = lockers.get(Card("Downtown", 1042))
print(f"Key with value equality: {'not found' if locker is None else f'found locker {locker}'}")
Plain object as the key: not found
Key with value equality: found locker 17
const plainLockers = new Map();
plainLockers.set({ gym: "Downtown", number: 1042 }, 17);
const plainFound = plainLockers.has({ gym: "Downtown", number: 1042 });
console.log(`Plain object as the key: ${plainFound ? "found" : "not found"}`);
function cardKey(gym, number) {
return `${gym}-${number}`;
}
const lockers = new Map();
lockers.set(cardKey("Downtown", 1042), 17);
const locker = lockers.get(cardKey("Downtown", 1042));
console.log(`Key with value equality: ${locker === undefined ? "not found" : `found locker ${locker}`}`);
Plain object as the key: not found
Key with value equality: found locker 17
const plainLockers = new Map<{ gym: string; number: number }, number>();
plainLockers.set({ gym: "Downtown", number: 1042 }, 17);
const plainFound = plainLockers.has({ gym: "Downtown", number: 1042 });
console.log(`Plain object as the key: ${plainFound ? "found" : "not found"}`);
function cardKey(gym: string, number: number): string {
return `${gym}-${number}`;
}
const lockers = new Map<string, number>();
lockers.set(cardKey("Downtown", 1042), 17);
const locker = lockers.get(cardKey("Downtown", 1042));
console.log(`Key with value equality: ${locker === undefined ? "not found" : `found locker ${locker}`}`);
Plain object as the key: not found
Key with value equality: found locker 17
The fix in each language:
- C#: a
record. It writesEqualsandGetHashCodefor you, both made from all its data. - Java: a
record. It writesequalsandhashCodefor you, the same way. - Python: a
@dataclass(frozen=True). It writes__eq__and__hash__, and "frozen" means its fields can't change. - JavaScript and TypeScript: a
Mapcompares object keys only by reference, and there's no way to change that. Use a string made from the data, such as"Downtown-1042", as the key, and build it in one function, ascardKeydoes, so every screen makes it the same way.
Writing it by hand
Sometimes a key has to be an ordinary class. Then you write both halves of equality yourself, from the same fields: Equals and GetHashCode in C#, equals and hashCode in Java, __eq__ and __hash__ in Python. Each language has a helper that builds a good hash code from several fields: HashCode.Combine, Objects.hash and hash of a tuple. JavaScript and TypeScript have nothing to override, so the class gives the Map a string key instead:
Dictionary<MemberCard, int> lockers = new Dictionary<MemberCard, int>();
lockers[new MemberCard("Downtown", 1042)] = 17;
Console.WriteLine("Locker: " + lockers[new MemberCard("Downtown", 1042)]);
class MemberCard
{
public string Gym { get; }
public int Number { get; }
public MemberCard(string gym, int number)
{
Gym = gym;
Number = number;
}
public override bool Equals(object? other)
{
return other is MemberCard card && card.Gym == Gym && card.Number == Number;
}
public override int GetHashCode()
{
return HashCode.Combine(Gym, Number);
}
}
Locker: 17
class MemberCard {
final String gym;
final int number;
MemberCard(String gym, int number) {
this.gym = gym;
this.number = number;
}
@Override
public boolean equals(Object other) {
return other instanceof MemberCard card && card.gym.equals(gym) && card.number == number;
}
@Override
public int hashCode() {
return Objects.hash(gym, number);
}
}
void main() {
Map<MemberCard, Integer> lockers = new HashMap<>();
lockers.put(new MemberCard("Downtown", 1042), 17);
IO.println("Locker: " + lockers.get(new MemberCard("Downtown", 1042)));
}
Locker: 17
class MemberCard:
def __init__(self, gym, number):
self.gym = gym
self.number = number
def __eq__(self, other):
return isinstance(other, MemberCard) and other.gym == self.gym and other.number == self.number
def __hash__(self):
return hash((self.gym, self.number))
lockers = {MemberCard("Downtown", 1042): 17}
print(f"Locker: {lockers[MemberCard('Downtown', 1042)]}")
Locker: 17
class MemberCard {
constructor(gym, number) {
this.gym = gym;
this.number = number;
}
key() {
return `${this.gym}-${this.number}`;
}
}
const lockers = new Map();
lockers.set(new MemberCard("Downtown", 1042).key(), 17);
console.log(`Locker: ${lockers.get(new MemberCard("Downtown", 1042).key())}`);
Locker: 17
class MemberCard {
readonly gym: string;
readonly number: number;
constructor(gym: string, number: number) {
this.gym = gym;
this.number = number;
}
key(): string {
return `${this.gym}-${this.number}`;
}
}
const lockers = new Map<string, number>();
lockers.set(new MemberCard("Downtown", 1042).key(), 17);
console.log(`Locker: ${lockers.get(new MemberCard("Downtown", 1042).key())}`);
Locker: 17
The classic bug is writing only one half. In C# and Java, a class that overrides Equals but not GetHashCode (equals but not hashCode) compiles and runs, and its equal objects land in different buckets: the picture above. C# warns about it; Java doesn't. Python refuses outright: a class that defines __eq__ without __hash__ can't be a key at all (TypeError: unhashable type). Override both, from the same fields, every time.
Keys must not change
There's one more way to lose a key: change it after it's stored. If Maya's card moves from Downtown to Uptown while it's a key, its hash code changes, but the entry stays in the bucket of the old hash code. Lookups with the new data go to a new bucket and find nothing; lookups with the old data find the bucket but fail the equality check.
So keys should be immutable: impossible to change once made. Strings, numbers, records (C# and Java make their fields read-only), and frozen dataclasses all are. It's also why Python won't let a list be a key: a list can change.
Which key?
For the lockers, the key is the gym and the number together, as a record, a frozen dataclass or a cardKey string: exactly the data that makes one member one member. The member number alone is smaller and quicker to hash, and it was a fine key until the second branch opened. A name is friendly and never safe, because two people can share one. And a wrong key never complains: the dictionary finds nothing, or quietly finds someone else's locker.
Check yourself
2 questions to try on the lesson page.
So what
A key is a promise: equal data, equal hash code, and no changes while it's stored. Records, frozen dataclasses and string keys keep that promise for you, and they're the first thing to reach for when your own type becomes a key.