RightSignal

Data structures · 4 of 111 / 3

Hash tables

The concept

How your phone finds one contact among thousands instantly

A hash table is a way of storing things so you can find any one of them in a single step, however many there are. It doesn't search. It works out exactly where the item must be.

Picture a coat check with a thousand hooks. The attendant turns your name into a hook number using a fixed recipe. When you return, they use the same recipe on your name and walk straight to that hook.

Data structures · 4 of 112 / 3

Hash tables

Real-life use case

Typing a username and seeing 'already taken' in a blink

When you pick a username, the site checks hundreds of millions of names in a split second. It doesn't go through them one by one. It turns your name into a slot number and looks in that one slot.

The same trick sits behind your phone's contacts, a browser remembering which pages you've visited, and the way most programming languages store lists of named settings.

Data structures · 4 of 113 / 3

Hash tables

How it helps

The name itself tells the computer which drawer to open

The recipe, called a hash function, scrambles any name into a number in a way that always gives the same answer for the same name. That number picks a drawer, so the computer opens one drawer instead of checking them all.

Sometimes two names land in the same drawer. That's fine: the drawer holds a short list, and the computer checks those few items. If drawers get crowded, the table adds more and spreads things out again.

Got it?

6 quick questions on Hash tables.

Learn first: Hash functions · Arrays
Leads to: Bloom filters · Hash functions
Related: B-trees · Database indexes · Bloom filters · Huffman coding
In the brief: Concept of the day, Thu, Oct 15

Your RightSignal

Topics in News

How your phone finds one contact among thousands instantly

Typing a username and seeing 'already taken' in a blink

The name itself tells the computer which drawer to open

Got it?