A lesson from the data structures and algorithms bootcamp. About a 11 minute read.
A hash map stores keys and values with near-instant lookup, and a set is the same machine answering only 'have I seen this'. It is the single most effective way to delete a nested loop, and the word 'average' in its complexity is doing more work than people realise.
A hash function turns a key into a number, that number picks a slot in an array, and the pair goes there. Lookup repeats the calculation and goes straight to the slot. That is the whole idea, and notice what it rests on: the array indexing from the first lesson. A hash map is an array you can index by anything.
The rest of this lesson continues with 4 further sections. See the full curriculum.
Browse all 536 practice puzzles