Hashing introduction

Hashing: instant lookup

Here's how a hash table answers "have I seen this before?" almost instantly, no matter how much data you have.

The problem it solves

Say you need to check if a value is in a big pile of data. Scanning the whole pile every time is slow — the bigger the pile, the slower it gets. A hash table answers "is this here?" in about the same amount of time whether the pile has 10 items or 10 million.

The core idea

Think of a coat check counter. Instead of searching every rack for your coat, the attendant runs your ticket number through a quick rule that says "rack 42, slot 7" — straight there, no searching. A hash table does the same thing: it runs each key through a hash function that turns it into a slot number in an array. Insert or look up, and you jump straight to that slot instead of searching everything.

When two keys land on the same slot

Sometimes two different keys hash to the same slot — a collision, like two coats assigned to the same peg. Two common fixes:

Chaining — each slot holds a small list of everything that landed there. Hash to the slot, then check that short list.
Open addressing — one key per slot. On a collision, move to the next open slot and try there.

Either way, the table stays fast as long as it isn't too crowded. When it gets too full (the load factor climbs too high), it resizes — grows the array and re-files everything — so lookups stay close to instant.

Sets vs. maps

A hash set just stores keys: "is X here?" A hash map stores key → value: "what's attached to X?" In Go, map[string]int is a hash map; map[string]bool is commonly used as a set.

Patterns you'll use constantly

Counting — bump a counter per key. Build it in O(n), read any count in O(1).
Finding pairs — remember values you've seen; for each new value, check whether its partner already showed up.
Deduplication — a set throws away duplicates for free.

The one rule to remember

A nested loop that rescans data to answer "have I seen this?" is O(n²). Swap that inner loop for a hash lookup and it drops to O(n). Trading a bit of memory for a lot of speed is the whole trick — every problem in this section is a version of it.