Hash tables

A hash table is a way to store key–value pairs so you can find any key almost instantly, without searching. It runs the key through a hash function, which turns it into a number, and uses that number to pick a slot in an array. Two keys sometimes land in the same slot, so the table either keeps a short list per slot or probes for the next free one. As long as keys spread out evenly and the table grows before it gets too full, lookups, inserts and deletes take constant time on average. Dictionaries, sets, caches and database joins are all built on this idea.