Linear probing
Checks consecutive slots, wrapping around the table. It is simple, but primary clustering creates long, contiguous runs of occupied slots.
Chapter 15Lecture slides ↓
Hashing
A key gives you a starting address. What happens when another key lands there too? Build a hash table, follow its probes, and see how deletion and probabilistic membership change the rules.
Explore as you readUse Step to follow each insertion. Compare collision strategies with the same keys, then test a Bloom-filter false positive.
15.1Why hashing?
Go to an address instead of scanning every element.
A hash table maps a key to a bucket or slot. Hash-table operations take expected O(1) time when hashing distributes keys well and the load stays controlled, with resizing amortized over many insertions. A single operation can still cost O(n). Computing the hash of a string also depends on its length.
| Search structure | Typical guarantee |
|---|---|
| Unsorted array or linked list | O(n) worst-case search |
| Sorted array or balanced BST | O(log n) worst-case search |
| Hash table | Expected O(1), worst-case O(n) |
Find the repeated characters
Change the text and watch the counts update.
Compare every pair
For each character, scan again to check for duplicates: O(n²) time. With a fixed character alphabet, repeated output can be avoided without a growing set.
Count once
A frequency table counts each character in one pass. A fixed array costs O(n+Σ) time and O(Σ) space. This activity uses a map so Unicode characters work too.
ASCII, byte values, and input length
Standard ASCII has 128 codes. A byte-indexed frequency array has 256 counters and can handle values 0…255. The string length n can be any size; it is not fixed at 256. The activity counts Unicode code points, which can differ from user-perceived characters such as joined emoji.
15.2Direct addressing and memory waste
What if your next key is 100001?
Direct addressing stores key k at T[k]. For a small integer universe 0…100, a 101-slot array is convenient. With a few very large keys, most cells would sit empty.
Direct address for keys up to 13271,328slots, indexed 0…1327
Small hash-table example10slots, plus collision handling
Map a large key into a small table
Use h(k) = k mod 10. Try 1, then 11.
Key1327
h(k) = k mod 10
Slot7
A collision occurs when distinct keys have the same initial address. For example, h(1)=h(11)=1. The table must still distinguish those two keys.
15.3Hash functions
A fast calculation must also spread the keys.
Deterministic
The same key gives the same hash while it is stored.
Quick to compute
A good distribution must be worth its computation cost.
Well distributed
Avoid overloading a few buckets for the expected key patterns.
Try the folding method
Split a decimal key into two-digit groups, add, then reduce modulo 11.
Sum 218mod 11Slot 9
The load factor is α=n/m: stored keys divided by buckets or slots. A hash function works together with table capacity and the collision strategy.
Perfect hashing and unavoidable collisions
A perfect hash function has no collisions on a particular known key set. It need not be restricted to tiny sets, but constructing it is a different task from supporting arbitrary changing keys. If the possible key universe is larger than the table, a single mapping into its slots cannot be collision-free for every possible key.
15.4Collision resolution by chaining
Keep colliding keys in the same bucket.
Each bucket points to a chain of entries. Here 1, 11, 21, and 31 all map to bucket 1 in a ten-bucket table. The picture shows the completed chain. Use Step to rebuild it by inserting at the head.
A hash table with linked chains
Follow the keys through h(k)=k mod 10. All four reach bucket 1; ∅ marks a null pointer.
Read the pointer structure
Head insertion
O(1) if duplicate checking is unnecessary. A dictionary that must detect an existing key first searches the chain.
Find or delete
O(chain length). Expected O(1+α) with uniform distribution, worst-case O(n).
Space trade-off
Chains need link storage, but can hold more keys than there are buckets: α may exceed 1.
15.5Open addressing
Keep every entry in the table. Change the route after a collision.
A table with m slots can store at most m entries. Practical implementations resize before it fills because probes become expensive at high load. A search follows the same probe sequence used for insertion.
Compare the same colliding keys
Insert 1, 11, 21, 31 in a ten-slot table, or enter your own sequence.
Current key —Slot probes 0Load α 0.0
Quadratic probing
Uses a quadratic offset instead of a fixed step. Keys with the same initial hash follow the same sequence, causing secondary clustering. Choose c1, c2, and m carefully to obtain suitable probe coverage.
Double hashing
A second hash function chooses a key-dependent step size, h2(k), to reduce clustering. The step must be nonzero and coprime to the table size to visit every slot before repeating.
k is the key; m is the table size; i = 0, 1, …, m−1 is the probe number. The first probe uses i = 0.
Why this quadratic example can fail before the table is full
Here c₁=0, c₂=1, and m=10. Starting at slot 1, i=0…9 visits 1,2,5,0,7,6,7,0,5,2: only six distinct slots. The seventh colliding key cannot be inserted, even though other slots are empty. This is a limitation of these parameters, not of every quadratic-probing scheme.
The double-hash stride in this activity
The activity chooses h₂(k) from [1,3,7,9], using k mod 4 as the list index. All four strides are coprime to 10, so each sequence visits all ten slots before repeating. This is a small teaching function. Good production choices also need suitable distribution. Double hashing does not eliminate every collision and is not universally the fastest strategy.
15.6Deletion and tombstones
An empty slot can end a search. A deleted slot must not break its path.
Linear probing inserted 1, 11, 21, and 31 into slots 1, 2, 3, and 4. Delete 11, then search for 31 in the two versions below.
EMPTY versus DELETED
Follow both searches from the same starting slot.
Ordinary EMPTY
DELETED tombstone
EMPTY
This slot was never used since the last rebuild. A search can stop here.
DELETED
A key used to occupy this slot. A search continues; an insertion may reuse it.
OCCUPIED
Compare keys. If they differ, continue along the probe sequence.
Reusing tombstones safely
Remember the first tombstone, then continue probing to check whether the key already exists. Insert at the remembered tombstone only after confirming absence. Bound the search by the probe coverage. Tombstones accumulate, so rebuilding can shorten future searches. Some linear-probing implementations repair clusters instead of using tombstones.
15.7Bloom filters
A “no” can be certain even when a “yes” is only a possibility.
A standard Bloom filter stores a bit array and several hash functions. Insertion sets the key’s bit positions to 1. A query checks those same positions. It stores no original keys and can produce false positives.
Three hashes, sixteen bits
Add a word, test it, then try a known false positive.
Recorded insertions: NoneBits set: 0 / 16
Empty filter
No words have been added.
The small, deterministic hashes make shared bits easy to see. The recorded insertion list is shown only to verify the demonstration’s answers; the filter’s query uses the bits alone.
Some tested bit is 0
Definitely absent. With unchanged hash functions and no unsafe bit clearing, an inserted key cannot produce this result.
All tested bits are 1
Possibly present. Other inserted words may have set those same bits.
Why a standard Bloom filter cannot simply delete
Clearing a shared bit can make another inserted key appear absent, creating a false negative. Standard Bloom filters therefore do not support arbitrary deletion by clearing bits. Counting Bloom filters use counters instead. With appropriate hashes, more bits generally reduce false positives for a fixed number of insertions and hashes; a filling bit array makes positives less selective.
15.8Static and dynamic hashing
A larger table needs new addresses, not just extra empty cells.
When an in-memory hash table grows, its bucket mapping may change. Recompute the bucket for every stored key. The example below migrates a chained table from eight buckets to sixteen.
Resize and rehash
hold(k)=k mod 8; hnew(k)=k mod 16.
Old table · 8 buckets
New table · 16 buckets
| Feature | Static hashing | Dynamic hashing |
|---|---|---|
| Bucket organization | Fixed initial bucket set | Adapts as records change |
| Growth | May need overflow chains or a rebuild | May split buckets or expand the addressing structure |
| Database examples | Fixed bucket files | Extendible hashing and linear hashing |
The animation shows whole-table resizing in memory. Database dynamic hashing can grow through bucket splits instead: extendible hashing uses a directory, while linear hashing splits buckets gradually. The hash function’s code need not change; its modulus or the number of address bits used can change.