How does a hash table work?

The engine of a hash table is the hash function. Its job is to take an input of any size (like a person's name or a string of text) and return a fixed-size integer. This integer is then used as an index in an underlying array. For example, if you input the word 'Apple', the hash function might crunch the letters and spit out the number 4. A crucial rule is that the same input must always produce the same output. If 'Apple' gives you 4 today, it must give you 4 tomorrow, otherwise you would never find your data again.

Behind the scenes, a hash table is basically just an array. Each slot in this array is often called a 'bucket'. When you want to store a key-value pair, the hash table calculates the hash of the key, uses the modulo operator ($ext{hash} \pmod{ ext{array size}}$) to make sure the number fits within the array's bounds, and places the data in that bucket. Because arrays allow for immediate access if you know the index, finding data in a hash table takes $O(1)$ time on average. You just compute the hash and look in that exact bucket.

A common place students slip up is forgetting about collisions. Because the array has a fixed size and the number of possible keys is infinite, two different keys will eventually produce the same index. This is called a collision. There are two main ways to handle this. The first is 'Chaining', where each bucket holds a linked list of entries; if two items go to the same bucket, they just join the list. The second is 'Open Addressing', where the hash table looks for the next available empty bucket to store the colliding item.