Hashing: a name tag that finds the slot

The name tag decides the slot number

Earlier we learned values
sit lined up by slot numbers.
To find one we had to scan slot by slot.
But what if we look at the value itself
and decide its slot number from it?
Like picking a slot from a name's letters.
We set up a small calculation
that takes a value and gives a slot number.
That calculation is called a hash function.

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

Each value got its slot right away.
No need to wonder where to put it.
The calculation tells the spot.
Put the same value in again
and the result is always the same slot.
So slots do not wander about.
Then for finding too,
can we not use the same calculation?

Calculate and jump straight to the slot

When finding, the secret is the same.
Put the searched value into the same calculation,
get the slot number,
and head straight to that slot.
No need to scan slot by slot.
The calculation used to put in
and the one used to find are the same,
so the stored slot matches the searched slot.
So you arrive in one step.

Tap a value to find. The same calculation gives the slot number, and it jumps straight there without scanning.

It arrived at once without scanning.
Whether there are a hundred slots or ten thousand,
the effort stays about the same.
One calculation, one jump, and done.
This is why hashing is fast.
But one thing nags.
What happens if two different values
calculate to the same result?

Two head for the same slot

The calculation always names a slot,
but different values do not mean different slots.
Two different values
can happen to calculate to the same result.
Then both head for the same slot.
Two of them want one slot.
This bumping over the same slot
is called a collision.
Collisions are rare but they do happen.

Tap the two values in turn. They calculate to the same result, so both go to the same slot and collide.

Two bumped over the same slot.
A slot usually holds just one,
so two arriving at once is a problem.
Still, we cannot give up hashing.
A collision is once in a while,
and the rest are still fast in one step.
So only when a collision happens
we handle it a little on the side.
Shall we see how it is handled?

Collisions get handled separately

There are two main ways to solve a collision.
One is to bundle two into one slot.
Keep a small bundle in the slot
and place the bumped values there side by side.
The other is to push to a neighbor slot.
If the original slot is full,
find an empty neighbor slot and put it there.
Either way no value is lost
and it can be found again later.

Pick and tap a handling method. Bundle into one slot, or push to a neighbor slot to resolve the collision.

The collision was solved cleanly.
Whether bundled or pushed to a neighbor,
the value settled safely into a spot.
When finding, follow the same rule
and even a collided value is found well.
Collisions are occasional and handling is simple,
so hashing stays fast and dependable.
Now let's wrap the whole thing up.

Let's wrap up

Gathered on one line, it is this.
Look at the value, calculate the slot number.
When putting in, put it at that slot;
when finding, the same calculation goes to that slot.
So it reaches in one step without scanning.
Now and then a collision happens
when another value goes to the same slot, and we handle it apart.
Bundle them, or push to a neighbor slot.
Finding at once by calculation, that is hashing.

Tap the key points in order to review. (decide slot by calculation -> find at once by the same calculation -> same-slot collision -> handle collisions apart)

Now you know a clever way
to find a value at once by calculation.
The stuffiness of scanning slots
cleared up with a single calculation.
Knacks like this, making putting in and finding fast,
are the power of handling data.
Next, with what other way
can we store and find values even better?
Let's keep exploring together.