How do you make a struct holding a user id and a device id usable as a std::unordered_map key in C++?
answer
- two things the container calls
- disabled std::hash specialization
- equal keys, equal hashes
- mix every compared field
- third template argument
basics
~20 sGive the struct equality, such as a defaulted operator== in C++20, and a hash: specialize std::hash for it or pass a hasher type as the third template argument. Keys that compare equal must hash equal, and the hash should mix every field.
solid answer
~40 s`std::unordered_map` calls two function objects: `Hash` (default `std::hash<Key>`) to pick a bucket and `KeyEqual` (default `std::equal_to<Key>`) to compare keys inside it. For a program-defined struct, `std::hash<SessionKey>` is disabled, so instantiation fails. Supply equality with `bool operator==(const SessionKey&) const = default;` (C++20) or a hand-written one, and supply a hash in one of two ways: an explicit specialization `template<> struct hash<SessionKey>` in namespace `std`, or a separate hasher struct passed as `std::unordered_map<SessionKey, Session, SessionKeyHash>`. The contract that matters: if `a == b`, then `hash(a) == hash(b)`; the reverse is not required, but collisions slow lookups. The standard library offers no hash-combine function, so combine field hashes with a mixing step, never a bare XOR, and mark the call operator `noexcept`.
code
cpp · 29 lines#include <cstdint>
#include <functional>
#include <iostream>
#include <string>
#include <unordered_map>
struct SessionKey {
std::uint64_t user_id;
std::uint32_t device_id;
bool operator==(const SessionKey&) const = default; // C++20
};
namespace std {
template <>
struct hash<SessionKey> {
size_t operator()(const SessionKey& k) const noexcept {
size_t h = hash<uint64_t>{}(k.user_id);
h ^= hash<uint32_t>{}(k.device_id) + 0x9e3779b97f4a7c15ULL + (h << 6) + (h >> 2);
return h;
}
};
} // namespace std
int main() {
std::unordered_map<SessionKey, std::string> sessions;
sessions[{42, 1}] = "phone";
sessions[{42, 2}] = "laptop";
std::cout << sessions.at({42, 2}) << ' ' << sessions.count({7, 1}) << '\n';
}go deeper
Know that a custom struct key needs both an equality operator and a hash before std::unordered_map accepts it.
Show both ways to supply the hash, a std::hash specialization or a hasher template argument, and state the equal-keys-equal-hashes rule.
Write a combine that mixes fields and survives patterned ids, keep hash and equality consistent, and explain why bare XOR degrades a real cache.
Decide whether the codebase provides one vetted hash-combine utility for key types, so teams stop writing ad hoc XOR hashes.
## Why the default fails An unordered container is parameterized as `std::unordered_map<Key, T, Hash = std::hash<Key>, KeyEqual = std::equal_to<Key>>`. On every lookup it calls `Hash` once to choose a bucket and `KeyEqual` on each element in that bucket. For a session cache keyed by ```cpp struct SessionKey { std::uint64_t user_id; std::uint32_t device_id; }; ``` neither default works. The standard says that for any type for which neither the library nor the user provides a specialization, `std::hash<Key>` is **disabled**: it is not default-constructible and not callable. Apple clang 21 reports the first error as `call to implicitly-deleted default constructor of 'std::hash<SessionKey>'`, followed by libc++'s own `static assertion failed due to requirement 'integral_constant<bool, false>::value': the specified hash does not meet the Hash requirements`. Without `operator==`, `std::equal_to<SessionKey>` fails as well. ## Supplying equality - **C++20**: `bool operator==(const SessionKey&) const = default;` compares every member in declaration order. - **Earlier standards**: write `operator==` by hand, or compare `std::tie(a.user_id, a.device_id) == std::tie(b.user_id, b.device_id)`. - **A different notion of equality**, such as case-insensitive names, goes into a `KeyEqual` type passed as the fourth template argument, and then the hash must follow the same notion. ## Supplying the hash | Approach | How | When it fits | |---|---|---| | Specialize `std::hash` | `namespace std { template<> struct hash<SessionKey> { size_t operator()(const SessionKey&) const noexcept; }; }` | the struct has one natural hash, wanted everywhere, including `std::unordered_set<SessionKey>` without extra arguments | | Hasher type | `struct SessionKeyHash { size_t operator()(const SessionKey&) const noexcept; };` then `std::unordered_map<SessionKey, Session, SessionKeyHash>` | several hashes for one type, or a type you do not own | Adding a specialization of a standard class template to namespace `std` is permitted when it depends on a program-defined type and meets the template's requirements, which is exactly this case. ## The contract The standard's rules, in order of importance: 1. **Equal keys must hash equal.** If `KeyEqual` says two keys are equivalent, the hash must return the same value for both. Breaking this makes `find` look in the wrong bucket and miss elements that are present, a silent bug. 2. **The result may depend only on the argument** for the duration of the program, so no hashing of the key object's own address or of mutable global state. 3. **Collisions should be rare**: the requirement says the probability that two different values hash equal *should* be very small. That is a quality goal, not a correctness rule, but violating it turns average O(1) into O(n). 4. A program-defined `std::hash` specialization *may* throw, but mark it `noexcept` anyway: libstdc++, for example, decides whether to cache each node's hash code partly on whether the hasher is nothrow invocable. ## Combining fields There is no `std::hash_combine`. A common pattern hashes each field with `std::hash` and folds them with a mixing step, as the code example does: `h ^= next + 0x9e3779b97f4a7c15 + (h << 6) + (h >> 2);`. The shifts and the odd constant make the result depend on field order and spread bits, so `(1, 2)` and `(2, 1)` hash differently. What not to do: - **Bare XOR**, `user_id ^ device_id`: symmetric, and every key whose two fields are equal hashes to 0. - **Hashing only some fields**: legal, because equal keys still hash equal, but every device of one user collides. - **Hashing fields that `operator==` ignores**: two equal keys can then hash differently, which breaks rule 1. Remember too that `std::hash` for integers is the identity function in both libc++ and libstdc++, so structured ids are not scrambled for you; the mixing step is what spreads them. ## Placing and testing it - Declare the `std::hash` specialization **in the same header as the struct**, right after it. A specialization must be declared before the first use that would instantiate `std::hash<SessionKey>`; a translation unit that instantiates `std::unordered_map<SessionKey, ...>` before the specialization is declared is ill-formed, and no diagnostic is required. - Unit-test the contract directly: for pairs of keys that `operator==` treats as equal, assert equal hashes; for keys that differ in one field, check that the hashes usually differ. - Check the distribution on real data once: fill a container with production-like ids and look at the largest `bucket_size`; a good hash keeps it to a handful of elements at the default load factor.
- What breaks if the hash reads a field that operator== ignores, such as a last-seen timestamp?Two keys that `operator==` treats as equal can then land in different buckets. `find` hashes the probe, searches only that bucket and misses the stored element, and inserting the same logical key twice creates a duplicate. The hash must use only data that equality compares, or a function of it.
- How do you look up a std::unordered_map<std::string, Session> with a std::string_view without building a std::string?Since C++20 the lookup members have heterogeneous overloads that participate only when both `Hash::is_transparent` and `KeyEqual::is_transparent` are valid. Use a hasher that declares `using is_transparent = void;` and hashes `std::string_view`, plus `std::equal_to<>`. The standard guarantees `std::hash<std::string>` and `std::hash<std::string_view>` agree on the same characters.
- XOR of the field hashes is a good enough combine
- std::hash works for any struct whose members are hashable
- Two different keys must never produce the same hash
- Adding a std::hash specialization to namespace std is always forbidden
- The hash can include fields that operator== ignores