Hashing & Hash Tables: Introduction to O(1) Lookup

Hashing is a technique for turning a key (a number, string, or object) into an array index so you can store and find its value almost instantly. The structure built on top of it — a hash table (also called a hash map or dictionary) — gives you O(1) average time for insert, lookup, and delete by key. That is the single biggest speed-up in everyday programming: it turns many slow O(n) scans into one fast jump.

The problem hashing solves

Suppose you have a list of users and you keep asking “is this email already registered?”. With a plain array you must scan every element — O(n) per query. A hash table answers the same question in O(1) average time by computing where the key would live instead of searching for it.

The core idea

A hash table is just an array of “buckets” plus a hash function that maps any key to a bucket index:

index = hash(key) % numberOfBuckets

To store a key/value pair, compute the index and drop it in that bucket. To look it up, compute the same index and read it back. No scanning — you go straight there. (We cover the hash function itself in hash functions.)

A first hash table

Every language ships a ready-made hash table. Here is the same “count, store, and look up” in all four — switch the tab to your language:

#include <unordered_map>
#include <string>

std::unordered_map<std::string, int> ages;
ages["alice"] = 30;          // insert  — O(1) average
bool has = ages.count("alice"); // lookup — O(1) average
int a = ages["alice"];        // read    — O(1) average
ages.erase("alice");          // delete  — O(1) average

import java.util.HashMap;
import java.util.Map;

Map<String, Integer> ages = new HashMap<>();
ages.put("alice", 30);             // insert — O(1) average
boolean has = ages.containsKey("alice"); // lookup — O(1) average
int a = ages.get("alice");          // read   — O(1) average
ages.remove("alice");               // delete — O(1) average

const ages = new Map();
ages.set("alice", 30);     // insert — O(1) average
const has = ages.has("alice"); // lookup — O(1) average
const a = ages.get("alice");   // read   — O(1) average
ages.delete("alice");        // delete — O(1) average

ages = {}
ages["alice"] = 30        # insert — O(1) average
has = "alice" in ages     # lookup — O(1) average
a = ages["alice"]         # read   — O(1) average
del ages["alice"]         # delete — O(1) average

Why “average” and not “guaranteed” O(1)

Two different keys can hash to the same bucket — a collision. A few collisions are fine, but if many keys pile into one bucket, operations degrade toward O(n). Good hash functions and collision resolution keep collisions rare, so the average stays O(1) even though the worst case is O(n).

For beginners: A hash table is the same idea as a real dictionary — you don’t read every page to find “apple”; you jump to the “A” section. The hash function is what tells you which section to open.

Going deeper: The O(1) average relies on keeping the load factor (entries ÷ buckets) low. When it crosses a threshold the table resizes — allocating a bigger bucket array and rehashing everything. That resize is O(n), but amortized over many inserts each insert is still O(1), the same amortization that makes dynamic arrays cheap.

What you give up

Hash tables are unordered — iterating gives no meaningful order (unlike a sorted structure or a balanced BST). If you need keys in sorted order or range queries, a hash table is the wrong tool. For pure key lookup, it is unbeatable.

When to reach for a hash table

• Membership tests (“have I seen this before?”) — see hash sets.
• Counting frequencies, grouping, and key/value lookups — see applications & patterns.
• Replacing a nested O(n²) loop with a single O(n) pass plus O(n) memory.

Next: what makes a good hash function, then collision resolution.