# Hashing and Hash Tables — Part 2: Building One

## 1. A Minimal Hash Table with Separate Chaining

```js
class HashTable {
  constructor(size = 16) {
    this.buckets = new Array(size).fill(null).map(() => []);
    this.size = size;
    this.count = 0;
  }

  _hash(key) {
    let hash = 0;
    const str = String(key);
    for (let i = 0; i < str.length; i++) {
      hash = (hash * 31 + str.charCodeAt(i)) % this.size;
    }
    return hash;
  }

  set(key, value) {
    const index = this._hash(key);
    const bucket = this.buckets[index];
    const existing = bucket.find(entry => entry[0] === key);
    if (existing) {
      existing[1] = value; // update
    } else {
      bucket.push([key, value]);
      this.count++;
    }
  }

  get(key) {
    const bucket = this.buckets[this._hash(key)];
    const entry = bucket.find(entry => entry[0] === key);
    return entry ? entry[1] : undefined;
  }

  has(key) {
    return this.buckets[this._hash(key)].some(entry => entry[0] === key);
  }

  delete(key) {
    const bucket = this.buckets[this._hash(key)];
    const index = bucket.findIndex(entry => entry[0] === key);
    if (index === -1) return false;
    bucket.splice(index, 1);
    this.count--;
    return true;
  }
}
```

## 2. Why the Modulo Matters

`hash % this.size` compresses a potentially huge hash number down into a valid array index (`0` to `size - 1`). This is the step that actually creates collisions in practice — even a perfect, evenly-distributed hash function will produce colliding *bucket indices* once you have more keys than buckets.

## 3. Why This Beats a Plain Array of `[key, value]` Pairs

```js
// Naive linear search — O(n) every lookup
function linearGet(pairs, key) {
  for (const [k, v] of pairs) if (k === key) return v;
  return undefined;
}

// Hash table — O(1) average: jump straight to the right bucket,
// then scan only the (typically very short) list of collisions within it
```

With 1,000,000 entries, a linear search checks up to 1,000,000 pairs in the worst case. A well-sized hash table checks roughly `1,000,000 / bucketCount` entries — a handful, not a million.

## 4. Worst-Case vs Average-Case

| Operation | Average case | Worst case |
|---|---|---|
| `get`/`set`/`delete` | O(1) | O(n) — if every key collides into the same bucket |

The worst case happens with a poor hash function (everything collides) or a deliberately crafted "hash flooding" attack against a predictable hash function — one reason production hash table implementations use randomized hash seeds.

## 5. Resizing (Rehashing) Sketch

```js
_resize(newSize) {
  const oldEntries = this.buckets.flat();
  this.size = newSize;
  this.buckets = new Array(newSize).fill(null).map(() => []);
  this.count = 0;
  for (const [key, value] of oldEntries) this.set(key, value); // re-hash every entry into the new size
}
```

Every entry must be rehashed because `hash % size` depends on `size` — changing the table size invalidates every existing bucket assignment.

## 6. Under the Hood: What Real Engines Do Differently From This Sketch

The `HashTable` class built above teaches the correct mental model, but production engines refine it in a few concrete ways worth knowing.

### String hash codes are computed once and cached

Recomputing a string's hash on every lookup would waste work for strings used repeatedly as keys (property names, `Map`/`Set` keys). V8 computes a string's hash lazily on first use, then **caches it directly inside the string object's own header** — a spare bit-field reserved for exactly this. Every subsequent hash of that same string instance is a cheap field read, not a recomputation character-by-character. This is part of why using the same repeated string literal as a key across many lookups is cheaper than it looks.

### Randomized seeds defeat "hash flooding" attacks

Section 4 mentions hash-flooding: an attacker who knows your exact hash function can craft many different inputs that all collide into the same bucket, degrading every lookup to O(n) and creating a denial-of-service vector (this is a documented, real category of vulnerability that affected multiple language runtimes historically). Production hash table implementations mix in a **random seed**, generated once per process, into the hash computation — so the mapping from input to bucket differs between runs and can't be predicted by an external attacker who only knows the hash algorithm itself, not the runtime's private seed.

### Real hash tables in engines are exactly this + the OrderedHashTable layer

The Map and Set topics' "Under the Hood" sections describe V8's actual `OrderedHashMap`/`OrderedHashSet` — which is precisely this chapter's chaining-based hash table, with one additional layer bolted on: a separate insertion-ordered entries array, so that iteration order matches insertion order (something a raw hash table, as built in this topic, does not guarantee at all — see the last Common Pitfall below).

## 7. Common Pitfalls

1. **Using a hash function that only depends on length or a single character** — produces massive collision rates; always fold in every character's contribution (as `_hash` above does).
2. **Forgetting to update, not duplicate, an existing key** — `set` must check for an existing entry in the bucket first, or you'll get duplicate `[key, value]` pairs for the same key.
3. **Never resizing** — a fixed-size table degrades to O(n) performance as more entries are added and load factor climbs.
4. **Assuming hash tables preserve insertion order** — a raw hash table (unlike JS's actual `Map`) generally does not; `Map`'s insertion-order guarantee is an additional design choice on top of hashing, not an inherent property of hash tables.

## 8. Quick Reference

```
hash(key) -> number -> index = hash % bucketCount
collision  -> chaining (list per bucket) or open addressing (probe next slot)
load factor = entries / buckets   -> resize when too high
average case O(1), worst case O(n)
```