What is a hash table?
A hash table stores key → value pairs. A hash function turns each key into a
number, then that number picks a bucket — a slot in an array. Most of the time
you jump straight to the right bucket, so lookups feel like O(1) on average.
- Key
- The label you look things up by — a name, an id, a word
- Value
- Whatever you store under that key — a count, an index, an object
- Hash
- A number computed from the key; same key → same hash
- Bucket
- One slot in the underlying array where that hash lands
- Collision
- Two keys hash to the same bucket — the table needs a plan (a chain, or a probe)
See it: key → hash → bucket
Watch a key fly into the hash function. The function spits out a bucket index, and the pair lands in that slot — like dropping a coat at the numbered hook the attendant gives you.
When a second key hashes to the same hook, it chains on — a short linked list in that bucket. Collisions are normal; good tables just keep chains short.
Same key always lands in the same bucket. Collisions share a chain.
Types of hash tables
Two big design choices: how you handle collisions, and what the API stores. Chaining hangs a list off each bucket. Open addressing finds another empty slot in the array when a bucket is taken.
In TypeScript, Map is key → value. Set is “keys only” — a membership
bag with the same hashing idea underneath.
Collisions answer “where if taken?” API answers “value or membership?”
How it is stored in memory
Declaring a Map keeps a reference on the call stack. The real table lives on
the heap: an array of buckets, and — with chaining — short lists hanging off the
busy slots.
Press Next to declare, allocate buckets, then hang a chain after a collision.
Start here. Each step highlights the TypeScript below.
Operations
Everyday work is hash, then touch one bucket. On average that is O(1) —
get, set, delete, and has all tell the same story. Iterating keys walks every
entry, so that one is O(n). For Map/Set methods and snippets, open the
Functions tab.
Get
Hash the key, open that bucket, walk a short chain until the key matches — or the chain ends.
Hash "tea" → land in bucket 2. Peek the chain.
Set / put
Hash, then write. Empty bucket gets a new link; an existing key just updates its value.
Put "lin" → 29. Hash picks bucket 1.
Delete
Find the link in the bucket’s chain and unlink it. Neighbors in other buckets do not move.
Delete "ada". Hash to bucket 0 and walk the chain.
Has
Same path as get, but you only ask “is it there?” — no value to return.
Ask has("zoe"). Hash lands in bucket 3.
Iterate keys
Walk every non-empty bucket and yield each key. Cheap per entry, linear in the whole table.
Iterate keys: visit bucket 0 chain first.