Hashmaps in C++ provide a fast, flexible way to store and retrieve key-value pairs with average constant-time complexity. They are part of the Standard Template Library as unordered_map, unordered_multimap, and related containers designed for efficient lookup.
Engineers use hashmaps when they need quick access by unique keys, such as caching results, counting frequencies, or building associative arrays. Understanding their behavior helps you choose the right tool for performance-critical components.
| Container | Ordering | Lookup Complexity | Use Case |
|---|---|---|---|
| map | Sorted by key | O(log n) | Ordered traversal, range queries |
| unordered_map | No guaranteed order | Average O(1), worst O(n) | Fast lookup, unique keys |
| unordered_multimap | No guaranteed order | Average O(1), worst O(n) | Multiple values per key |
| map (large entries) | Sorted by key | O(log n) | Stable performance, ordered API |
Hashing Mechanics and Bucket Management
Hash Function and Collisions
The core of hashmaps in C++ is the hash function, which transforms a key into a bucket index. Good hash functions distribute keys evenly to minimize collisions, where different keys map to the same bucket. The standard library provides defaults for common types and allows custom hash objects for user-defined types.
Rehashing and Load Factor
As elements are added, the load factor, calculated as size divided by bucket count, increases. When it crosses a threshold, the container performs rehashing, allocating more buckets and redistributing elements. This process is expensive but keeps average lookup times near constant.
Performance Characteristics and Complexity
Average vs Worst Case
In practice, unordered_map offers average O(1) complexity for insert, erase, and find operations. However, poor hash functions or adversarial inputs can lead to O(n) behavior in a single bucket, turning effective performance linear.
Iterator Invalidation Rules
Insertions may cause rehashing, which invalidates all iterators, pointers, and references. On rehash-free insertions, only iterators to the erased element are invalidated, making careful planning essential for performance-sensitive loops.
Memory Layout and Customization
Bucket Array and Node Storage
Hashmaps store elements in nodes allocated separately from the bucket array. Each bucket holds a pointer to a linked list or similar structure of nodes, trading some memory overhead for flexible growth and fast insertions.
Allocators and Hash Policy
You can supply custom allocators to control memory management and define your own hash, key equality, and rehashing policy. This enables specialized memory pools, predictable latency patterns, and integration with custom object lifetimes.
Practical Usage Patterns
Common patterns include using emplace to construct objects directly in place, reserving adequate bucket count upfront to avoid repeated rehashing, and choosing the right key type to balance distribution and copy cost.
When ordering is not required, unordered_map often outperforms map in lookup-heavy workloads. For small sizes or frequent full-container scans, however, vector-based maps or flat_hash_map variants may be more cache-friendly.
Best Practices and Tuning
- Reserve enough buckets upfront to avoid rehashing during critical phases.
- Select or design hash functions that spread keys uniformly across buckets.
- Measure load factor and profile performance to balance memory usage and speed.
- Use emplace variants to construct objects in place and reduce copies.
- Prefer unordered_map for large, lookup-heavy workloads when order is irrelevant.
FAQ
Reader questions
How can I avoid frequent rehashing in my hashmap?
Call reserve with an estimate of the final number of elements before inserting many items so bucket count is set once and rehashing is minimized.
What should I do if my custom key has poor hash distribution?
Provide a custom hash function that mixes key bits thoroughly and test the distribution with representative data to lower collision rates.
When should I prefer map over unordered_map?
Choose map when you need ordered iteration, predictable O(log n) worst-case behavior, or operations like lower_bound that rely on order.
Are pointers and references stable after insertion in a hashmap?
References and pointers to elements remain valid until that specific element is erased; iterators are invalidated only on rehash, not on every insertion.