Hash tables convert keys into array indices using hash functions, offering O(1) expected time key-value lookups. Master std::unordered_map, custom hash functions for pair keys, collision handling, and frequency set indexing in C++.
O(1) Average Lookup: Directly computes bucket index from key hash value.
Collision Resolution: Uses chaining (linked lists/vectors) or open addressing (linear probing).
Custom Pair Hashes: Requires explicit hash functor when using std::pair or custom structs in std::unordered_map.
Set Invariant: std::unordered_set guarantees O(1) element uniqueness verification.