# Hashing and Dictionaries

Computer Science I · Data Structures · https://tryals.app/learn/computer-science-i/hashing-and-dictionaries

## Finding Things Instantly

A **dictionary** (map) ADT stores **key–value** pairs for fast lookup, insertion, and deletion by key. The underlying structure is the **hash table**.

A **hash function** computes an integer from a key. Reduced modulo the array size, this gives the **index** of the bucket holding that value:

$$\text{index} = \text{hash(key)} \bmod m$$

When keys spread evenly, operations take **$O(1)$ on average**. Because two different keys can yield the same index, **collisions** occur. Every hash table uses a **collision-resolution** strategy to prevent overwriting values.

| Strategy | Mechanism |
| --- | --- |
| **Chaining** | Stores a small list at each bucket for all matching keys |
| **Open addressing** | Probes to a different empty bucket by a fixed rule |

## Performance and Pitfalls

Performance relies on the **load factor** (elements divided by buckets). As the table fills, collisions increase. To maintain speed, hash tables **resize** by allocating a larger array and rehashing all elements.

> **Common Pitfall:** Believing hash lookups are _guaranteed_ $O(1)$. The $O(1)$ is an **average** under a good hash function and low load factor.

| Case | Complexity | Condition |
| --- | --- | --- |
| **Average case** | $O(1)$ | Good hash function, reasonable load factor |
| **Worst case** | $O(n)$ | Many keys colliding into a single bucket |

## Practice questions

4 of this lesson's 10 practice questions, with answers. The full set is in the app.

### 1. Hash-table lookup is described as O(1), yet the worst case is O(n). Why is the constant-time figure still the honest way to describe it?

A. Because O(1) is the expected cost under a hash that spreads keys evenly.
B. Because the worst case never actually occurs, so it can be disregarded entirely.
C. Because O(1) refers to the hashing step alone, and the bucket search is counted separately.
D. Because hash tables automatically rebalance to prevent the worst case from arising.

**Answer:** A. Because O(1) is the expected cost under a hash that spreads keys evenly.

**Why:** The O(1) is an expected cost: with a decent hash and a bounded load factor each bucket holds a small constant number of entries. The worst case is improbable by accident and reachable on purpose, an attacker who knows the hash function can construct colliding keys and turn every lookup linear. The defence is per-process randomised hashing, which most runtimes now do.

Page: https://tryals.app/practice/computer-science-i/hashing-and-dictionaries/hash-table-lookup-is-described-as-o-1-yet-the-worst-case-is-o-n

### 2. Order the steps a hash table takes to look up a value by its key, using chaining.

**Answer:**

1. Apply the hash function to the key to get an integer
2. Reduce that integer modulo the number of buckets to get an index
3. Jump straight to the bucket at that index
4. Search the short list held at that bucket for the matching key
5. Return the value stored alongside that key

**Why:** Hashing and the modulo give an index with no memory reads at all, which is why the jump is direct; only then is the bucket's short chain searched. The whole cost is that final search, so keeping chains short, which is what the load factor and resizing control, is what keeps lookup constant on average.

Page: https://tryals.app/practice/computer-science-i/hashing-and-dictionaries/order-the-steps-a-hash-table-takes-to-look-up-a-value-by-its-key

### 3. Language runtimes now seed their hash functions randomly at process start, so the same string hashes differently between runs. What attack does that prevent?

A. Guessing the contents of a hash table from its size
B. Forging authentication tokens derived from hash outputs
C. Hash flooding, crafted keys that all collide into one bucket
D. Reading other processes' memory through predictable hash values

**Answer:** C. Hash flooding, crafted keys that all collide into one bucket

**Why:** The O(n) worst case is improbable by accident and reachable on purpose, a few thousand colliding form fields can pin a CPU. Random seeding makes the collisions unpredictable, and it is a good illustration that 'the worst case never happens' holds only while nobody is trying.

Page: https://tryals.app/practice/computer-science-i/hashing-and-dictionaries/language-runtimes-now-seed-their-hash-functions-randomly-at-process

### 4. Sort each description by the collision-resolution strategy it describes.

**Answer:**

- Chaining: Each bucket holds a small list of all the keys that landed there, The number of stored elements can exceed the number of buckets, A lookup ends by scanning the short list at one bucket
- Open addressing: When the chosen bucket is taken, a fixed rule probes a different bucket, Every key is stored directly in the bucket array itself

**Why:** Chaining hangs a list off each bucket, so it can hold more elements than buckets and finishes a lookup by scanning that list. Open addressing keeps every key inside the array and moves on to another bucket by a fixed rule, so it cannot hold more elements than buckets. Either way the collision must be handled, or values would overwrite each other.

Page: https://tryals.app/practice/computer-science-i/hashing-and-dictionaries/sort-each-description-by-the-collision-resolution-strategy-it