A hash map lets a program look up a value by a meaningful key rather than searching through every item. Store a student's score under a student ID, for example, and retrieve it later using that ID.
From key to bucket
A hash function converts a key into a number. The map uses that number to choose a bucket in its internal storage. A well-designed hash function spreads common keys across buckets, so lookup, insertion, and deletion are expected to take O(1) time.
What if two keys collide?
Different keys can lead to the same bucket; this is called a collision. Implementations commonly keep a small collection of entries in each bucket or search for another open position. If too many entries crowd the table, performance can degrade, so maps resize when their load factor gets too high.
The expected constant-time claim depends on a good distribution and a controlled load factor. In the worst case, many keys can land together and lookup can approach O(n).
When a hash map helps
- Count frequencies, such as how often each word appears.
- Match records by ID without repeatedly scanning a list.
- Remember values already computed by a recursive algorithm.
Keys should have stable equality and hashing behavior while they are stored. If two keys compare equal, they must produce compatible hash values; otherwise, the map may not find an entry where expected.