Hashing and Hash Maps

1Hash function to bucket index

A hash table stores key–value pairs in an array of buckets. A hash function maps each key to an integer bucket index, so insert, delete, and lookup avoid a linear scan of every stored key. In the average case those three operations are O(1) — you pay extra space for the bucket array to buy constant-time access by key.

The function does not invent order among keys. Two different keys may land in the same bucket; that collision is handled by the next concept. What hashing buys is a direct jump to a small neighbourhood of the table, not a guarantee that every key has a private cell forever.

Figure. Five equal bucket cells. The hash reduces a key to one index in 0\ldots4; work then stays inside that cell's chain or probe sequence.

Where a key lands

1. Hash the keyCompute an integer from the key (language runtime or a chosen hash).
2. Reduce to a bucketMap that integer into 0 \ldots m-1 for an m-bucket table — typically a modulo or bit mask.
3. Act in that bucketInsert, find, or delete inside the bucket's collision structure. Average work stays O(1) when buckets stay short.

2Collisions: chaining vs open addressing

When two keys hash to the same index, the table must still store both. Separate chaining hangs a list (or tree) off each bucket and walks only that bucket's chain. Open addressing keeps one key per slot and, on a collision, probes onward — linear probing steps one cell at a time, quadratic probing uses a quadratic stride, and double hashing uses a second hash for the step.

Chaining grows local lists; open addressing spreads keys across the array and is sensitive to clustering. Neither removes the need for a good hash and a controlled load factor — they only decide where the colliding key lives.

Figure. Bucket 2 holds a chain apple → apricot → avocado. Open addressing would instead scatter those keys into later empty slots of the array.

Two ways to place a colliding key

1. ChainingAppend the key to the list at the hashed bucket. Lookup walks that list only.
2. Open addressingIf the hashed slot is full, probe the next candidate slot until an empty one appears.
3. Same contractBoth still aim for short searches per operation; the difference is list-at-bucket versus probe-through-array.

3Load factor and rehash

Load factor \alpha = n / m is the ratio of stored entries n to buckets m. As \alpha grows, chains lengthen or probe runs stretch, and average operation time drifts above the O(1) target. Implementations typically resize (often double m) and rehash every key when \alpha crosses a threshold such as 0.75.

A single resize costs O(n) to place every key into the new table. Amortized over many insertions that cost spreads to O(1) per insert — the same doubling argument as a dynamic array — but any one insert that triggers growth still pays the hitch.

Figure. When load factor \alpha grows, rehash into a larger table so average chain length stays near constant.

When the table grows

1. Measure \alphaAfter an insert, \alpha = n/m. Compare to the threshold (e.g. 0.75).
2. Allocate larger mTypically double the bucket count so \alpha halves.
3. Rehash all keysRecompute each key's bucket in the new array — O(n) work once, amortized O(1) per insert across a growth sequence.

4Hash set vs hash map

A hash set stores unique keys and answers membership: is x present? A hash map stores key–value pairs and answers retrieval: what value is bound to k? Both sit on the same hash-table engine, so average insert, delete, and lookup stay O(1) for each.

Reach for a set when the value is only "present or not" (seen characters, visited nodes). Reach for a map when you must remember an associated payload (value → index, character → count). Swapping them usually means you are encoding the payload into a side structure you did not need.

Figure. A set answers membership; a map stores a payload per key — pick by whether you need the associated value.

Pick the structure

1. Only membership?Use a hash set — the key is the whole record.
2. Need a payload?Use a hash map — key looks up the associated value.
3. Same costsAverage O(1) access either way; space still O(n) for n stored keys (plus values in a map).

5Worst case: when hashing falls to linear

Average O(1) assumes keys spread across buckets. With a bad hash or adversarial keys that all collide, every operation walks a structure of size n and degrades to O(n). That is the same cost as a linked list or unsorted scan — the table shape no longer helps.

Some runtimes mitigate long chains by treeifying a bucket past a length threshold, bringing a pathological bucket down to O(\log n) rather than O(n). The average-case slogan still needs the disclaimer: constant time is not a worst-case guarantee unless the hash and load factor cooperate.

Reuse the chaining picture under Collisions: chaining vs open addressing — a long single-bucket chain is exactly the O(n) degeneration; treeified buckets cut that bucket to O(\log n).

How the bound collapses

1. All keys share a bucketHash collisions pile every entry into one chain or one probe cluster.
2. Lookup walks themFinding or rejecting a key compares against \Theta(n) entries.
3. MitigationTreeified buckets (e.g. in Java) cut that walk to O(\log n); they do not restore true O(1) worst case.

6Two Sum in one pass

Given an array and a target, return indices of two values that sum to the target. Brute force tries every pair in O(n^2). The hash-map pattern stores each value's index as you scan: for the current number, ask whether \mathrm{target} - \mathrm{num} was already seen; if yes, return those indices; if not, record the current value → index.

One pass yields O(n) time and O(n) extra space. The map is essential — a set of values alone would lose the indices the problem asks for.

Figure. One pass: for each x look up t-x in the map of prior values; store x after the probe.

One-pass map

1. Empty mapvalue → index, initially empty.
2. ComplementFor nums[i], compute need = target − nums[i].
3. Hit or storeIf need is in the map, return [map[need], i]; else store nums[i] → i.

Two Sum, one pass

def two_sum(nums, target):
    seen = {}
    for i, num in enumerate(nums):
        need = target - num
        if need in seen:
            return [seen[need], i]
        seen[num] = i

Coding lab. Two Sum in one pass runs in the app, with checks on your output.

7First non-repeating character

To find the first character that appears exactly once, count frequencies in a hash map on a first pass, then scan the string again in order and return the first character whose count is 1. Two linear passes beat comparing every pair in O(n^2).

Space is O(k) for alphabet size k (or O(n) in the worst case over arbitrary symbols). Order of first appearance comes from the second scan of the string — the map alone does not know which unique character appeared first.

Figure. "leetcode" after the frequency pass. Second scan returns the first letter whose count is 1 — here l — later uniques stay unused.

Count, then scan

1. Frequency passFor each character, increment its count in a hash map.
2. Order passWalk the string from the left; return the first character with count 1.
3. ComplexityO(n) time, O(k) space for alphabet size k.

8When hashing is the right hammer

Reach for a hash set or map when the bottleneck is "have I seen this key" or "what did I store under this key" and you can afford O(n) extra memory for average O(1) probes. Two Sum, anagram grouping, frequency counting, and graph visited-sets are the usual shapes.

Skip hashing when you need ordered traversal of keys, when worst-case O(1) is mandatory without a trusted hash, or when O(1) extra memory is required and a two-pointer or in-place pass exists. The structure is a trade: space and hash quality for speed.

Use the need → structure table: membership → hash set; key→value or count → hash map; unsorted pair sum → one-pass map; sorted pair sum with O(1) extra memory → two pointers instead.