Algorithms

Hash Tables Explained by How Search Engines Find Words

Learning how a hash table finds one word among millions of web pages, using a school locker picture.

It’s a Saturday afternoon in the computer lab. You’re a college sophomore, and you’ve been clicking through Yahoo’s lists (Recreation, then Sports, then Basketball) to find one team’s schedule. It works, but it’s slow, like flipping through a library’s card catalog.

So you try something different. You type a single word into AltaVista’s search box and press Enter. About a second later, a list of pages appears. How does a computer find one word among a huge number of web pages that fast?

Yahoo’s lists are built by people, and people can’t keep up with a web that grows every day. A search engine has to do the work itself. The trick behind it is a hash table.

Why not just read every page?

The simplest plan is to start at the first page, read every word, and note each page where your word shows up. That’s a linear scan: one page after another, in a line.

Here is a tiny web of four pages, and a scan for “pizza”.

const std::vector<std::vector<std::string>> pages = {
    {"pizza", "deals", "near", "campus"},
    {"campus", "basketball", "scores"},
    {"pizza", "recipes", "fast"},
    {"basketball", "shoes", "sale"},
};

std::size_t checked = 0;
for (std::size_t i = 0; i < pages.size(); ++i) {
    for (const auto& word : pages[i]) {
        ++checked;
        if (word == "pizza") {
            std::println("Found \"pizza\" on page {}", i);
        }
    }
}
std::println("Words checked: {}", checked);
Found "pizza" on page 0
Found "pizza" on page 2
Words checked: 13
pages = [
    ["pizza", "deals", "near", "campus"],
    ["campus", "basketball", "scores"],
    ["pizza", "recipes", "fast"],
    ["basketball", "shoes", "sale"],
]

checked = 0
for i, page in enumerate(pages):
    for word in page:
        checked += 1
        if word == "pizza":
            print(f'Found "pizza" on page {i}')
print(f"Words checked: {checked}")
Found "pizza" on page 0
Found "pizza" on page 2
Words checked: 13

The scan had to look at all 13 words. With four pages, that’s nothing. With a web that keeps growing, every search would take longer than the one before it. If the web doubles in size, the scan takes twice as long.

What if every word had its own locker?

Think about a school hallway. You never search every locker for yours. Your locker number tells you exactly where to go.

Picture it: Give every word in the world a locker. Inside each locker, keep a note listing the pages where that word appears. To search for “pizza,” you don’t read any pages. You work out which locker belongs to “pizza,” walk straight to it, and read the note. The hallway can be huge, but you only ever open one door.

A hash table is that hallway. The rule that turns a word into a locker number is called a hash function. Here is a simple one. Add up the numeric codes of the letters (a computer stores each letter as a number), divide by the number of lockers, and keep the remainder:

locker=(sum of letter codes) mod 10 \text{locker} = (\text{sum of letter codes}) \bmod 10

The “mod” symbol means “the remainder after dividing.” With 10 lockers, the answer is always a number from 0 to 9.

std::size_t locker(const std::string& word, std::size_t lockers) {
    std::size_t total = 0;
    for (char c : word) {
        total += static_cast<unsigned char>(c);
    }
    return total % lockers;
}

for (const auto* word : {"pizza", "campus", "basketball"}) {
    std::println("{} -> locker {}", word, locker(word, 10));
}
pizza -> locker 8
campus -> locker 9
basketball -> locker 5
def locker(word, lockers):
    return sum(ord(c) for c in word) % lockers


for word in ["pizza", "campus", "basketball"]:
    print(f"{word} -> locker {locker(word, 10)}")
pizza -> locker 8
campus -> locker 9
basketball -> locker 5

The same word always lands in the same locker. That’s what makes the walk straight to it possible.

What happens when two words want the same locker?

With only 10 lockers and many words, some words are bound to land on the same number. That’s a collision. It’s like two students being assigned one locker.

One fix is chaining: let each locker hold a short list, so the two words share it. Another fix is open addressing: if your locker is taken, walk down the hallway to the next empty one. This post shows chaining.

std::vector<std::vector<std::string>> lockers(10);
for (const auto& page : pages) {
    for (const auto& word : page) {
        auto& bucket = lockers[locker(word, 10)];
        if (std::ranges::find(bucket, word) == bucket.end()) {
            bucket.push_back(word);
        }
    }
}
for (std::size_t n = 0; n < lockers.size(); ++n) {
    if (lockers[n].size() > 1) {
        std::print("Locker {} is shared by:", n);
        for (const auto& word : lockers[n]) {
            std::print(" {}", word);
        }
        std::println("");
    }
}
Locker 1 is shared by: deals sale
Locker 5 is shared by: basketball scores
lockers = [[] for _ in range(10)]
for page in pages:
    for word in page:
        bucket = lockers[locker(word, 10)]
        if word not in bucket:
            bucket.append(word)

for n, bucket in enumerate(lockers):
    if len(bucket) > 1:
        print(f"Locker {n} is shared by:", *bucket)
Locker 1 is shared by: deals sale
Locker 5 is shared by: basketball scores

Looking up a word now takes two steps: walk to the locker, then check the short list inside. A good hash function spreads words evenly, so each list stays short and the lookup stays fast.

How does a search engine use this?

A search engine does the slow work once, before you ever type anything. It reads every page and builds a hash table where each word points to the list of pages that contain it. This is called an inverted index, because it flips “page → its words” into “word → its pages.”

std::unordered_map<std::string, std::vector<std::size_t>> index;
for (std::size_t i = 0; i < pages.size(); ++i) {
    for (const auto& word : pages[i]) {
        auto& found_on = index[word];
        if (found_on.empty() || found_on.back() != i) {
            found_on.push_back(i);
        }
    }
}
for (std::size_t i : index.at("pizza")) {
    std::println("\"pizza\" is on page {}", i);
}
"pizza" is on page 0
"pizza" is on page 2
index = {}
for i, page in enumerate(pages):
    for word in page:
        found_on = index.setdefault(word, [])
        if not found_on or found_on[-1] != i:
            found_on.append(i)

for i in index["pizza"]:
    print(f'"pizza" is on page {i}')
"pizza" is on page 0
"pizza" is on page 2

When you type “pizza,” the engine doesn’t read a single page. It opens one locker and hands you the note inside. Building the index takes a long time, but you only pay that cost once, and every search after it is quick.

Real engines do more. They rank the pages so the best one comes first, and they pack their lists to save space. But the lookup at the heart of it is this one.

Key takeaways

  • A linear scan checks every item, so it gets slower as the data grows.
  • A hash function turns a word into a locker number, so you can jump straight to the right place.
  • Two words can land in the same locker. Chaining fixes this by letting a locker hold a short list.
  • An inverted index is a hash table from each word to the pages that contain it.
  • Later in this series, we’ll build one on a graphics chip, where thousands of lookups can run at the same time.

Your turn

Using the rule from above (add the letter codes, then take the remainder after dividing by 10), which locker does “near” belong to? The letter codes are n = 110, e = 101, a = 97 and r = 114.

Show the answer

Add the codes: 110+101+97+114=422110 + 101 + 97 + 114 = 422. Dividing 422 by 10 leaves a remainder of 2, so “near” goes in locker 2.

Next time your grandparents ask you how a computer finds one word so fast, tell them this: “It doesn’t look through everything. It works out which locker the word belongs to and opens just that one.”

Art of the Possible With AI