Hash maps and sets

A hash map stores key and value pairs. It runs each key through a hash function, which turns the key into an array index. So lookup, insert and delete take O(1) on average.

Sometimes two keys land in the same slot, which is called a collision. The map keeps both, using chaining or probing, and it grows its array as it fills so lookups stay fast. A set is the same idea with keys only.

This is the structure that most often turns a slow solution into a fast one. Checking "have I seen this?" in a list is O(n); in a set it is O(1). Keys must be hashable (the language must be able to hash them), and should never change after they are inserted.