How does hashing work

The label decides the slot number

In the last lesson, finding a value in a row meant scanning one by one or using a sorted index. But what if you could decide the slot number from the value itself, the way you might pick a slot from the letters of a name?
You set up one small calculation that turns a value into a slot number. That calculation is called a hash function. The dictionary from the first lesson, if you look inside, works this way too.

Tap a value. The calculation decides its slot number, and the value drops right into that slot.

Every value got its slot at once. There is no need to think about where to put it, because the calculation tells you the place.
Put in the same value again and the calculation always gives the same slot, so the places do not jump around. Then couldn't we use the same calculation when searching too?

Calculate, then go straight to the slot

Searching works the same way. Put the value you are looking for through the same calculation to get its slot number, then go straight to that slot. There is no need to scan the slots one by one.
Because the calculation used when putting in and the one used when searching are the same, the slot you stored it in and the slot you look in match exactly. So you get there in one go.

Tap a value to find. The same calculation gives the slot number, and you jump straight to that slot without scanning.

You arrived straight away without scanning. Whether there are a hundred slots or ten thousand, the effort is about the same, because it takes one calculation and one jump.
That is why hashing is fast. Where a sorted index needed about twenty looks, hashing usually finishes in one. But there is one catch. What happens if two different values give the same result?

Two values head for the same slot

The calculation always gives the same slot for the same value, but different values do not always get different slots. The number of slots is fixed, while there can be far more values.
So two different values sometimes end up with the same slot by chance, both trying to fit into one slot. Two values bumping into each other over the same slot like this is called a collision.

Tap the two values in turn. Their results are the same, so both go to the same slot and collide.

The two values collided over the same slot. A slot normally holds just one value, so two arriving at once is a problem.
But that is no reason to give up on hashing. With a well-chosen calculation collisions are rare, and everything else is still fast, done in one step. So you only need to handle collisions separately when they happen. Let's see how.

Handling collisions separately

There are two main ways to resolve a collision. One is to keep several values together in one slot: each slot holds a small list, and the values that collided go into it side by side.
The other is to push the value on to a neighboring slot: if the original slot is taken, you find the next empty slot and put it there. Either way, no value is lost, and you can find it again later.

Choose a method and tap it. Resolve the collision by keeping both in one slot or pushing one to the slot next door.

The collision was resolved neatly. Whether kept together or pushed next door, each value settled safely into a place.
Follow the same rule when searching and you can find the collided values too. But when the slots are almost full, collisions become frequent, so before they fill up, the slots are increased and everything is placed again. Collisions are occasional and easy to handle, so hashing stays fast and dependable.

Summary

In short: hashing decides a slot number by a calculation on the value. When putting in, you put the value in that slot; when searching, the same calculation takes you to that slot. So you get there in one step without scanning.
When a collision occasionally happens, with different values heading for the same slot, it is handled separately, by keeping them together in one slot or pushing one next door. Finding things directly by calculation: that is hashing.

Tap the key points in order to review. (decide the slot by calculation → find it at once with the same calculation → collision in the same slot → handle collisions separately)

Now you know how to find a value directly by calculation. The frustration of scanning places was solved with a single calculation.
But there are things hashing cannot do. Because the slots are scattered regardless of the size of the values, it cannot search by range, such as everything from A to C, or list things in order. The next lesson introduces a container that finds things fast while keeping them in order: the tree.