Hash maps and sets

A hash map stores pairs of keys and values, like a dictionary that links each word to its meaning. A hash function turns each key into a position in an array, so looking up, adding and deleting take O(1) on average. A hash set is the same idea with keys only.

Sometimes two keys land in the same position. This is a collision, and the map handles it by keeping a small list there (chaining) or trying another free slot (probing). The table also grows as it fills, so the average stays constant.

This is the most useful structure in the roadmap. When a problem asks "have I seen this before?", "how many times?" or "where is its partner?", a hash map usually turns an O(n²) search into O(n). To use a pair of values as the key, build a composite key: a tuple or a combined string.