A function turns any key into an index. Jump straight to that bucket — no searching, no walking. Average-case O(1) for get, set, and delete.
A hash table stores key-value pairs in an array of buckets. When you set a key, a hash function crunches it into an integer, and integer % bucket_count gives the bucket index. Looking it up later runs the same function — one step, constant time. The wrinkle is collisions: two different keys can hash to the same bucket. The usual fix is chaining — each bucket holds a short list of everything that landed there. A good hash keeps chains short, preserving the O(1) average.
Each framed row is a bucket. The glowing arrow is the hash function pointing your key straight to its bucket. Drag to orbit, scroll to zoom.
All three core operations are O(1) average — the hash function routes you in one step.
Average vs worst case differ dramatically — a bad hash or an overfull table degrades everything.