# Hash tables

> Hash a key to pick a bucket, and get average O(1) insert, lookup and delete — the structure behind maps, sets, caches and indexes.

Concept · Algorithms & complexity · https://levelcode.org/concepts/hash-tables

A **hash table** stores key–value pairs in an array of buckets. A **hash function** turns the key into a number, and that number modulo the array size picks the bucket. Lookup repeats the same calculation and checks one bucket, so insert, lookup and delete take **O(1) on average**, regardless of how many items are stored. Go's `map`, JavaScript's `Map` and Python's `dict` are hash tables.

## Collisions and resizing

Different keys can land in the same bucket — a **collision**. Implementations handle it in one of two ways:

- **Chaining:** each bucket holds a small list (or array) of entries, scanned on lookup.
- **Open addressing:** on a collision, probe other slots in a fixed sequence until a free one is found.

Either way, performance depends on the **load factor** — items divided by buckets. As it rises, buckets get longer, so tables **resize** (typically doubling) and rehash every entry when a threshold is crossed. One insert then costs O(n), but resizes are rare enough that inserts stay amortized O(1).

A good hash function spreads keys evenly. A poor one, or an attacker who can choose keys that collide, pushes everything into a few buckets and degrades lookups to O(n) — the basis of hash-flooding denial-of-service attacks, which is why Go and other runtimes seed their hash functions randomly per process.

## What hash tables don't do

- **No order.** Iterating a Go map visits keys in an unspecified order (deliberately randomised). Need sorted keys? Collect and sort them, or use a tree.
- **No range queries.** "All keys between A and F" requires a scan; a [B-tree](https://levelcode.org/concepts/b-tree-vs-lsm-tree) answers it directly.
- **Keys must be hashable and comparable.** In Go, slices and maps can't be map keys; in JavaScript, object keys are compared by reference.

## Where they show up

Hash tables are the workhorse for de-duplication, counting, joining data in memory, caches (an LRU cache pairs one with a linked list), and turning O(n²) "search inside a loop" code into O(n). Databases use them for hash joins and hash indexes, and distributed systems extend the idea across machines with [consistent hashing](https://levelcode.org/concepts/consistent-hashing). See the [data structures lesson](https://levelcode.org/roadmaps/software-engineer/data-structures) for worked examples.