How a hash table works

A hash table is an array plus a function. The hash function turns a key into an integer; the integer, reduced modulo the array size, is the slot. Because computing it takes constant time and indexing takes constant time, lookup is O(1).

function hash(key, buckets) {
  let h = 0;

  for (let i = 0; i < key.length; i++) {
    h = (h * 31 + key.charCodeAt(i)) | 0;   // 31: odd prime, cheap to multiply
  }

  return Math.abs(h) % buckets;
}

That * 31 + char loop is Java's String.hashCode, and it is a reasonable default: fast, and it spreads similar strings apart.

What a good hash function must do

1. Deterministic — the same key always gives the same slot, or nothing works.
2. Uniform — keys spread evenly across buckets. Clustering destroys the O(1).
3. Fast — it runs on every single operation.
4. Avalanche — one changed bit in the key should change roughly half the output bits, so user1 and user2 land far apart.

Cryptographic hashes like SHA-256 satisfy all of these and are far too slow for a hash table. Table hashing uses non-cryptographic functions — FNV, MurmurHash, xxHash — chosen for speed and distribution.

The load factor

The ratio of entries to buckets. As it approaches 1, collisions climb and performance falls off a cliff. Implementations resize — typically doubling and rehashing everything — when the load factor crosses about 0.75.

Rehashing is O(n), but it happens rarely enough to be O(1) amortised, exactly like the dynamic array's doubling.

// A resize repositions every key, because the modulus changed.
// This is why hash tables have occasional latency spikes.

What you get, and what you give up

Hashing trades ordering for speed. The moment you need "the next key after x" or "all keys between a and b", a hash table cannot help you, no matter how fast it is.