التصادمات وتغيير الحجم
في هذا الدرس 11 موضوعات
هذا الدرس متاح حاليًا باللغة الإنجليزية فقط، ولم تُنشر نسخته العربية بعد.
Lesson Overview
Last lesson ended with a loss: Khaled and Omar both belonged in mailbox 7, and the second one overwrote the first. In this lesson we fix that. There are two classic answers. With chaining, a mailbox holds a small list, so several keys can share it. With open addressing, the key that finds its box taken tries the next box along.
A second problem follows. As more keys arrive, the boxes fill up and the lists grow longer, and lookups slow down. The cure is to resize: build a bigger wall of mailboxes and move everything across. The number that tells the table when to do this is the load factor.
Why this matters: this is exactly what HashMap does when it "resizes", and it is why a good hashCode and a sensible initial size affect performance.
This lesson builds on the previous two lessons, on linked lists and the resizing of dynamic arrays (module BEG-040), and on Big O notation.
Learning Objectives
By the end of this lesson you will be able to:
- Define a collision and say why it cannot be avoided.
- Describe chaining and trace
putandgetin a chained table. - Describe open addressing with linear probing, and name the complication it brings for removal.
- Compute the load factor and the entry count at which a table resizes.
- Explain why resizing re-places every entry and why it keeps lookups fast.
- Explain why many collisions turn O(1) into O(n).
Written Explanation
Collisions again
A collision is two different keys mapping to the same bucket. Even a good hash function causes them, because there are more possible keys than buckets (and the index is a hash code squeezed into the range of the array). A table must therefore store both keys and still find each one.
Chaining
In chaining, each bucket holds a small linked list of entries, called a chain. The chain is made of nodes (key, value, next), the same linked-list idea from the data structures module.
put: find the bucket; walk its chain. If a node has anequalskey, replace its value. Otherwise add a new node.get: find the bucket; walk its chain comparing keys withequals; return the value of the match, or "not found" at the end of the chain.remove: find the bucket, then unlink the matching node, as in any linked list.
With short chains this is fast, because only the chain in one bucket is walked, never the others. java.util.HashMap uses chaining (lesson 4).
Open addressing
In open addressing, every entry lives inside the array itself, with no lists. If the bucket you want is taken, you probe for another one. The simplest rule, linear probing, tries the next bucket, then the next, wrapping around at the end.
put: start at the key's bucket and move forward until you find an empty slot or the same key.get: start at the key's bucket and move forward. Stop when you find the key (success) or hit an empty slot (the key is not here).
Open addressing avoids creating node objects, but removal needs care. If you empty a slot in the middle of a run of probed entries, a later get would stop at the empty slot and wrongly report "not found" for keys placed beyond it. Textbooks, such as the Open Data Structures book, solve this by leaving a special "deleted" marker (a tombstone) instead of an empty slot. Open addressing tables also have to be kept much emptier than chained ones: in that book's linear-probing table, occupancy is capped at 50%.
You will build chaining in the lab; open addressing is here so you can recognise the idea.
Load factor and resizing
The load factor is the number of entries divided by the number of buckets:
load factor = size / capacityA table with 12 entries in 16 buckets has a load factor of 12 / 16 = 0.75. The higher the load factor, the more likely a new key lands in an occupied bucket, and the longer chains become.
To keep chains short, a table chooses a maximum load factor, and when it is exceeded, resizes: it creates a new array with twice as many buckets, then takes every entry and places it again with the new capacity. Entries must be placed again, not just copied, because the index depends on the capacity (hash modulo the number of buckets). A key whose hash code is 13 sits in bucket 1 when there are 4 buckets, but its index becomes 5 when there are 8.
The Java documentation for HashMap says that when the number of entries exceeds the product of the load factor and the current capacity, the table is rehashed to roughly double the number of buckets, and the default load factor is 0.75. With the default capacity of 16, the first resize happens when the number of entries exceeds 16 * 0.75 = 12, so with the 13th entry.
Why resizing is worth its cost
One resize touches every entry, so it costs O(n). But a table doubles its size, so resizes become rarer as it grows. The Open Data Structures book shows that, over a sequence of m operations, total resizing work is O(m), so each put costs O(1) on average. This is the same amortized argument you saw for dynamic arrays in ArrayList.
What too many collisions cost
- Few collisions, short chains, and
getcosts O(1) on average. - Many collisions, long chains, and
getmust walk a long list. In the worst case all n keys share one bucket andgetcosts O(n), no better than a list.
Resizing fixes crowding that comes from filling the table. It cannot fix a bad hash function that sends every key to one bucket, because a larger array still gives all those keys the same index. Spread comes from the hash function; room comes from resizing. You need both.
Examples
Example 1: chaining by hand (simple)
A table has 4 buckets and uses index = hash % 4. Keys arrive with hash codes 5, 9, 2, and 13.
| Key hash | Index |
|---|---|
| 5 | 1 |
| 9 | 1 |
| 2 | 2 |
| 13 | 1 |
Bucket 1 holds a chain of three nodes (5, 9, 13). Bucket 2 holds one node. Buckets 0 and 3 are empty. A get for 13 goes to bucket 1 and walks past 5 and 9 before finding it. Here the load factor is 4 / 4 = 1, which is higher than the 0.75 limit, so a table would have resized earlier.
Example 2: a chained table in Java (practical)
static class Node {
final String key; int value; Node next;
Node(String key, int value, Node next) { this.key = key; this.value = value; this.next = next; }
}
static Node[] buckets = new Node[4];
static int size = 0;
static int indexFor(String key, int n) { return Math.floorMod(key.hashCode(), n); }
static void put(String key, int value) {
int i = indexFor(key, buckets.length);
for (Node n = buckets[i]; n != null; n = n.next) {
if (n.key.equals(key)) { n.value = value; return; }
}
buckets[i] = new Node(key, value, buckets[i]); // new node at the front of the chain
size++;
if (size > 0.75 * buckets.length) resize();
}
static Integer get(String key) {
for (Node n = buckets[indexFor(key, buckets.length)]; n != null; n = n.next)
if (n.key.equals(key)) return n.value;
return null;
}
static void resize() {
Node[] old = buckets;
buckets = new Node[old.length * 2];
for (Node head : old)
for (Node n = head; n != null; n = n.next) {
int i = indexFor(n.key, buckets.length);
buckets[i] = new Node(n.key, n.value, buckets[i]);
}
System.out.println("resized to " + buckets.length);
}Putting Ana, Omar, Sara, Lina, Khaled (value = name length) and then printing the buckets gave, with real output:
put Ana size=1 buckets=4
put Omar size=2 buckets=4
put Sara size=3 buckets=4
resized to 8
put Lina size=4 buckets=8
put Khaled size=5 buckets=8
[0] Lina
[1]
[2]
[3]
[4] Ana
[5] Sara
[6]
[7] Khaled Omar
6 4 nullWith 4 buckets the limit is 0.75 * 4 = 3, so the fourth entry (Lina) pushed the size above 3 and the table doubled to 8. Omar and Khaled share bucket 7 as a chain, and, unlike last lesson, both are found: get("Khaled") is 6, get("Omar") is 4, and a missing key gives null. The new node goes at the front of the chain, so Khaled is listed before Omar.
Example 3: a larger table stays shallow (realistic)
Insert 1,000 keys "user0" to "user999" into a chained table that starts at 16 buckets and doubles when size > 0.75 * capacity. Real output of that test:
size=1000 buckets=2048 resizes=7 longest chain=3 empty=1394Seven doublings took 16 up to 2,048 buckets; 1,024 buckets would only have allowed 768 entries (0.75 * 1024). The longest chain has just 3 nodes, even though there are 1,000 keys, and most buckets are empty. That is what "well spread plus resizing" looks like. A get walks at most three nodes. These counts depend on this exact key set and hash function; other keys give other numbers, but the picture is the same.
Backend Insight
Resizing is invisible but real. A single put that triggers a resize on a table with millions of entries takes much longer than the others, which can show up as a rare slow request. If you know roughly how many entries a map will hold, you can size it up front. The HashMap documentation notes that if the initial capacity is greater than the maximum number of entries divided by the load factor, no rehash ever occurs. (Since Java 19, HashMap.newHashMap(n) does this calculation for you.)
The trade-off behind the load factor is time against space: a lower limit gives shorter chains but more empty buckets (more memory); a higher one saves memory but slows lookups. The default of 0.75 is the JDK's compromise.
Common Mistakes
Mistake 1: Thinking resizing just copies entries over
Entries must be placed again with the new capacity, because the bucket index depends on the capacity. Copying each bucket to the same index in the larger array would make most keys unreachable.
Mistake 2: Saying a collision means data is lost
- Incorrect: "Two keys in one bucket means one is overwritten."
- Correct: "In a proper table both are kept, in a chain or in a nearby slot. Only a naive one-entry-per-bucket table loses data."
Mistake 3: Expecting resizing to cure a bad hashCode
If every key hashes to the same value, doubling the array changes nothing: all keys still land in one bucket. Resizing helps only when the hash function spreads keys.
Mistake 4: Forgetting equals while walking the chain
Matching on hash code alone is wrong, because different keys can share one. The walk must compare keys with equals.
Exercises
Try each exercise yourself before opening the solutions.
Level A: Foundation
A1. A table has 8 buckets and 5 entries. What is its load factor?
A2. A chained table with 4 buckets receives keys with hash codes 6, 10, 3, 14 and uses hash % 4. Draw the chains.
A3. In one sentence, what does a table do when its load factor passes the limit?
Level B: Application
B1. A table starts with 10 buckets and a maximum load factor of 0.75. At which entry does it resize, and to what capacity if it doubles?
B2. In the table of A2, the table doubles to 8 buckets. Where do the four keys go afterwards (using hash % 8)?
B3. An open-addressing table with 8 slots uses linear probing. Keys with home slots 2, 2, 3, 2 arrive in that order. Which slot does each key end up in?
Level C: Challenge
C1. A developer says: "Our map is slow, so I will make it bigger at the start." The keys are all instances of a class whose hashCode returns 42. Will it help? Explain.
C2. Why can you not simply set a slot back to empty when removing a key from an open-addressing table? Give a small example using B3's final state.
أظهر الحلول
A1. 5 / 8 = 0.625.
A2. 6 % 4 = 2, 10 % 4 = 2, 3 % 4 = 3, 14 % 4 = 2. Bucket 2 holds a chain of three nodes (6, 10, 14), bucket 3 holds 3, and buckets 0 and 1 are empty.
B1. The limit is 10 * 0.75 = 7.5, so it resizes when the entry count exceeds 7.5, which is the 8th entry. The new capacity is 20.
B2. 6 % 8 = 6, 10 % 8 = 2, 3 % 8 = 3, 14 % 8 = 6. Keys 6 and 14 still share bucket 6, but 10 has moved away from them, and the chain of three is now chains of two, one, and one. This is why the keys must be placed again.
B3. First key: slot 2. Second key: slot 2 is taken, so slot 3. Third key (home slot 3): slot 3 is taken, so slot 4. Fourth key (home slot 2): slots 2, 3, 4 are taken, so slot 5.
C1. No. Every key still has the same hash code, so every key lands in one bucket however large the array is. The map stays a long chain, O(n) per lookup. The fix is a proper hashCode.
C2. If you empty slot 3 (the second key), a get for the fourth key starts at slot 2, which is occupied by another key, continues to slot 3, finds it empty, and stops, reporting "not found" although the key sits in slot 5. That is why textbooks leave a deletion marker (tombstone) instead of emptying the slot.
Mini Challenge
Take the chained table of Example 2 and add a method longestChain() that walks every bucket and returns the length of the longest chain. Call it after inserting the keys "a0" to "a99", and print it together with the capacity. Then change the keys to ones you choose so that two or more land in one bucket, and describe how the result changes.
Check your work: the method visits every bucket and counts nodes using next; after 100 inserts the capacity is a doubled value from the starting 4 (the table resized more than once); and you can explain why the longest chain is small compared with 100.
Summary & Next Lesson
Key takeaways
- A collision is two different keys in one bucket; it is normal and must be handled.
- Chaining keeps a list in each bucket; open addressing probes for another slot inside the array.
- Load factor is entries divided by buckets. Past the limit (0.75 by default in Java), the table doubles its buckets and places every entry again.
- Short chains give O(1) on average; long chains give O(n).
- Resizing gives room, but only a well spread hash function gives short chains.
Next lesson
Next, "Inside HashMap and HashSet" connects this to the JDK classes: their default capacity and load factor, how HashSet builds on HashMap, and the rules for keys, including why you must not change a key after storing it.
Self-check
- What is a collision?
- How does chaining deal with a collision?
- What is the load factor of a table with 12 entries and 32 buckets?
- Why must a resize place entries again instead of copying them?
- Why does a constant
hashCodestay slow even in a huge table?
أظهر الإجابات
- Two different keys mapped to the same bucket.
- Each bucket holds a list of entries; both keys go in the chain, and a lookup compares keys with
equalsalong it. 12 / 32 = 0.375.- The index depends on the number of buckets, so the same key may belong in a different bucket after the table grows.
- Every key still gets the same index, so all keys sit in one chain regardless of the capacity.
References
- Oracle,
HashMap(Java SE 21). It gives the default capacity (16) and load factor (0.75), says the table is rehashed to roughly twice as many buckets when entries exceed load factor times capacity, and explains how a large enough initial capacity avoids rehashing. - Pat Morin, Open Data Structures, ChainedHashTable. It describes chaining and shows that doubling keeps the work of resizing amortized O(1) per operation.
- Pat Morin, Open Data Structures, LinearHashTable. It describes linear probing, the deleted-marker (tombstone) approach for removal, and the 50% occupancy cap used in that book's table.
- The code and numbers in Examples 2 and 3 were compiled and run on JDK 21. The mailbox analogy and the Backend Insight remarks on slow resizing requests are this course's own teaching additions.
التطبيق
طبّق هذا الدرس بمختبر الوحدة وتمارينها واختبارها.
تعليم الدرس كمكتمل اختياري ويمكنك التراجع عنه في أي وقت. يبقى تقدمك محفوظًا في هذا المتصفح.