عرض عملي: MyHashMap وبطء hashCode الثابت
في هذا الدرس 11 موضوعات
هذا الدرس متاح حاليًا باللغة الإنجليزية فقط، ولم تُنشر نسخته العربية بعد.
Lesson Overview
This is a build-and-break lesson. First you will build your own hash map, MyHashMap<K,V>, from the pieces of the last four lessons: an array of buckets, chains of nodes, an index that is never negative, and resizing at a load factor of 0.75. Then you will test it. Finally you will break its speed on purpose with a key class whose hashCode() always returns the same number, and measure the slowdown with real timings.
By the end you will have seen, with numbers and not just with words, why a bad hashCode turns O(1) into O(n). This lesson prepares the lab BEG-041-LAB1, where you write and time it yourself.
Why this matters: a hash map is the most-used data structure in backend code. Building one is the best way to stop treating it as a black box, and a measured slowdown is far more convincing than a rule you were told.
This lesson uses everything from the module, generics (BEG-031) for MyHashMap<K,V>, linked-list nodes (BEG-040), and Big O (BEG-039).
Learning Objectives
By the end of this lesson you will be able to:
- Build a chained hash map with
put,get,remove,size, and resizing. - Test it, including replacing an existing key and looking up a missing key.
- Write a key class with a constant
hashCodeand one with a goodhashCode. - Time the same workload with both and record the results.
- Explain from the timings why a constant
hashCodemakes lookups O(n). - Describe the limits of a simple timing experiment.
Written Explanation
The plan
We build in four steps, each one using a lesson from this module.
- Nodes and buckets.
Node<K,V>holds a key, a value, andnext. The table is an array ofNodereferences. (Lesson 3.) - The index.
(hash & 0x7fffffff) % lengthis always0or higher, even for negative hash codes and forInteger.MIN_VALUE. Anullkey gets hash 0. (Lesson 2.) put,get,remove. Each walks only the chain in one bucket, comparing keys withequals. (Lesson 3.)- Resizing. When
size > 0.75 * capacity, double the array and place every node again. (Lesson 3.)
Creating a generic array
Java does not let you write new Node<K,V>[16] (generic array creation is not allowed). The usual workaround is to create a raw Node[] and cast it, with @SuppressWarnings("unchecked") to silence the compiler warning. This is safe here because the array is private and only holds Node<K,V> objects.
The timing experiment
To see the effect of the hash function, we use the same map with two key classes that both have an int id:
GoodKey: a record, so itshashCodeis generated fromid.BadKey: a class withequalsonid, buthashCode()returning1.
For each key class we insert n keys, then look each one up, and measure the total time using System.nanoTime(). We run for several values of n, so that we can see how the time grows.
Predict first: with BadKey all n keys share one chain. The k-th put walks about k nodes (to check for an existing key), and the k-th get walks up to k nodes. The total is about n*²/2 steps for the inserts plus the same again for lookups: O(n²) overall, so doubling n should make the time about four times larger. With GoodKey the total should grow roughly in step with *n.
Reading timings with care
Timing in Java is noisy. The JIT compiler optimises code as it runs, other programs share the CPU, and a single run may not represent typical behavior. So: run a short warm-up first, repeat the measurement, record the numbers with your machine and JDK version, and compare trends, not exact values. A 100-fold gap, as you will see, is far outside the noise. A proper benchmark would use a dedicated tool; this experiment is enough to show a growth pattern.
Examples
Example 1: the MyHashMap class (simple)
public class MyHashMap<K, V> {
private static class Node<K, V> {
final K key;
V value;
Node<K, V> next;
Node(K key, V value, Node<K, V> next) { this.key = key; this.value = value; this.next = next; }
}
private static final double MAX_LOAD = 0.75;
private Node<K, V>[] buckets;
private int size;
@SuppressWarnings("unchecked")
public MyHashMap() { buckets = (Node<K, V>[]) new Node[16]; }
private static int indexFor(Object key, int length) {
int h = (key == null) ? 0 : key.hashCode();
return (h & 0x7fffffff) % length;
}
public V put(K key, V value) {
int i = indexFor(key, buckets.length);
for (Node<K, V> n = buckets[i]; n != null; n = n.next) {
if (java.util.Objects.equals(n.key, key)) {
V old = n.value;
n.value = value;
return old;
}
}
buckets[i] = new Node<>(key, value, buckets[i]);
size++;
if (size > MAX_LOAD * buckets.length) resize();
return null;
}
public V get(K key) {
for (Node<K, V> n = buckets[indexFor(key, buckets.length)]; n != null; n = n.next)
if (java.util.Objects.equals(n.key, key)) return n.value;
return null;
}
public V remove(K key) {
int i = indexFor(key, buckets.length);
Node<K, V> prev = null;
for (Node<K, V> n = buckets[i]; n != null; prev = n, n = n.next) {
if (java.util.Objects.equals(n.key, key)) {
if (prev == null) buckets[i] = n.next; else prev.next = n.next;
size--;
return n.value;
}
}
return null;
}
public int size() { return size; }
public int capacity() { return buckets.length; }
@SuppressWarnings("unchecked")
private void resize() {
Node<K, V>[] old = buckets;
buckets = (Node<K, V>[]) new Node[old.length * 2];
for (Node<K, V> head : old)
for (Node<K, V> n = head; n != null; n = n.next) {
int i = indexFor(n.key, buckets.length);
buckets[i] = new Node<>(n.key, n.value, buckets[i]);
}
}
}Points to notice. put and remove return the previous value (or null), as java.util.Map does. put on an existing key replaces the value and does not add a node, so size does not grow. remove unlinks a node with a prev pointer, exactly as in a linked list. resize creates new nodes, which is simple and correct; it is not the most memory-efficient way.
Example 2: tests (practical)
MyHashMap<String, Integer> m = new MyHashMap<>();
check(m.put("Ana", 1) == null, "first put returns null");
check(m.put("Ana", 2) == 1, "replace returns old");
check(m.size() == 1, "size after replace");
check(m.get("Zed") == null, "missing key");
for (int i = 0; i < 100; i++) m.put("k" + i, i);
check(m.size() == 101 && m.get("k57") == 57, "after resizes");
check(m.remove("k57") == 57 && m.get("k57") == null && m.size() == 100, "remove");
System.out.println("capacity " + m.capacity() + ", all tests passed");where check(boolean ok, String what) throws an AssertionError when ok is false. Real output:
capacity 256, all tests passedThe map held 101 entries at the end. Printing capacity() after each put showed doublings at entries 13, 25, 49, and 97 (limits 12, 24, 48, 96), so the final capacity is 256. The tests cover the lab cases: replacing an existing key, a missing key, resizing, and removal.
Example 3: the timing experiment and its results (realistic)
record GoodKey(int id) {}
static final class BadKey {
final int id;
BadKey(int id) { this.id = id; }
@Override public boolean equals(Object o) { return o instanceof BadKey b && id == b.id; }
@Override public int hashCode() { return 1; }
}
static long timeBad(int n) {
long t = System.nanoTime();
MyHashMap<BadKey, Integer> m = new MyHashMap<>();
for (int i = 0; i < n; i++) m.put(new BadKey(i), i);
long sum = 0;
for (int i = 0; i < n; i++) sum += m.get(new BadKey(i));
if (sum < 0) System.out.println(sum); // use the result so it is not optimised away
return (System.nanoTime() - t) / 1_000_000; // milliseconds
}timeGood is the same with GoodKey. After a warm-up call for each, two runs of the program on my machine (JDK 21, a laptop; yours will differ) printed:
5000 keys: good 2 ms, constant 102 ms
10000 keys: good 2 ms, constant 411 ms
20000 keys: good 2 ms, constant 1750 msand in the second run 1 / 97, 2 / 408, 2 / 1656. Read it as a growth pattern. With the good hashCode the time stays at a couple of milliseconds. With the constant one, each doubling of n multiplies the time by roughly four (102, 411, 1750), the O(n²) prediction. At 20,000 keys the constant version is hundreds of times slower, and it only gets worse.
One more measurement, from java.util.HashMap itself with 20,000 keys of a constant-hash class: about 9.9 seconds when the key class was not Comparable, and about 17 ms when the same key class implemented Comparable, which let the JDK's tree buckets (lesson 4) work. This was a single run; treat it as an illustration that tree buckets help only for comparable keys. In both cases, a good hashCode is the real fix.
Backend Insight
Constant or near-constant hash codes are not just theory. A key class whose hashCode uses only one small field, such as the status of an order, gives a few distinct values, so a huge number of keys share a few buckets. The service works with test data and becomes slow in production when the map holds millions of entries. Slowdowns that grow faster than the data are the typical signature.
Your measuring habit also transfers: when someone says "this map is slow", record sizes and times for two or three values of n. A time that grows with n per lookup points at collisions. Related security note: attackers can deliberately send many keys that collide to slow a server down, which is one reason the JDK added tree buckets. We only mention this to show that hash quality matters beyond speed tests.
Common Mistakes
Mistake 1: Timing without a warm-up or a repeat
The first run includes JIT compilation and class loading. Always do a short warm-up and run twice. Report the machine and JDK with your numbers.
Mistake 2: Using Math.abs(hash) % length
It breaks for Integer.MIN_VALUE, as lesson 2 showed. Use the mask h & 0x7fffffff or Math.floorMod.
Mistake 3: Replacing an existing key by adding a second node
Without the loop that checks for an equal key first, put("Ana", 2) adds a duplicate node, size grows, and get returns whichever node comes first. Check for the key before inserting.
Mistake 4: Forgetting to decrement size in remove
Then size drifts upward and the table resizes too early. Every size++ needs a matching size-- on removal.
Exercises
Try each exercise yourself before opening the solutions.
Level A: Foundation
A1. Why does indexFor use h & 0x7fffffff before %?
أظهر الحل A1
A1. A hash code can be negative, and % keeps the sign of the left operand, which would give a negative index. The mask clears the sign bit so the number is zero or higher, even for Integer.MIN_VALUE.
A2. MyHashMap has capacity 16 and holds 12 entries. A put of a new key arrives. What happens, and what is the capacity afterwards?
أظهر الحل A2
A2. With 12 entries and capacity 16, the limit is 0.75 * 16 = 12. The new key becomes entry 13, 13 > 12, so resize doubles the capacity to 32 and places every node again.
A3. What should be written down as "timing evidence" in the lab?
أظهر الحل A3
A3. The timings of both versions for the same workload (for example 20,000 inserts and 20,000 lookups), the machine and JDK, and a short statement that the constant version was slower and by how much. The tests should pass first.
Level B: Application
B1. get returns null both for a missing key and for a key stored with value null. Add containsKey(K key) that tells them apart.
أظهر الحل B1
B1.
private Node<K, V> find(K key) {
for (Node<K, V> n = buckets[indexFor(key, buckets.length)]; n != null; n = n.next)
if (java.util.Objects.equals(n.key, key)) return n;
return null;
}
public boolean containsKey(K key) { return find(key) != null; }After put("x", null), containsKey("x") is true while get("x") is null, and containsKey("y") is false (compiled and run).
B2. Add longestChain() that returns the length of the longest chain. What would you expect for 1,000 keys with a good hashCode, and for 1,000 BadKey objects?
أظهر الحل B2
B2.
public int longestChain() {
int longest = 0;
for (Node<K, V> head : buckets) {
int len = 0;
for (Node<K, V> n = head; n != null; n = n.next) len++;
longest = Math.max(longest, len);
}
return longest;
}For 1,001 string keys such as "user0" to "user999" (plus one extra key) it printed capacity 2048 and a longest chain of 3. For 1,000 BadKey objects the longest chain is 1,000, because all keys share bucket 1.
B3. Before running it, predict the time for 40,000 constant-hash keys given 1,750 ms for 20,000. Explain the reasoning.
أظهر الحل B3
B3. Doubling n multiplies the work by about four for O(n²), so about 7,000 ms (4 * 1750). Expect noise, but the ratio should be of that order.
Level C: Challenge
C1. Change MyHashMap so it never resizes (capacity stays 16), and time 20,000 inserts and lookups with GoodKey. Explain the result with a sentence about chain length.
أظهر الحل C1
C1. With 16 buckets and 20,000 entries the chains hold about 1,250 nodes each, so lookups walk long chains even though the hash function is good: the good hash code cannot help a table that never grows. Two runs on my machine gave about 215 to 225 ms, against 2 ms with resizing. Spread and room are both needed.
C2. Replace BadKey's hashCode with return id % 10;. Predict how the timing compares with the constant version and with the good one, then check.
أظهر الحل C2
C2. With id % 10 there are only ten distinct hash codes, so ten chains of roughly n/10 nodes: far fewer steps than the constant version, yet still O(n) per lookup, and much slower than the good version. Three timed runs on my machine (20,000 keys, with resizing) gave about 300 ms, against about 1,700 ms for the constant hash and 2 ms for the good one. A "partly bad" hash function like this is common in real code.
Mini Challenge
Write the lab report skeleton in a text file: (1) the test list, with a pass or fail mark for each; (2) a small table with n (5,000, 10,000, 20,000), the time with a good hashCode, and the time with a constant hashCode; (3) three sentences explaining the pattern in terms of chain length and Big O. Run your program twice and put the second run's numbers next to the first.
Check your work: the table has both columns for all three values of n; the constant column roughly quadruples when n doubles; and your explanation mentions that all keys share one chain, so each lookup walks it.
Summary & Next Lesson
Key takeaways
- A chained hash map is an array of buckets, a node class for chains, an always-non-negative index, and resizing at a load factor.
putreplaces an existing key;getandremovewalk only one chain withequals.- A constant
hashCodeputs every key in one chain, so the total work for n inserts and lookups grows as n*², and doubling *n roughly quadruples the time. - Timing is noisy: warm up, repeat, and compare trends.
- Good spread plus resizing is what makes hash maps fast.
Next lesson
This is the last lesson of module BEG-041, Hashing. Finish the lab BEG-041-LAB1: build your own MyHashMap, test it, and record the timing evidence. The module quiz and exercises then check the whole module.
Self-check
- Why does a constant
hashCodemake a hash map slow? - What does
putdo when the key already exists? - When does
MyHashMapresize, and what happens to the existing nodes? - If the time for 10,000 constant-hash keys is 400 ms, about what do you expect for 20,000?
- Name two things you do to make a timing experiment more trustworthy.
أظهر الإجابات
- Every key goes into one bucket, so a lookup must walk one long chain: O(n).
- It replaces the value in the existing node, returns the old value, and does not change the size.
- When
size > 0.75 * capacity. The array doubles and every node is placed again with the new capacity. - About four times as much, roughly 1,600 ms, because the total work grows as *n*².
- Run a warm-up first and repeat the measurement; also record the machine and JDK, and compare trends, not single numbers.
References
- Oracle,
HashMap(Java SE 21). It supports the default load factor of 0.75, the doubling on rehash, constant-time performance only when hashes disperse well, and the warning that many keys with the samehashCode()slow any hash table. - Oracle,
Math(Java SE 21). It supports the claim thatMath.abs(Integer.MIN_VALUE)stays negative. - OpenJDK, JEP 180. It describes the tree buckets that improve high-collision cases for
Comparablekeys, in Java 8. - All code, test output, and timings above were compiled and run on JDK 21 on one laptop. The timings are my own measurements from two runs and one run of the JDK comparison, and are illustrations of a growth pattern, not benchmarks. The attacker remark in Backend Insight is general knowledge that I did not check against a specific source here.
التطبيق
طبّق هذا الدرس بمختبر الوحدة وتمارينها واختبارها.
تعليم الدرس كمكتمل اختياري ويمكنك التراجع عنه في أي وقت. يبقى تقدمك محفوظًا في هذا المتصفح.