Why this matters
A map finds a value by its key. The key is whatever you search with: a word, a student ID, or a grid cell written as row 3 and column 5. The built-in types int and std::string work as keys with no extra work. Your own types do not. A struct that holds a row and a column can be stored in a std::map only after you say how to compare two of them. It can be stored in a hash map only after you say two more things: when two keys are the same, and which number stands for a key.
If you skip those steps, the code may not compile. If you get them slightly wrong, it compiles and runs, and the map quietly loses items. A key you inserted can be missing on the next lookup, or the same logical key can appear twice. This lesson shows the rules, shows what goes wrong when they are broken, and then gives the C++ way to hash a pair of numbers, which is the most common custom key in grid and graph problems.
Java uses the names equals and hashCode for the same two rules. This lesson uses the C++ names, which are operator== and a hash function object.
The idea: a hash table needs two answers
A hash map that is written with std::unordered_map or a hash set written with std::unordered_set stores its items in buckets. A bucket is one slot in an internal array. A hash is a whole number that the table computes from a key. A hash function is the piece of code that does that computation. The same key always has to give the same hash, or the table would look in the wrong bucket.
Here is how the table uses the two answers:
- To store a key, it computes the hash, takes that number modulo the bucket count (the remainder after dividing by it) to pick a bucket, and puts the key in there.
- To find a key, it computes the same hash, goes to the same bucket, and compares the key it is looking for with each key already in the bucket using
==.
Picture a table with 8 buckets and a key whose hash is 27. The bucket index is 27 modulo 8, which is 3. The table looks in bucket 3 only. If that bucket holds keys A and B, the table compares the search key with A and then with B. It does not look anywhere else.
From this picture come the two rules your type must follow.
- If two keys are equal according to
==, their hashes must be equal too. If the hashes differ, the table looks in a different bucket and never finds the equal key. - The hash must give the same number every time for the same key while the key is in the table. A hash that changes over time loses the key.
The rules do not say that different keys need different hashes. Two unequal keys can share a hash. That is called a collision, and the table handles it by comparing keys inside the bucket. Collisions cost time, but they do not cause wrong answers. Unequal keys that compare equal, or equal keys that hash differently, do cause wrong answers.
Maps that use < do not need a hash
A std::map does not use a hash. It keeps its keys in sorted order, so it needs a rule that says whether one key comes before another. That rule is operator<. The standard library already defines operator< for std::pair, comparing the first items and then the second. So this code works with no extra work:
#include <iostream>
#include <map>
#include <utility>
int main() {
std::map<std::pair<int, int>, char> grid{
{{0, 0}, 'S'},
{{2, 1}, 'E'},
{{0, 1}, '.'},
};
grid[{1, 1}] = '#';
for (const auto& [cell, symbol] : grid) {
std::cout << "(" << cell.first << "," << cell.second << ") " << symbol << "\n";
}
}The output is:
(0,0) S
(0,1) .
(1,1) #
(2,1) EThe cells come out in sorted order, by row first and then by column. This is useful when you want sorted output. For a lookup-heavy program, a hash map is usually faster, and then you need the rest of this lesson.
Step 1: a struct with equality
Suppose a maze solver stores a visited cell as a struct instead of a pair. A struct gives the fields names, which makes the code easier to read.
struct Point {
int x;
int y;
bool operator==(const Point&) const = default;
};The line bool operator==(const Point&) const = default; asks the compiler to write == for you. Two points are equal when their x values are equal and their y values are equal. This line is the C++20 way to write the first of the two answers. Without it, == does not exist for Point, and the comparison is a compile error.
A set of visited points needs one more thing, a hash. Trying to use the struct without a hash gives a long compile error. The Common mistakes section below shows the error for a missing hash.
Step 2: a hash for the struct
The C++ counterpart of Java's hashCode is a specialization of std::hash for your type. A specialization is a version of a template (code with a type left blank for the compiler to fill in) that you write for one specific type. std::hash is a template that the standard library provides. It has versions for int, std::string and other standard types. You add one for Point.
#include <cstddef>
#include <functional>
#include <iostream>
#include <unordered_set>
struct Point {
int x;
int y;
bool operator==(const Point&) const = default;
};
template <>
struct std::hash<Point> {
std::size_t operator()(const Point& p) const noexcept {
std::size_t h = std::hash<int>{}(p.x);
h = h * 0x9e3779b97f4a7c15ULL + std::hash<int>{}(p.y);
return h;
}
};
int main() {
std::unordered_set<Point> visited;
visited.insert({1, 2});
visited.insert({1, 2});
visited.insert({3, 4});
std::cout << "visited size: " << visited.size() << "\n";
std::cout << "contains (1,2): " << visited.contains({1, 2}) << "\n";
std::cout << "contains (9,9): " << visited.contains({9, 9}) << "\n";
}The output is:
visited size: 2
contains (1,2): 1
contains (9,9): 0The second insert of {1, 2} does nothing, because the set already has an equal point. The size is 2, not 3. contains returns true or false, and the program prints them as 1 and 0.
Here is what the hash function does. It turns x into a number with std::hash<int>, then multiplies that number by a large odd constant and adds the hash of y. The constant 0x9e3779b97f4a7c15 is an arbitrary large number with a mix of bits set. The multiplication spreads the bits of x across the whole result, so that nearby points get very different hashes. The exact constant is less important than the fact that it is large, odd, and used the same way every time.
The function is marked noexcept because it does not throw. The standard library can use this promise to make some operations faster. You do not have to mark it, but it is a good habit for hash functions.
The hash uses both x and y. It has to. If the hash used only x, every point in the same column would share a bucket. Those points would still be correct, but each lookup would compare against many keys in that bucket, which is slow.
Step 3: a pair hash for std::pair
Grid problems often use std::pair<int, int> as the key, because a pair is a built-in way to hold a row and a column. The standard library does not provide std::hash for std::pair. You have to write it. The usual way is a small struct with an operator() function. The struct is a function object, so the hash table can call it like a function.
Here is a naive first try. It combines the two hashes with ^, which is the exclusive or operator. Exclusive or gives 1 for each bit where the two inputs differ and 0 where they match.
#include <cstddef>
#include <functional>
#include <iostream>
#include <unordered_set>
#include <utility>
struct XorPairHash {
std::size_t operator()(const std::pair<int, int>& p) const {
return std::hash<int>{}(p.first) ^ std::hash<int>{}(p.second);
}
};
template <typename Hash>
std::size_t distinct_hashes(int n) {
std::unordered_set<std::size_t> seen;
Hash hash;
for (int r = 0; r < n; ++r) {
for (int c = 0; c < n; ++c) {
seen.insert(hash({r, c}));
}
}
return seen.size();
}
int main() {
std::cout << "pairs: " << 1000 * 1000 << "\n";
std::cout << "distinct hashes with XOR: " << distinct_hashes<XorPairHash>(1000) << "\n";
std::cout << "XOR hash of (5,5): " << XorPairHash{}({5, 5}) << "\n";
std::cout << "XOR hash of (0,0): " << XorPairHash{}({0, 0}) << "\n";
}The output is:
pairs: 1000000
distinct hashes with XOR: 1024
XOR hash of (5,5): 0
XOR hash of (0,0): 0There are a million cells in a 1000 by 1000 grid. The XOR hash gives only 1024 different values for them, so about a thousand cells share each value on average. The reason is that ^ of two equal numbers is always 0. So every cell on the diagonal, such as (5,5), hashes to the same value as (0,0). Also, the result of ^ never has a bit set above the highest bit of either input. Two inputs below 1024 can only produce results below 1024.
The fix is to multiply the first number before adding the second. The multiplication moves the bits of the row into high positions, so the row and the column no longer cancel each other out. Here is the version with that fix, plus a count of the distinct values for the same grid.
#include <cstddef>
#include <functional>
#include <iostream>
#include <unordered_set>
#include <utility>
struct PairHash {
std::size_t operator()(const std::pair<int, int>& p) const {
return std::hash<int>{}(p.first) * 0x9e3779b97f4a7c15ULL + std::hash<int>{}(p.second);
}
};
template <typename Hash>
std::size_t distinct_hashes(int n) {
std::unordered_set<std::size_t> seen;
Hash hash;
for (int r = 0; r < n; ++r) {
for (int c = 0; c < n; ++c) {
seen.insert(hash({r, c}));
}
}
return seen.size();
}
int main() {
std::cout << "distinct hashes with multiply-add: " << distinct_hashes<PairHash>(1000) << "\n";
std::cout << "hash of (0,1): " << PairHash{}({0, 1}) << "\n";
std::cout << "hash of (1,0): " << PairHash{}({1, 0}) << "\n";
}The output is:
distinct hashes with multiply-add: 1000000
hash of (0,1): 1
hash of (1,0): 11400714819323198485All one million cells now get a different hash value. The hash of (0,1) and the hash of (1,0) are different, which the XOR version could not say. The cells now spread across the buckets evenly, so each bucket holds few keys and lookups compare only a few of them.
You can use the pair hash like this:
std::unordered_map<std::pair<int, int>, int, PairHash> distance;
distance[{2, 3}] = 7;The third template argument of std::unordered_map is the hash type. The table creates one PairHash object and calls it for every key. The equality test is the default, std::equal_to<std::pair<int, int>>, which uses == on pairs. Pairs already have == built in, so only the hash needs to be written.
Step 4: a key that goes wrong
The rule that equal keys must hash equal is easy to break when == and the hash look at different fields. Here is a user record where the equality test checks only the id, but the hash function also uses the name.
#include <cstddef>
#include <functional>
#include <iostream>
#include <string>
#include <unordered_map>
struct User {
int id;
std::string name;
bool operator==(const User& other) const { return id == other.id; }
};
struct BrokenUserHash {
std::size_t operator()(const User& u) const {
return std::hash<int>{}(u.id) ^ (std::hash<std::string>{}(u.name) << 1);
}
};
int main() {
std::unordered_map<User, int, BrokenUserHash> scores;
scores[User{7, "ann"}] = 10;
User same_id{7, "anna"};
std::cout << "equal users: " << (User{7, "ann"} == same_id) << "\n";
std::cout << "hash ann: " << BrokenUserHash{}(User{7, "ann"}) << "\n";
std::cout << "hash anna: " << BrokenUserHash{}(same_id) << "\n";
std::cout << "found with broken hash: " << scores.contains(same_id) << "\n";
}The output on g++ 15.2 with its standard library is below. The hash numbers depend on the standard library and will differ on other systems.
equal users: 1
hash ann: 6950199530278763107
hash anna: 13177252595631385921
found with broken hash: 0The program says the two users are equal, because == returns 1. But the two users have different hashes, so the table usually looks for anna in a different bucket from the one where ann was stored. The lookup returns 0, which means not found, even though the table has an equal key. The C++ compiler does not check this rule for you. The program compiles and runs without any warning.
The fix is to make the hash use exactly the fields that == uses. Here the hash should use id only.
struct FixedUserHash {
std::size_t operator()(const User& u) const {
return std::hash<int>{}(u.id);
}
};If you want a user's name to count as part of the key, put it in == too. Then the two users are different keys, and the table is correct to treat them as different.
Step 5: a key that changes after insertion
A key must not change while it is inside a map or a set. The table places the key in a bucket using its hash at the time of insertion. If you later change a field that the hash uses, the key sits in the wrong bucket. A lookup for the new value goes to a bucket that does not hold it, and a lookup for the old value goes to a bucket that holds an item with the new value. Both fail.
The standard library protects you from one form of this. The key in a std::unordered_set is const, so you cannot assign to it directly. You can still get around that with a pointer or with const_cast, and then the table has no way to detect the mistake. The safe approach is to treat keys as read-only. To change a key, erase the old entry and insert the new one.
#include <cstddef>
#include <functional>
#include <iostream>
#include <unordered_map>
#include <utility>
struct Point {
int x;
int y;
bool operator==(const Point&) const = default;
};
template <>
struct std::hash<Point> {
std::size_t operator()(const Point& p) const noexcept {
std::size_t h = std::hash<int>{}(p.x);
h = h * 0x9e3779b97f4a7c15ULL + std::hash<int>{}(p.y);
return h;
}
};
int main() {
std::unordered_map<Point, int> cost;
cost[{1, 2}] = 5;
auto node = cost.extract(Point{1, 2});
node.key() = Point{3, 4};
cost.insert(std::move(node));
std::cout << cost.size() << " " << cost.contains({3, 4}) << " " << cost.contains({1, 2}) << " " << cost.at({3, 4}) << "\n";
}The output is:
1 1 0 5The extract function removes an entry from the map without destroying it. The key() function on the removed node gives you a way to change its key before you put the node back with insert. Here the key moves from (1,2) to (3,4), and the value 5 moves with it. This is the one safe way to change a key in place. The new key must not already be in the map, because insert then returns without adding the node.
Common mistakes
The hash type is missing
If you use a key type that has no hash, the compiler reports an error from inside the standard library. The error is long. The first lines are the important ones. Here is a program that uses a pair as the key of an unordered map with no hash.
#include <iostream>
#include <unordered_map>
#include <utility>
int main() {
std::unordered_map<std::pair<int, int>, int> cell_cost;
cell_cost[{0, 1}] = 5;
std::cout << cell_cost[{0, 1}] << "\n";
}Compiling it with g++ -std=c++20 -Wall gives these first error lines, shortened here:
hashtable.h:210:51: error: static assertion failed: hash function must be copy constructible
l11_missing_hash.cpp:6:50: error: use of deleted function 'std::unordered_map<...>::unordered_map()'The phrase to look for is static assertion failed. It says that the hash type is not usable. The fix is to pass a hash type as the third template argument, as in std::unordered_map<std::pair<int, int>, int, PairHash>.
The equality test is missing
If the struct has no ==, the hash table cannot compare two keys in the same bucket. This program gives a Cell a hash but no operator==:
#include <cstddef>
#include <functional>
#include <iostream>
#include <unordered_set>
struct Cell {
int row;
int col;
};
template <>
struct std::hash<Cell> {
std::size_t operator()(const Cell& c) const noexcept {
return std::hash<int>{}(c.row) * 31 + std::hash<int>{}(c.col);
}
};
int main() {
std::unordered_set<Cell> seen;
seen.insert(Cell{1, 1});
std::cout << seen.size() << "\n";
}Compiling it with g++ -std=c++20 -Wall gives this error (the path depends on your install):
/usr/include/c++/15/bits/stl_function.h:378:20: error: no match for 'operator==' (operand types are 'const Cell' and 'const Cell')The message names the missing operator and the type, which tells you where to look. Add bool operator==(const Cell&) const = default; to the struct.
Equal keys that hash differently
The example in Step 4 shows the failure. The symptom is a lookup that returns not found for a key you inserted, or a set that holds two items that should be one. Check that every field used in == is used in the hash, and that no field outside == is used in the hash. If the hash uses a pointer address, check that it does not point to a temporary object.
A hash that gives different values for the same key
A hash that calls a random number generator, reads the clock, or reads a value that changes will give different results on each call. The table then cannot find a key after it was stored. Keep the hash a pure function of the key's fields.
The XOR combine for pairs
The XOR pair hash in Step 3 compiles and gives correct answers, because equal pairs still hash equal. The problem is speed. With 1024 distinct values for a million cells, each bucket holds about a thousand keys, and every lookup compares many keys one by one. The program still prints the right answers, but each lookup compares more keys than it needs to. Use the multiply-add version for grid keys.
Storing a pointer as the key
A key of type Point* hashes the address, not the coordinates. Two different pointers to two equal points are different keys, and that is almost never what you want. Store the value, not the pointer, as the key.
Practice
Exercise 1
Write a struct Cell with two int fields, row and col. Give it an operator==. Then write a std::hash<Cell> specialization. Use an std::unordered_set<Cell> to count the distinct cells in this list: {0,0}, {0,1}, {0,0}, {2,2}. The count should be 3.
Show the answer
#include <cstddef>
#include <functional>
#include <iostream>
#include <unordered_set>
struct Cell {
int row;
int col;
bool operator==(const Cell&) const = default;
};
template <>
struct std::hash<Cell> {
std::size_t operator()(const Cell& c) const noexcept {
std::size_t h = std::hash<int>{}(c.row);
return h * 0x9e3779b97f4a7c15ULL + std::hash<int>{}(c.col);
}
};
int main() {
std::unordered_set<Cell> seen{{0, 0}, {0, 1}, {0, 0}, {2, 2}};
std::cout << seen.size() << "\n";
}The program prints 3. The set is built from a list with four entries. The second {0, 0} is equal to the first, so the set keeps only one of them.
Exercise 2
With the XOR pair hash from Step 3, what is the hash of (7, 7)? Explain why without running the code.
Show the answer
The hash is 0. The hash of a pair is the XOR of its two parts, and XOR of two equal numbers is always 0. So std::hash<int>{}(7) ^ std::hash<int>{}(7) is 0. The same is true for any pair with equal parts, including (0,0).
Exercise 3
The BrokenUserHash in Step 4 uses the name. Change the program so that scores.contains(same_id) returns 1. Do not change operator==.
Show the answer
Change the hash type of scores to FixedUserHash, which uses only the id, as in the code below. Then ann and anna have the same hash, and the table finds the equal key in the same bucket. The last line of the program then shows 1 after its label. The hash must use the same fields as ==, and == here uses only id.
struct FixedUserHash {
std::size_t operator()(const User& u) const {
return std::hash<int>{}(u.id);
}
};Exercise 4
Write a key type Triple with fields x, y, and z. Write its hash by starting from the hash of x, multiplying by 0x9e3779b97f4a7c15ULL, adding the hash of y, then multiplying again and adding the hash of z. Test that {1,2,3} and {3,2,1} have different hashes.
Show the answer
#include <cstddef>
#include <functional>
#include <iostream>
struct Triple {
int x;
int y;
int z;
bool operator==(const Triple&) const = default;
};
template <>
struct std::hash<Triple> {
std::size_t operator()(const Triple& t) const noexcept {
std::size_t h = std::hash<int>{}(t.x);
h = h * 0x9e3779b97f4a7c15ULL + std::hash<int>{}(t.y);
h = h * 0x9e3779b97f4a7c15ULL + std::hash<int>{}(t.z);
return h;
}
};
int main() {
std::size_t a = std::hash<Triple>{}({1, 2, 3});
std::size_t b = std::hash<Triple>{}({3, 2, 1});
std::cout << a << "\n" << b << "\n" << (a != b) << "\n";
}Printing the two hashes and the result of comparing them gives:
1995974887614534118
15725297606679463254
1The last line is 1, which means true: the two hashes differ. The multiplication makes the position of each field matter, so {1,2,3} and {3,2,1} get different values.
Exercise 5
Why does a std::map<std::pair<int, int>, int> need no hash function, while an std::unordered_map with the same key does?
Show the answer
A std::map keeps its keys in sorted order. It only needs a way to say whether one key comes before another, and operator< already exists for std::pair. An std::unordered_map finds keys by computing a hash and looking in one bucket. It needs a hash function for the key type, and the standard library has none for std::pair, so you must write one.
Summary
- A hash map or hash set needs two answers from a key type: an
==test and a hash. - Equal keys must give equal hashes. If they do not, lookups miss keys that are in the table.
- A
std::mapneedsoperator<instead of a hash.std::pairalready hasoperator<. - The C++ counterpart of Java's
hashCodeandequalsisstd::hash<T>specialized for your type, together withoperator==. - Combine field hashes with a multiply and an add. XOR of two equal fields always gives 0, which makes many keys collide.
- Never change a key while it is in a container. Use
extractto change a key safely.