From a dictionary query to a storage choice
A dictionary associates each key with one value. In an unsorted list, finding a key may require checking every entry. Sorting an array permits binary search, but inserting a new key while preserving order may shift many entries. Direct array indexing avoids that search only when the keys themselves fit a suitable integer range; arbitrary strings do not supply such indices.
A hash table computes an index from the key and searches only the candidates assigned to that location. It gives up sorted order to reduce the expected work of lookup and update. The index cannot uniquely identify every possible key, so the representation must preserve distinct entries even when they collide.
The dictionary contract
Definition 1.2.1
(Dictionary semantics of the table)
A hash table is a dictionary structure. For one key, the table should support insertion, lookup, and deletion. If the same key is inserted again, the newer value replaces the older association instead of creating a second copy of the key.
Worked example 1.2.2
(Enter updates an existing key)
Suppose a table already stores:
"cat" -> 3"dog" -> 8
If Enter(table, "cat", 9) is called again, the intended result is not two
copies of "cat". The association for "cat" is updated, so a later
Lookup(table, "cat") returns 9.
Enter therefore inserts a value for a specified key and overwrites the old
value if that key already exists.
Values behind opaque pointers
The following C interface uses void * values to keep the ADT independent of
the concrete value type.
typedef struct hashtableCDT *hashtableADT;
hashtableADT EmptyHashtable();
void Enter(hashtableADT table, char *key, void *value);
void *Lookup(hashtableADT table, char *key);
The table does not need to know the concrete value type. It only stores the association between a key and an opaque pointer to some client-owned data.
That makes the same hashtable ADT usable for many different applications, as long as the client also knows how to interpret the returned pointer correctly.
What a hash function is supposed to do
Definition 1.2.3
(Hash function)
A hash function maps a key into an integer index in a fixed range, usually
[0, H_SIZE).
A good hash function should have four properties:
- it must always return a legal bucket index,
- it should reduce collisions,
- it should distribute keys reasonably evenly,
- it should be quick to compute.
The last point matters because a beautifully distributed hash rule is not very useful if every lookup spends too long computing the bucket index itself.
Worked example 1.2.4
(A simple string hash idea)
For a string key, one very simple rule is:
int Hash(char *s, int nBuckets) {
int h = 0;
while (*s != '\0') {
h += *s;
s++;
}
return h % nBuckets;
}
This kind of rule is easy to compute, but it is also easy to fool. Strings whose
character sums are equal, or merely congruent modulo nBuckets, collide;
anagrams are an immediate example. The fragment also assumes nBuckets > 0,
nonnegative input characters such as ASCII bytes, and a sum that fits in int.
Those assumptions make it useful for tracing the calculation, but a production hash
table would use a carefully defined unsigned hash state and a stronger mixing
rule.
Test a simple hash-and-bucket model
Insert the keys one at a time. Each key goes to bucket (sum of its character codes) mod 7; watch whether two keys ever share a bucket.
- insert("cat");
- insert("dog");
- insert("cow");
- insert("cod");
| Bucket index | Keys | Count |
|---|---|---|
| 0 | empty | 0 |
| 1 | empty | 0 |
| 2 | empty | 0 |
| 3 | empty | 0 |
| 4 | empty | 0 |
| 5 | empty | 0 |
| 6 | empty | 0 |
Nothing has been inserted yet.
- This instruction
- —
- Hash
- —
- Occupied buckets
- 0 of 7
- Collision count
- 0
Open: every inserted key is alone in its bucket
Nothing has been inserted yet; all 7 buckets are empty.
NoticeCollision count adds up, for every bucket, the keys beyond its first one: three keys in one bucket count as 2 collisions, not 3 pairs. This simplified hash sums the first UTF-16 code unit of each character.
Why different keys can share a bucket
Definition 1.2.5
(Collision)
A collision occurs when two different keys map to the same bucket index.
If the key domain contains more keys than the table has buckets, at least two possible keys must share an index. This does not mean every small input already contains a collision; it means no hash function into that range can rule out collisions for all legal inputs. Hashing identifies candidates. Comparing keys still determines whether one of those candidates is the requested entry.
Chaining stores colliding entries in a list attached to the bucket. Open addressing keeps them in other slots of the same table and uses a reproducible probe sequence to find them. In both cases the search must recover the entry with the matching key rather than merely accept the first occupied location.
Watch how a hash table keeps dictionary operations correct when two different keys collide.
Hashing is only the first step. Correct lookup and update still depend on the collision strategy checking keys along the chain or probe sequence.
Chaining keeps colliding keys in one bucket list
Chaining handles a collision by retaining the entries in a bucket-side list.
Definition 1.2.6
(Chaining)
With chaining, each bucket stores a linked list of all entries whose keys hash to that bucket.
A bucket chain uses the same pointer-linked nodes as other linked structures:
typedef struct cellT {
char *key;
void *value;
struct cellT *next;
} cellT;
Each bucket head points to the first node in its chain. Lookup therefore has two layers:
- hash the key to choose a bucket,
- scan only that bucket’s chain instead of the whole table.
Worked example 1.2.7
(What lookup does under chaining)
Suppose Hash("cat") = 3, and bucket 3 stores the chain
("cow", value1) -> ("cat", value2) -> ("cod", value3).
To execute Lookup(table, "cat"), the implementation:
- computes bucket
3, - moves along the linked list in bucket
3, - compares keys until
"cat"is found, - returns
value2.
The collision does not destroy correctness. It only makes that one bucket take longer to search.
The order within a bucket is not part of the dictionary contract. An implementation may insert at the front, at the back, or in another consistent order, provided lookup and overwrite still identify the correct key. That freedom concerns representation, not the meaning of an association.
Worked example 1.2.8
(Insertion and lookup under chaining)
Consider a table with five buckets and a simple hash rule.
- Insert
"ape". - Insert
"ant". - Insert
"apple". - Look up
"ant".
If "ape" and "ant" collide, they will appear in the same bucket chain. The
lookup for "ant" hashes once, follows only that chain, and compares keys until
it finds the exact entry.
This is why chaining can still stay fast on average when the buckets remain reasonably balanced.
Occupancy and expected search cost
Even a good hash function degrades if the table is too full.
For n stored entries and m buckets, the load factor is usually written as
For chaining, n may exceed m, so may exceed 1. For open
addressing, each slot contains at most one live entry, so ;
inserting a new key requires and a probe sequence that can actually
reach an empty slot.
Theorem 1.2.9
(Counting identity for separate chaining)
Let be the length of the chain stored at bucket , for . Then
Under separate chaining, the bucket chains partition the n stored entries:
every entry belongs to exactly one chain. Summing all chain lengths therefore
counts every entry once and gives ; dividing by m gives the
average occupancy .
This is a deterministic counting identity, not by itself a constant-time lookup guarantee. An expected bound such as additionally needs a suitable hash-function or key-distribution assumption. Without that assumption, even a small load factor can coexist with one long chain.
As the table becomes more heavily loaded:
- the exact average chain occupancy is , although individual chain lengths depend on how keys are distributed;
- open-addressing probe sequences tend to become longer as approaches
1, and probe-coverage conditions still matter; - average-case lookup moves away from the ideal constant-time picture unless the distribution and load remain controlled.
So resizing is not just a practical optimization. It is part of protecting the performance model promised by the data structure.
Open addressing keeps the search inside the table
Instead of attaching a list to each bucket, open addressing keeps searching for another slot inside the table itself.
The cost of a collision therefore moves into the probing rule.
- linear probing checks the next slot, then the next, and so on;
- quadratic probing jumps by square offsets;
- double hashing uses a second hash function to generate a step size.
Definition 1.2.10
(Linear probing)
With linear probing, if the preferred slot is full, the table checks the next slot in sequence and wraps around when necessary.
Linear probing tends to create long runs of filled buckets. That effect is called primary clustering, and it degrades the performance of the table because future probes are more likely to collide with the same dense region.
Quadratic probing is one response to that problem.
Definition 1.2.11
(Quadratic probing)
With quadratic probing, the ith probe uses a square offset such as i^2.
The step size grows faster than in linear probing, which helps reduce primary
clustering.
Worked example 1.2.12
(Quadratic probing with a small table)
Start with an empty table of size 10 and hash rule h(k) = k % 10. Insert
89, 18, 49, 58, 69 in that order, using the quadratic probes
for .
The probe sequence works as follows:
89goes to bucket918goes to bucket849hashes to9, collides, then probes bucket058hashes to8, collides, then probes9, then269hashes to9, collides, then probes0, then3
So the occupied buckets end up as:
0 -> 492 -> 583 -> 698 -> 189 -> 89
The final location is determined by both the initial hash and the occupied positions encountered by the probe sequence.
Common mistake
(Quadratic probes need not visit every slot)
Reducing primary clustering does not guarantee complete probe coverage. For example, with Nbuckets = 7 and F(i) = i^2, the probe
sequence repeats before reaching all
slots. Some buckets may never be visited under a given probe rule.
Worked example 1.2.13
(Why the probe sequence can miss slots)
For Nbuckets = 7, h0 = 0, and probes (h0 + i^2) % 7, taking
i = 0, 1, ..., 6 gives the sequence
0, 1, 4, 2, 2, 4, 1
Only four distinct slots are reached. If they are occupied, this probe cannot find a vacancy in any of the other three slots, even though the table is not full. Load factor and probe coverage are therefore separate conditions.
Definition 1.2.14
(Double hashing)
For a table of size , double hashing uses a second hash function to choose a step and probes
The probe sequence is guaranteed to cover all slots only when . Requiring only a nonzero step, or merely , is not sufficient.
For a table of size 10 with h(k) = k % 10 and second hash
, key 23 has step . Starting at bucket 3, the probes alternate
between 3 and 8 because ; if both are occupied, the search
cycles without reaching other empty slots. A well-chosen second hash can spread
probes better, but the table size and step rule must be designed together.
Deletion has a further obligation: it must preserve the search path for entries placed later in the same probe sequence. Simply marking a removed slot as unused can break that path. The probe examples here concern insertion and lookup; they do not specify a deletion implementation.
Changing the bucket count requires rehashing
The bucket count participates in the index rule. Even if the underlying hash code stays the same, changing that count can assign an existing entry to a new bucket. Every entry must therefore be placed again according to the new rule; this is rehashing.
Worked example 1.2.15
(A changed modulus changes the bucket)
With h(k) = k % m, key 18 belongs to bucket 8 when m = 10, but bucket
18 when m = 20. Copying the old cells into a larger array would leave that
entry outside the bucket where a new lookup expects it. Rehashing recomputes
the placement; for open addressing it must also rebuild the probe placement.
How to choose between chaining and probing
No collision strategy is universally best. The useful comparison is the set of tradeoffs each strategy makes visible.
- Chaining is easier to explain and naturally handles collisions with a linked list.
- Linear probing keeps the table compact but can form primary clustering.
- Quadratic probing reduces that clustering but needs stricter load-factor control.
- Double hashing usually distributes probes better, but it is more expensive because it depends on two hash functions.
The choice depends on table size, expected load, memory layout, and the operations being performed. A probe rule must satisfy its coverage condition before its speed becomes relevant.
Common mistakes
Common mistake
(A collision does not mean two keys are equal)
If Hash(key1) == Hash(key2), that only means the keys land in the same bucket.
It does not mean the keys are identical.
Common mistake
(A valid hash range is necessary but not sufficient)
A hash function that always returns a legal bucket index can still be bad if it clusters many unrelated keys into the same few buckets.
Common mistake
(Average-case speed depends on keeping the table healthy)
Saying “hash table lookup is O(1)” silently assumes a reasonable hash function and a controlled load factor. It is not a license to ignore collisions.
Summary
The dictionary contract fixes the association for each key; the representation chooses where that association is stored. Hashing selects candidates, key comparison identifies the entry, and collision handling keeps every stored key reachable. Expected speed depends on both the key/hash model and occupancy. Changing the table size requires rehashing because placement and lookup must continue to use the same rule.
Quick checks
Quick check
(What is a collision in hashing?)
Answer in terms of keys and bucket indices.
Solution · Answer
A collision happens when two different keys are mapped to the same bucket index.
Quick check
(Under chaining, what extra work happens after computing the bucket index?)
Focus on where the implementation looks next.
Solution · Answer
It scans the linked list stored in that bucket until it finds the matching key or reaches the end of the chain.
Exercises
Quick check
(Why does a hashtable still need key comparison after hashing?)
Use collision reasoning, not only a slogan about speed.
Solution · Guided solution
Hashing only narrows the search to a bucket. Because different keys may collide into the same bucket, the implementation must still compare stored keys to the target key to confirm it found the correct entry.
Quick check
(Explain one tradeoff between chaining and open addressing.)
Answer in terms of where the collision-handling work is stored.
Solution · Guided solution
Chaining stores colliding entries in an auxiliary linked structure attached to the bucket, while open addressing keeps probing alternative slots inside the main table. Chaining uses extra pointer structure; open addressing relies more heavily on table occupancy and probe design.
Quick check
(Why does Enter need to overwrite an old value when the key already exists?)
Answer from the dictionary contract, not from the code alone.
Solution · Guided solution
The ADT is a dictionary keyed by unique keys. If the same key is inserted again, the stored association should be updated. Otherwise the table would no longer have a single well-defined value for that key.
Quick check
(What clustering problem does quadratic probing reduce compared with linear probing?)
Name the clustering effect.
Solution · Answer
Quadratic probing reduces primary clustering, which is the tendency of linear probing to build long contiguous runs of filled buckets.
Quick check
(Start with an empty table of size 10. Insert 89, 18, 49, 58, 69 in that order, using probes for . In which buckets do 49 and 69 land?)
Use the probe sequence, not just the raw hash values.
Solution · Guided solution
49 hashes to 9, collides, and then lands in bucket 0. 69 hashes to
9, collides, then probes 0, then lands in bucket 3.
Quick check
(How can double hashing improve probe distribution, and what extra computation does it require?)
Focus on what extra ingredient it needs.
Solution · Guided solution
Double hashing can spread probe paths more evenly, but it needs a second hash computation and a step coprime to the table size. The extra hash computation is part of its cost.