CONCEPT · Pupil
Hashing
also hash map · unordered_map · dictionary
Expected O(1) lookup by value. The usual replacement for an enormous array when keys are up to 1e9, and the usual Two Sum companion.
Intuition
Pay a hash to ask 'have I seen x?' instead of scanning.
When to reach for it
- Two Sum / complement search
- Frequency of large values
- Coordinate compression as a first step
Usual pits
- Worst-case hash collisions in contests — sometimes ordered maps or custom hashes
- Using a map when values are small enough for an array