Hashing and Hash Tables: Complete Beginner's Guide

Hashing finds data almost instantly: you compute a number from the item's key (like a name or ID) with a hash function, and that number tells you exactly which table slot to check. A hash table is the array of slots where items live — like a library where a formula on the title reveals the exact shelf.

Hash tables give average O(1) insert, delete, and search — the fastest lookups in computing. Python dicts, Java HashMaps, database indexes, caches, and password storage all rely on hashing. Logging in to a website very likely queried a hash table once to find your account.

Key Concepts

• Key / value: the identifier you search by (a username) and its attached data (the profile).
• Hash function: maps a key to an index, e.g., index = hash(key) mod table_size; a good one spreads keys evenly and is fast.
• Collision: two keys hashing to the same slot — normal and expected; the question is how you handle it.
• Chaining: each slot holds a linked list of the keys that hashed there.
• Linear probing: on collision try the next slot, then the next: index = (hash + i) mod m for i = 0, 1, 2, ….
• Load factor (α): α = n / m (items / slots); crossing ~0.7 triggers a rebuild into a bigger table (rehashing).

Formulas

• Index: index = h(key) mod m. With m = 7, key 15 lands at 15 mod 7 = 1.
• Load factor: α = n / m. Five items in 7 slots gives α ≈ 0.71 — time to resize.
• Average search: about 1 + α/2 comparisons with chaining; near-constant while α stays well below 1.
• Worst case: O(n) if every key collides into one slot — why the hash function and resizing matter.
• Assumptions: O(1) average needs a uniform hash function and a bounded load factor maintained by resizing.

Worked Example

Insert 15, 22, 8, 29 into an empty size-7 table using h(key) = key mod 7 with linear probing. 15 mod 7 = 1 → slot 1 empty, store 15. 22 mod 7 = 1 → slot 1 taken, probe slot 2 (empty), store 22. 8 mod 7 = 1 → slots 1, 2 taken, probe slot 3 (empty), store 8. 29 mod 7 = 1 → slots 1–3 taken, probe slot 4 (empty), store 29. Final: slot 1 = 15, slot 2 = 22, slot 3 = 8, slot 4 = 29. Search for 8: compute slot 1, check 15 (no), slot 2: 22 (no), slot 3: 8 (found!) — 3 probes instead of a full scan. Load factor is 4/7 ≈ 0.57, safely below 0.7.

Common Misconceptions

• "Good hash functions eliminate collisions." Wrong. Collisions are unavoidable once keys outnumber slots — good design handles them, not prevents them.
• "Hashing is encryption." Wrong. A table hash is just recomputed on lookup; encryption hides data with a key. Never store passwords with a plain table hash.
• "Tables iterate in insertion order." Wrong in general — slots follow hash values, so order looks random. (Python's dict adds insertion order as an extra feature.)

Real-World Applications

• Dictionaries/maps: Python dict, Java HashMap, JavaScript objects.
• Database indexes: hash indexes answer exact-match queries in one read.
• Caches: web and CPU caches map addresses to data via hashing.
• Deduplication: file systems hash contents to spot duplicate chunks.

Hashing trades a little arithmetic for the fastest lookups in computer science: compute the slot, jump straight there, handle the odd collision, and resize before the table crowds. That recipe sits under nearly every dictionary, cache, and login system you use.