How Hashing Works

Finding things without searching

Searching a vector checks items one by one: O(n). A hash table finds an item almost instantly: O(1) on average. In C++ that's unordered_map and unordered_set.

Think of it like this: A coat check at a theatre: you get ticket 42 for your coat. Later nobody searches every hook – they go straight to hook 42. The ticket number is like a hash.

The hash function

A hash function turns a key into a number that decides which slot (bucket) the item goes in. The same key always gives the same number, so the table knows exactly where to look later:

#include <iostream>
#include <string>
using namespace std;

int main() {
    int slots = 10;
    for (string word : {"apple", "mango", "kiwi"}) {
        int number = 0;
        for (char c : word) number += c;      // a very simple hash
        cout << word << " -> slot " << number % slots << endl;
    }
    return 0;
}

Output

apple -> slot 0
mango -> slot 0
kiwi -> slot 6

apple and mango both land in slot 0 – a collision. Real hash tables handle that (each slot can hold a short list), and with a good hash function collisions are rare. That's why lookups are O(1) on average.

Choosing a container

Common mistake: Never rely on the order you get when looping over an unordered_map. It can change between compilers and even between runs. If you need sorted output, use map or sort the keys.