Hash Maps

A hash map stores key → value pairs and answers "is this key here?" in constant time on average. A hash set is the same table without values.

	C++	Python	Java
Hash map	unordered_map	dict	HashMap
Hash set	unordered_set	set	HashSet
Sorted map	map	none built in	TreeMap

A hash map keeps its keys in no particular order. If you need the keys sorted, use a sorted map instead. It is a balanced tree, so every operation costs $O(\log n)$, but it can hand you the smallest key, the largest, or the nearest key above or below a value, which a hash map cannot.

Operation	Hash map	Sorted map
Insert, lookup, erase	$O(1)$ average	$O(\log n)$
Smallest, largest, or nearest key	not supported	$O(\log n)$
Iterate all entries	$O(n)$, any order	$O(n)$, sorted

Use a hash map whenever a problem asks whether you have seen something before, how many of each thing there are, or which element pairs with the current one. In most solutions the map replaces the inner loop of a nested scan, turning $O(n^2)$ into $O(n)$. Reach for the sorted map only when the order of the keys matters.

The problems below start with membership and pairing, move through counting and grouping, and end with keys you have to design yourself.