Hash table internals

A hash table (Map/plain object in JS, HashMap in Kotlin, Map in Dart) stores key–value pairs and gives O(1) lookup on average. Only three steps sit behind that:

• A hash function turns the key into an integer: hash("email") → 2938471
• A bucket index squeezes that integer into the array size: index = hash % capacity
• The bucket — that slot of the internal array, where the pair actually lands

So a hash table is not magic — it is an ordinary array. The only difference is that the index does not come from you, it is computed from the key. You never have to walk the array: compute the index once and go straight there.

What makes a good hash function? Three requirements:

• Deterministic — the same key always produces the same hash. Otherwise you could never find back what you stored.
• Uniform distribution — keys should spread across buckets. If they all land in one bucket, the hash table degenerates into a plain list.
• Fast — computing the hash must not cost more than the lookup it saves.

Note: cryptographic strength is NOT a requirement here. SHA-256 is needlessly expensive for a hash map; real runtimes use cheap functions like MurmurHash, SipHash, or a simple 31 * h + char.

One more critical rule: the hash must be stable. If you mutate a hash-relevant field of an object you already used as a key, the entry is effectively "lost" — it stays in the old bucket while you look in the new one.

Why O(1) average and O(n) worst case?

Average case: if the hash spreads keys evenly, each bucket holds about one element. Computing the index is O(1) and scanning inside the bucket is O(1) — O(1) in total.

Worst case: if every key lands in the same bucket (bad hash function, or deliberately crafted keys), that bucket becomes one long chain and lookup degrades to O(n). This is not a theoretical fear — hash flooding attacks do exactly this, which is why modern runtimes salt their hashes with a random seed.

Resizing is a separate nuance: when the load factor crosses 0.75 the map doubles its capacity and rehashes every entry — that single put costs O(n). But because it happens once every n operations, the amortized cost stays O(1). If you know the size up front (new HashMap(expectedSize)), you avoid those repeated rehashes entirely.