# Hashing and Hash Tables — Part 1: The Concept

## 1. What a Hash Function Does

A **hash function** takes an input of arbitrary size (a string, an object, anything) and deterministically produces a fixed-size output — usually an integer — called a **hash code**. The same input always produces the same hash code.

```js
function simpleHash(str) {
  let hash = 0;
  for (let i = 0; i < str.length; i++) {
    hash = (hash * 31 + str.charCodeAt(i)) | 0; // |0 keeps it a 32-bit integer
  }
  return hash;
}
simpleHash("hello"); // always the same number for "hello"
simpleHash("world"); // a different number (almost always)
```

A good hash function is **fast**, **deterministic**, and **spreads outputs evenly** across the possible output range, minimizing how often two different inputs produce the same output.

## 2. What a Hash Table Is

A **hash table** is a data structure that uses a hash function to map keys to array indices (called "buckets"), giving **average O(1)** lookup, insertion, and deletion — dramatically faster than scanning a list (O(n)) for large datasets.

```
key "name" -> hash("name") -> 47 -> bucket[47 % tableSize] -> stores { key: "name", value: "Ana" }
```

JavaScript's `Object`, `Map`, and `Set` are all implemented internally using hash tables — this is *why* property/key lookup on them is fast regardless of how many entries exist.

## 3. Hash Collisions

Two different inputs can produce the **same** hash code (or map to the same bucket after modulo) — this is called a **collision**, and it's mathematically unavoidable once you have more possible inputs than output slots (the pigeonhole principle).

```
hash("Alice") % 10 = 3
hash("Bob")   % 10 = 3   <- collision, both land in bucket 3
```

## 4. Collision Resolution Strategies

![Alice and Bob both hash to bucket 3; separate chaining stores both as a short list in that one bucket](diagrams/01-buckets-and-chaining.svg)

| Strategy | How it works |
|---|---|
| **Separate chaining** | each bucket holds a list (or small array) of all entries that hashed there; on collision, just append |
| **Open addressing (linear probing)** | on collision, keep checking the next slot (`+1`, `+1`, ...) until an empty one is found |
| **Open addressing (double hashing)** | use a second hash function to compute the probing step size, spreading collisions more evenly than linear probing |

```
Separate chaining, bucket 3: [ {key:"Alice",...}, {key:"Bob",...} ]
  — lookup for "Bob" hashes to bucket 3, then linearly scans that
    small list to find the matching key
```

Real-world hash table implementations (including JS engines' internal `Map`/`Object` implementations) use variations of these strategies, often switching approach based on how full the table is.

## 5. Load Factor and Resizing

**Load factor** = number of entries ÷ number of buckets. As load factor rises, collisions become more frequent and performance degrades toward O(n). Hash tables automatically **resize** (allocate a bigger underlying array and rehash every entry) once load factor crosses a threshold (commonly ~0.75), to keep operations close to O(1) on average.

Continue to `js_hashing_and_hash_tables_theory_2.md` to build one of these from scratch.