An unordered associative container stores key–value elements in a hash table rather than arranging them in a sequence-based order. Hashing selects a bucket for lookup, making searches average constant time when collisions are limited. section 8.2 section 8.2.1
Keep these behaviors in mind:
- A hash function maps each key to a bucket; collisions place multiple elements in one bucket. section 8.2.1
- A good hash usually gives average O(1) lookup, while the worst case can reach O(n) if elements share a bucket. section 8.2.1
- std::unordered_map uses std::hash and std::equal_to by default, with custom hashing available for user-defined keys. section 8.4 section 8.2.1
Matching pennies state table
A matching-pennies program models each state as a tuple containing the previous outcome, the current choice, and the latest outcome. An std::unordered_map maps that tuple to the player's last two choices. Because the tuple is not a standard key with a built-in hash, specializing std::hash<state_t> combines hashes for its three fields. A property check then inspects every bucket and asserts that each contains at most one element. section 8.2 section 8.2.1
Figure 8.1 Two hash tables, one without a collision and the second with a collision, meaning a bucket contains more than one element
Compare a hash table without collisions to one whose bucket contains multiple elements. section 8.2.1
