Custom keys

Why this matters

A hash table needs two things from a key. It needs a way to decide that two keys are the same, and it needs a number for each key that does not change. The standard library already knows both for int, std::string and a few other types. Your own class has neither until you write them.

Real programs use their own types as keys all the time. A chess program might use a board square. A game might use a grid cell. A school system might use a student record. Each of those is a class you define, and if you want to look it up in a hash table, you have to teach the table how to compare and hash it.

The previous lesson showed what happens inside a hash table. Keys go into buckets chosen by a hash function. Equal keys must end up in the same bucket, so the table can find them. This lesson shows how to write the two pieces that make that work for your own type.

The two rules

A hash table does two checks when you look up a key.

1. It computes a number from the key, called the hash. It uses the hash to pick a bucket.
2. It compares the key with the keys already in that bucket, using an equality test. If one of them is equal, that is the entry it wanted.

Both checks have to agree. Here is the rule in plain words:

• If two keys are equal, their hashes must be equal.
• A hash may be equal for two keys that are not equal. That is a collision, and the table can live with it.

The first rule is the one people break. If two equal keys produce different hashes, they can end up in different buckets. The table then looks in one bucket, does not find the key, and reports it as missing. The program does not crash. It just gives wrong answers.

Here is a concrete case. Suppose a key is a point on a grid, with an x and a y. The points (1, 2) and (1, 2) are equal. If the hash for each of them is computed the same way, they land in the same bucket, and the table finds the second one. If the hash for one of them used a different formula, the second point could land somewhere else, and the table would say it was never inserted.

The Java version of this idea

In Java, a class that can be a key defines two methods. equals decides whether two objects are the same. hashCode returns the number used for the bucket. Java's HashMap and HashSet call hashCode to pick the bucket, and then call equals to confirm the match. The rule is the same as in C++: if equals says two objects are equal, their hashCode values must match.

C++ splits the job differently. Equality is an operator, written operator==. The hash is a separate piece: you write a specialization of std::hash for your type. A specialization is a version of a standard template written for one type. The standard containers look for it when you use your type as a key. The rest of this lesson shows the C++ version, with the same two rules.

Step 1: equality with operator ==

The first step is to say when two values of your type are equal. In C++20 you can ask the compiler to compare every member for you.

#include <iostream>
 
struct Point {
    int x;
    int y;
    bool operator==(const Point&) const = default;
};
 
int main() {
    Point a{1, 2};
    Point b{1, 2};
    Point c{2, 1};
    std::cout << "a == b: " << (a == b) << "\n";
    std::cout << "a == c: " << (a == c) << "\n";
    return 0;
}

The line bool operator==(const Point&) const = default; tells the compiler to generate the comparison. Two points are equal when their x values match and their y values match. The word const after the parentheses means the comparison does not change either point. The word default means "use the member-by-member comparison".

Equality alone is not enough for a hash table. The table still has no way to pick a bucket for a Point. Step 2 adds that.

Step 2: a hash specialization

The standard library has a template called std::hash. Its general form does nothing useful. For each built-in type it has a specialization that returns a number. You can add a specialization for your own type.

You must put this specialization inside the std namespace, which is the namespace that holds the standard library. The example below does that with a namespace std { ... } block.

#include <cstddef>
#include <functional>
#include <iostream>
#include <unordered_map>
#include <unordered_set>
 
struct Point {
    int x;
    int y;
    bool operator==(const Point&) const = default;
};
 
namespace std {
template <>
struct hash<Point> {
    std::size_t operator()(const Point& p) const noexcept {
        std::size_t h1 = std::hash<int>{}(p.x);
        std::size_t h2 = std::hash<int>{}(p.y);
        return h1 ^ (h2 + 0x9e3779b9 + (h1 << 6) + (h1 >> 2));
    }
};
}  // namespace std
 
int main() {
    std::unordered_set<Point> visited;
    visited.insert(Point{1, 2});
    visited.insert(Point{2, 1});
    visited.insert(Point{1, 2});  // same point as before, not added again
 
    std::cout << "size = " << visited.size() << "\n";
    std::cout << "has (1,2) = " << visited.contains(Point{1, 2}) << "\n";
    std::cout << "has (3,3) = " << visited.contains(Point{3, 3}) << "\n";
 
    std::unordered_map<Point, std::string> labels;
    labels[Point{0, 0}] = "origin";
    labels[Point{5, 7}] = "tower";
    std::cout << "label of (5,7) = " << labels.at(Point{5, 7}) << "\n";
    return 0;
}

Compile and run it:

g++ -std=c++20 -Wall -Wextra -o point point.cpp
./point

Output:

size = 2
has (1,2) = 1
has (3,3) = 0
label of (5,7) = tower

The set has size 2 because the second insert of Point{1, 2} found an equal point already there and did nothing. The map works in the same way. The two Point keys are now usable with any unordered container.

Look at the body of operator(). It takes each field, hashes it with the standard hash for int, and mixes the two results. The line with 0x9e3779b9 is a common constant from the literature on hashing. It is there to spread the bits of the result, so that points such as (1, 2) and (2, 1) do not get the same number. The exact formula is a choice. The rule that matters is that the function uses every field that operator== uses.

Step 3: a key with more than one field

Points have two integers, which is easy. Real keys often mix types. The next example uses a name, which is a std::string, and a start year, which is an int. The standard hash for each field is already written, so the new work is to combine them. A helper function called hashCombine does the mixing. It can be reused for any number of fields.

#include <cstddef>
#include <functional>
#include <iostream>
#include <string>
#include <unordered_map>
 
struct Employee {
    std::string name;
    int startYear;
    bool operator==(const Employee&) const = default;
};
 
template <typename T>
void hashCombine(std::size_t& seed, const T& value) {
    seed ^= std::hash<T>{}(value) + 0x9e3779b9 + (seed << 6) + (seed >> 2);
}
 
namespace std {
template <>
struct hash<Employee> {
    std::size_t operator()(const Employee& e) const noexcept {
        std::size_t seed = 0;
        hashCombine(seed, e.name);
        hashCombine(seed, e.startYear);
        return seed;
    }
};
}  // namespace std
 
int main() {
    std::unordered_map<Employee, std::string> desks;
    desks[Employee{"Priya", 2019}] = "desk 4";
    desks[Employee{"Priya", 2023}] = "desk 9";
    desks[Employee{"Sam", 2019}] = "desk 2";
 
    std::cout << "entries = " << desks.size() << "\n";
    std::cout << "Priya 2019 -> " << desks.at(Employee{"Priya", 2019}) << "\n";
    std::cout << "Priya 2023 -> " << desks.at(Employee{"Priya", 2023}) << "\n";
 
    auto it = desks.find(Employee{"Priya", 2020});
    std::cout << "Priya 2020 found = " << (it != desks.end()) << "\n";
    return 0;
}

Output:

entries = 3
Priya 2019 -> desk 4
Priya 2023 -> desk 9
Priya 2020 found = 0

The two Priyas are different keys, because their start years differ. The table keeps both. The third employee, Sam, is a third key. The lookup for Priya in 2020 finds nothing, so find returns end(), which is the table's way of saying "not found".

Notice what hashCombine does. It starts from a seed of 0, mixes in the hash of the name, and then mixes in the hash of the year. The order matters. Swapping the two calls would give a different number, but the table would still work, because the same order is used on every call.

The fields are hashed in the same order as the comparison, so equal employees always get the same seed. If operator== compared the name and the year, the hash must use the name and the year. A hash that used only the name would still be correct, but Priya in 2019 and Priya in 2023 would collide every time, and a table with many people named Priya would slow down.

Example 4: equality that ignores case

Sometimes equality is not the same as comparing every byte. Suppose a city name should match no matter how it is capitalised, so "Paris", "paris" and "PARIS" count as one city. Then operator== must compare the letters without case, and the hash must give the same number to all three spellings. If the hash used the original text, the three spellings would land in different buckets, and the set would keep all three.

The program below writes both functions by hand. The comparison turns each letter to lower case before it compares. The hash does the same, then mixes each letter into a running number. The h * 31 step is a common way to mix characters, and it is only one choice among many.

#include <cctype>
#include <cstddef>
#include <functional>
#include <iostream>
#include <string>
#include <unordered_set>
 
struct City {
    std::string name;
    bool operator==(const City& other) const {
        if (name.size() != other.name.size()) return false;
        for (std::size_t i = 0; i < name.size(); ++i) {
            if (std::tolower(static_cast<unsigned char>(name[i])) !=
                std::tolower(static_cast<unsigned char>(other.name[i]))) {
                return false;
            }
        }
        return true;
    }
};
 
namespace std {
template <>
struct hash<City> {
    std::size_t operator()(const City& c) const noexcept {
        std::size_t h = 0;
        for (char ch : c.name) {
            h = h * 31 + static_cast<std::size_t>(std::tolower(static_cast<unsigned char>(ch)));
        }
        return h;
    }
};
}  // namespace std
 
int main() {
    std::unordered_set<City> seen;
    seen.insert(City{"Paris"});
    seen.insert(City{"paris"});
    seen.insert(City{"PARIS"});
    seen.insert(City{"Lyon"});
    std::cout << "size = " << seen.size() << "\n";
    std::cout << "has pArIs = " << seen.contains(City{"pArIs"}) << "\n";
    return 0;
}

Output:

size = 2
has pArIs = 1

The set holds two cities, Paris and Lyon. The three spellings of Paris were treated as one key, because the hash gave them the same number and the comparison said they were equal. The lookup with a new spelling, "pArIs", also found the entry.

Both functions do the same work on the letters. If you changed one to compare without case and left the other one using the raw letters, the program would still compile. The set would then behave in a way that depends on which bucket each spelling landed in. This is why the rule "same fields, same treatment" matters even when no field is missing.

Writing both functions by hand also means you own the rules. The default operator== compares every member as it is stored. A hand-written one can apply any rule you need, such as ignoring case, ignoring spaces or rounding a number. Whatever rule you choose, the hash must apply the same rule first.

Changing a key

Keys in a hash table should not change while they are stored. The table decided which bucket each key belongs in when the key was inserted. If you change the key so that its hash changes, the table still looks in the old bucket, and the key cannot be found.

C++ sets make this hard to do by accident. The elements of a std::unordered_set are const, so you cannot change them in place. To change a key, you take it out, change your copy, and put the copy back. The next program does that:

#include <cstddef>
#include <functional>
#include <iostream>
#include <string>
#include <unordered_set>
 
struct Tag {
    std::string name;
    bool operator==(const Tag&) const = default;
};
 
namespace std {
template <>
struct hash<Tag> {
    std::size_t operator()(const Tag& t) const noexcept {
        return std::hash<std::string>{}(t.name);
    }
};
}  // namespace std
 
int main() {
    std::unordered_set<Tag> tags;
    Tag a{"draft"};
    tags.insert(a);
    std::cout << "found before change = " << tags.contains(Tag{"draft"}) << "\n";
 
    // Copy the element out, change the copy, and insert it back.
    Tag copy = *tags.begin();
    tags.erase(tags.begin());
    copy.name = "final";
    tags.insert(copy);
    std::cout << "found draft = " << tags.contains(Tag{"draft"}) << "\n";
    std::cout << "found final = " << tags.contains(Tag{"final"}) << "\n";
    return 0;
}

Output:

found before change = 1
found draft = 0
found final = 1

The erase and insert steps leave the set in a correct state. The old key is gone, and the new key is in the bucket that matches its new hash. The mistake would be to find a way to change the key in place, bypassing the const. The table would then hold a key in a bucket that no longer matches its contents.

Common mistakes

Using a key type without a hash. If you put your class in an unordered container without writing std::hash for it, the compiler stops. This is the real first error from GCC 15 for a Point with an operator== but no hash, used in an std::unordered_set:

/usr/include/c++/15/bits/hashtable.h:210:51: error: static assertion failed: hash function must be copy constructible

The line names a static assertion. It says the hash for the key type is not usable. The rest of the messages are long, because the compiler reports the failure from inside the library. The fix is to add the std::hash specialization from step 2.

Writing a hash without an equality test. The hash alone is not enough. The table also needs operator== to confirm a match. If you write the hash but leave out operator==, the compiler reports an error when the table tries the comparison. This is the real first error from GCC 15 for a Point that has a hash specialization but no operator==, inserted into an std::unordered_set:

/usr/include/c++/15/bits/stl_function.h:378:20: error: no match for ‘operator==’ (operand types are ‘const Point’ and ‘const Point’)

The fix is to add the operator== from step 1.

Making the hash and the equality disagree. The compiler cannot check this rule for you. Suppose operator== compares only x, but the hash mixes both x and y. Then Point{1, 2} and Point{1, 3} count as equal, but they may get different hashes. Whether the table notices the duplicate depends on which bucket each one lands in. Sometimes the table holds two points that should be one key, and sometimes it holds one. The bug appears only on some runs, which makes it hard to find. Keep the two functions in step by listing the same fields in both.

Using a hash that depends on something that changes. A pointer address, a random number, or a field that the program updates after the insert are all bad choices. The hash must return the same number for the same key for as long as the key is in the table. Use only the values that define the key.

Forgetting that a copy is a different object. Two objects can be equal and still live at different addresses. A hash that uses the address of the object would give two equal keys different hashes. Always hash the values, not the address.

Practice

Exercise 1. Write a Cell struct with two int fields, row and col, and an operator== defaulted for it. Add a std::hash<Cell> specialization. Insert Cell{0, 0}, Cell{0, 1} and Cell{0, 0} into an std::unordered_set<Cell>, and print its size.

Show the answer

The size is 2. The third insert is equal to the first, so the set does not add it again. The two distinct cells are Cell{0, 0} and Cell{0, 1}.

Exercise 2. In the Employee example, what is the output of desks.size() after the line desks[Employee{"Priya", 2019}] = "desk 5"; is added at the end of the inserts?

Show the answer

It is still 3. The key Employee{"Priya", 2019} already exists, so the assignment changes its value from "desk 4" to "desk 5". No new entry is added.

Exercise 3. Your key is struct Order { int customerId; int orderNumber; };. Write the std::hash<Order> specialization. Use hashCombine from the Employee example. Explain in one sentence why the hash must use both fields if operator== compares both.

Show the answer

The hash body is std::size_t seed = 0; hashCombine(seed, o.customerId); hashCombine(seed, o.orderNumber); return seed;, placed inside namespace std. The hash must use both fields because two orders with the same customer but different order numbers are different keys, and a hash that ignored the order number would send all of a customer's orders to the same bucket.

Exercise 4. Look at this line: std::unordered_set<Tag> tags; tags.begin()->name = "x";. Why does the compiler refuse it?

Show the answer

The elements of an unordered set are const. The compiler refuses the assignment with this error from GCC 15:

error: no match for ‘operator=’ (operand types are ‘const std::string’ {aka ‘const std::__cxx11::basic_string<char>’} and ‘const char [2]’)

The refusal exists because changing the key in place could leave the element in the wrong bucket. The fix is to erase the element, change a copy, and insert the copy back, as the Tag example does.

Exercise 5. Remove operator== from the Point example in step 2, and compile the program. Write down the first line of the error message you see, and say which line of your program the error points to.

Show the answer

The first error line starts with a standard library file path, because that is where the comparison is made, and then reads error: no match for ‘operator==’ (operand types are ‘const Point’ and ‘const Point’). Below that, the compiler prints a trail of "required from here" lines that lead back to your own call, such as visited.insert(Point{1, 2});.

Summary

• A custom key needs an equality test (operator==) and a hash (a std::hash specialization).
• Equal keys must produce equal hashes. Use the same fields in both functions.
• Use = default for operator== in C++20 to compare every member. Write the hash by hashing each member and combining the results.
• Keep keys unchanged while they are in a table. C++ sets make elements const for this reason, so change a key by erasing it and inserting a copy.
• The Java names for the same ideas are equals and hashCode, and the rule between them is the same.