Lab 07 A Map Built on a Hash Table
The goal of this lab period is to build a hash map (also called a hash table).
In Lab 06 you built a map on a binary search tree: to find a key, get compared its way down the tree, left or right, one level at a time. This week you build the same map, with the same MapSet methods, but the structure of the data is very different. Instead of keeping the keys sorted and comparing them, a hash map calculates exactly where each key goes, and uses that calculation to put and get it in O(1) time, on average, under some "nice" assumptions. Lecture motivated this with the hash table concept: a hash function maps each key to a position, so the key leads to its position in constant time (L25, slides 20–27). Your Python dictionary works this way; it is a hash table too.
| BSTMap (Lab 06) | HashMap (this lab) | |
|---|---|---|
| Where a key goes | compare with compareTo, go left or right, level by level | turn the key into a bin number with hashCode, go straight there |
| Inside one spot | one node | a chain: a linked list of every key that landed in that bin |
| What keys must have | compareTo (that's the K extends Comparable<K>) | hashCode and equals, which every Java object has |
Order of keySet() | sorted | bin by bin, which looks random |
maxDepth(): the most nodes get may look at | the number of levels | the number of items in the biggest bin |
As in Lab 06, the keys are always words (String) and the values are always whole numbers (Integer): a HashMap<String, Integer>. In Project 07, you will count the words of Shakespeare and Reddit with both of your maps, and compare how fast each map is at building the counts and at using them.
- Build (Tasks 1–5): Hash a key to a bin, put keys and their values into chains, grow the table when it gets too full, and look up a key's value with get.
- Finish the map (Tasks 6–7): containsKey, keySet, values, maxDepth, and remove. When removes drop the load factor below a quarter of the maximum, remove halves the table.
- Apply in Project 07: Time your BSTMap and your HashMap on Shakespeare and Reddit, for building the map and for using it, and explain the differences.
Setup
Create Projects/Project07 in your personal Google Drive folder and download the three files below into it. MapSet.java is the same interface as in Lab 06. HashMap.java is the class you will complete. It already has the Node class, the fields, the constructors, makeTable, capacity, toString, and a placeholder for every method. You will download three more files later: HashDemo.java in Task 4, and tiny.txt and sorted.txt in Task 6.
Download now:
The three programs you will run
Open a Terminal and cd into your Project07 folder, as in Lab 06. Every command on this page is typed there. Always compile first with javac *.java: it compiles every file in the folder. Each time you need to run something, a blue Run it box shows what to type and what you should see.
| Command | What it runs | When |
|---|---|---|
java Lab07Tester | The tester: checks your HashMap, one section per task | At the end of every task, starting with Task 1 |
java HashMap | Your own tests: the main method in HashMap.java. There is no main until you paste one in during Task 2; before that, Java says Main method not found. | From Task 2 on, after each change |
java HashDemojava HashDemo tiny.txt | The demo: shows your map at work, step by step. Not graded. | Tasks 4 and 6 |
Keep the field names in HashMap.java (nodes and size, and key, value, next in Node). The tester looks inside your table through those names.
A hash map can look correct on small tests and still be broken. With a few keys in many bins, no two keys share a bin and the table never grows, so a bug in chaining or in resize never shows. So don't just run your code and trust what prints: first work out on paper what should happen, then check it against what your program prints. Include tests where two keys share a bin (like "Aa" and "BB") and where the table has to grow.
- Draw it. Before each put, draw the table as a column of numbered bins and decide which bin the key goes in.
- Predict the result of each test before you run it. The "expected X, got Y" lines only help if you decided X yourself.
- Implement one method at a time.
- Run your own small tests in
main, and print the table:System.out.print(map)shows every bin. - Run the tester after each task. The lab checkpoint comes at the end of Task 5. A method you haven't written yet shows as SKIP, not as a crash, so you can see your progress.
Task 1 — Meet HashMap READ
This lab builds a HashMap that uses separate chaining and Java's built-in hashCode method to decide where to put each key. Here is a table with 8 bins holding four of the words from Lab 06: dog, bee, eel, ant. This is exactly what System.out.print(map) prints:
bin 0: bin 1: bin 2: <bee -> 8> | bin 3: bin 4: <eel -> 16> | <dog -> 15> | bin 5: bin 6: bin 7: <ant -> 3> |
The table is an array of 8 bins. Each bin holds the first Node of a chain, a singly linked list, or null if the bin is empty. Bin 4 holds two words, because "eel" and "dog" got the same bin number. Two keys in one bin is a collision, and chaining handles it by linking them in a list (lecture: L25, slides 42–52). The first node in each bin is a real entry, with a key and a value: there is no empty "dummy" node at the front of a chain. Open HashMap.java and find each part:
| In HashMap.java | What it is |
|---|---|
private class Node: K key; V value; Node next; | one entry of a chain. Like Lab 06's Node it holds a key and a value, but instead of left and right it has a single next, like your LinkedList's Node. Its toString prints <key -> value> |
Node[] nodes; | the bins: nodes[i] is the first node of bin i's chain. Your LinkedList had one head; this has one head per bin |
int size; | the number of keys in the map |
double maxLoadFactor; | how full the table may get before it grows (Task 4) |
int initialCapacity; | the number of bins the map started with (Tasks 3 and 7) |
HashMap() | calls the next constructor with a starting capacity of 16, as Java does |
HashMap(int capacity) | calls the next constructor with a load factor of 0.75, as Java does |
HashMap(int capacity, double loadFactor) | makes the table with the given capacity and stores the load factor |
makeTable(capacity) | makes an array of empty bins (provided: use it as it is) |
capacity() | the length of the array. This is not the number of items stored in it: there can, and should, be many empty bins |
toString() | prints every bin and its chain (provided) |
The methods you write. Each one starts as a placeholder in HashMap.java:
| Method | What it does | Task |
|---|---|---|
private int hash(K key) | the bin where key belongs: its hashCode, brought into the range 0 to capacity() - 1 | 2 |
private Node find(K key) | a helper: the node holding key, or null | 3 |
put(K key, V value) | stores the value under the key; returns the old value, or null | 3 |
size(), clear() | the number of keys; empty the map | 3 |
private void resize(int newCapacity) | a helper: moves every key into a table with newCapacity bins | 4 |
get(K key) | the value stored under key, or null | 5 |
containsKey, keySet, values, maxDepth | is the key there; every key; every value; the size of the biggest bin | 6 |
remove(K key) | removes the key, returns its value, and shrinks the table if it gets too empty | 7 |
public class HashMap<K, V> implements MapSet<K, V>
Compare it with Lab 06's BSTMap<K extends Comparable<K>, V>. The extends Comparable part is gone: a hash map never asks which of two keys is smaller. It only asks two questions, and every Java object can answer both: "what is your hashCode?" (Task 2) and "are you equal to this other key?" (equals, Task 3).
makeTable exists because Java won't let this class write new Node[capacity], for a technical reason about generic types. The line inside it does the same thing. You don't need to understand it; just call makeTable whenever you need a new table.
java.util.HashMap. Because your HashMap.java is in the same folder, HashMap means yours, as long as no file in the folder says import java.util.HashMap;. Don't add that line.As in Lab 06, every method you write starts with a throw placeholder line. Delete that line when you write the method. Run the tester now, before you change anything:
Type:
$ javac *.java $ java Lab07Tester
You should see: the Task 1 section passes, every later section says SKIP, and the last lines are the summary:
== Task 1: the provided HashMap == Checks that the tester can look inside your table. [PASS] new HashMap() starts with 16 bins ... == Task 2: hash == Calls your hash(key) and checks it picks a bin from 0 to capacity() - 1. [SKIP] hash is not written yet (Task 2); the rest of this section waits until you write it ... Summary: 4 passed, 0 failed, 6 skipped.
If not: check that you are in your Project07 folder (ls should list HashMap.java and Lab07Tester.java), and that you didn't change HashMap.java yet.
node.key or node.value before checking whether node is null. If a section runs for more than 10 seconds, the tester reports a likely infinite loop (often a missing node = node.next;) and stops. The full list of what each section checks is in The tester, after Task 7.Task 2 — Implement hash: from a key to a bin READ AND EXPERIMENT
hash(K key). Given a key, it returns the index of the bin where that key belongs: a number from 0 to capacity() - 1. It works in two steps:
- Ask the key for its hashCode:
key.hashCode(), a whole number computed from the key. For our String keys, this is Java's built-in String hashCode. You don't write it; you call it. - Turn that number into a bin number with
% capacity(), and make sure it isn't negative.
2a explains where hashCode comes from and lets you look at some; 2b explains the % step and gives you the line to write.
2a. Experiment: what does hashCode look like?
Lecture introduced Java's hashCode on L25, slides 68–69.
Every Java class inherits a few methods from Java's base class, Object, whether you write them or not. You know one already: toString. The inherited toString prints something like HashMap$Node@1b6d3586, which is why classes such as our Node override it with their own version that prints something meaningful.
hashCode() is inherited the same way. Object's version gives each object its own number, so two separate String objects holding "dog" would get different numbers. That would be useless for a map: get("dog") must find the "dog" that put stored, even when the two calls use different String objects.
So the String class overrides hashCode(): it computes the number from the letters of the word, and the same letters always give the same number. String also overrides equals to compare letters, not objects. A map relies on both: hash uses hashCode to choose the bin, and find uses equals to pick the right key in that bin's chain.
You won't override hashCode in this lab: your keys are Strings, and hash calls String's version. If you ever use a class of your own as a key, it must override both hashCode and equals, so that equal keys get equal hashCodes.
Copy and paste: paste this method at the end of HashMap.java, just before the class's last closing brace }. It is your HashMap's own main method, so from now on java HashMap runs it.
// Task 2: Paste this method at the end of HashMap.java, before the class's last }.
public static void main(String[] args) {
System.out.println("dog " + "dog".hashCode());
System.out.println("bee " + "bee".hashCode());
System.out.println("dog, as a different String object: " + new String("dog").hashCode());
System.out.println("Aa " + "Aa".hashCode());
System.out.println("BB " + "BB".hashCode());
System.out.println("abroad " + "abroad".hashCode());
// TODO: Print the hashCode of your own name. Run it twice: does it change?
}
Type:
$ javac *.java $ java HashMap
You should see: each word and its hashCode, then your name's:
dog 99644 bee 97410 dog, as a different String object: 99644 Aa 2112 BB 2112 abroad -1423928639
If not: Main method not found means the method isn't inside the class: it must go before the class's last }, not after it.
What to notice:
- dog and bee: a hashCode is a big number, far bigger than the number of bins. Step 2 has to bring it into range.
- dog as a different String object: the same word gives the same number, because String overrides hashCode. That is why get can find what put stored.
- Aa and BB: two different words can have exactly the same hashCode. So even a perfect table needs chains, and find needs
equalsto tell the keys apart. Equal hashCodes like this are rare among real words; most keys that end up in the same bin, like dog and eel in Task 1, have different hashCodes that give the same bin number in step 2. - abroad: a hashCode can be negative. Step 2 has to deal with that.
- Your name, run twice: the number doesn't change. A hash function must give the same answer every time, or put and get would look in different bins.
2b. Implement hash: % capacity()
The % operator gives the remainder after division. 99644 ÷ 8 is 12455 with 4 left over, so 99644 % 8 is 4. Whatever the number, a remainder after dividing by 8 is always one of 0, 1, 2, …, 7: exactly the bin numbers of a table with 8 bins. Think of dealing cards into 8 piles: every card lands in some pile, and the piles are numbered 0 to 7. So key.hashCode() % capacity() always gives a bin number, whatever the hashCode is, and it uses every bin.
| Key | hashCode | % 4 | % 8 | % 16 |
|---|---|---|---|---|
| dog | 99644 | 0 | 4 | 12 |
| bee | 97410 | 2 | 2 | 2 |
| eel | 100300 | 0 | 4 | 12 |
The bin depends on the capacity: dog is in bin 0 of a 4-bin table but bin 12 of a 16-bin table. Task 4 comes back to this when the table grows.
The minus sign. In Java, % keeps the sign of the number being divided: "abroad" has hashCode -1423928639, and -1423928639 % 16 is -15. There is no bin -15: nodes[-15] crashes with an ArrayIndexOutOfBoundsException. Math.abs (absolute value) turns -15 into 15.
Put the two steps together. Write hash with exactly this line, the remainder first and then Math.abs:
private int hash(K key) {
return Math.abs(key.hashCode() % capacity());
}
Ask Yourself — what makes a good hash?
- With 4 bins, which bin does "bee" (97410) go in? With 8 bins? Check your answers against the table above.
- Why must the same word always give the same hashCode? What would go wrong in get if a word's hashCode changed each time you asked?
- "Aa" and "BB" have the same hashCode. Can two words in the same bin still be told apart? How?
Leave your main method in place; later tasks add to it. When hash is written:
Type:
$ javac *.java $ java Lab07Tester
You should see: the Task 1 and Task 2 sections pass; Tasks 3 to 7 still say SKIP.
== Task 2: hash == Calls your hash(key) and checks it picks a bin from 0 to capacity() - 1. [PASS] "dog".hashCode() is 99644, and 99644 % 4 is 0, so with 4 bins dog goes in bin 0 ... == Task 3: find, put, size, clear == [SKIP] put is not written yet (Task 3); the rest of this section waits until you write it
If not: a negative bin number means Math.abs is missing or is in the wrong place: write the line exactly as above.
Task 3 — find, put, size, and clear REUSE
Every operation starts the same way: hash the key to pick one bin, then walk only that bin's chain. The rest of the table is never touched.
3a. find: the node holding a key
find(K key) is a helper for put and get. It returns the node holding key, or null if the key isn't in the map:
/** The node holding key, or null if key is not in the map. */
private Node find(K key) {
// TODO 1: locate key's bin: start with the first node at index hash(key)
// TODO 2: while that node is not null, walk the chain (node = node.next)
// TODO 3: check whether the key in each node equals the requested key
// TODO 4: if it does, return that node
// TODO 5: otherwise, when the walk runs off the end of the chain, return null
}
Those are all the steps. A key can only be in the bin its hashCode gives, so find never needs to look anywhere else: if that one chain doesn't hold the key, the key isn't in the map. Replace the placeholder throw line in find with your code. The walk is the same loop you wrote for your LinkedList, starting at nodes[hash(key)] instead of at head.
toString and hashCode, every class inherits equals from Object. Object's version is the same as ==: true only for the same object. String overrides it to compare letters, so two Strings are equal when they have the same characters in the same order:
"dog".equals(new String("dog")) // true: same letters
"dog" == new String("dog") // false: different objects
"dog".equals("Dog") // false: capitals count
Equal keys are the same key. put with an equal key replaces the value instead of adding a node, and get with an equal key finds it. That's why every "the" read from a file, each a separate object, updates one count. So compare keys with equals, never ==: write node.key.equals(key).
equals and hashCode agree. Equal keys always have equal hashCodes, so they hash to the same bin. Unequal keys can still share a hashCode (Aa and BB), which is why find needs equals to pick the right one.
3b. put: replace, or add a new node
put(K key, V value) associates the value with the key. As in Lab 06: if the map already has the key, the old value is replaced and returned; put does nothing if the value is null; and it returns null if there was no mapping for the key.
public V put(K key, V value) {
// TODO 1: if value is null, do nothing: return null
// TODO 2: use find to look for a node that already holds key
// TODO 3: if there is one, save its old value, store the new value in it,
// and return the old value
// TODO 4: otherwise, make a new Node for key and value, and add it at the
// FRONT of the chain in bin hash(key)
// TODO 5: add 1 to size
// TODO 6 (Task 4): grow the table here when it is too full.
// Leave this TODO as a comment for now.
// TODO 7: return null: there was no old value
}
Leave TODO 6 as a comment until Task 4. If put calls resize now, put stops with "resize is not written yet (Task 4)" and the Task 3 section says SKIP.
TODO 4 is your LinkedList's add-at-the-head, with nodes[hash(key)] playing the role of head: the new node's next becomes the bin's current first node, and then the new node becomes the bin's first node. If the bin was empty, the same two steps still work: the new node's next is null.
3c. size and clear
public int size() {
// TODO: return the number of keys in the map (put keeps the size field up to date)
}
public void clear() {
// TODO 1: start over with a new, empty table of the starting size:
// nodes = makeTable(initialCapacity);
// TODO 2: set size back to 0
}
Ask Yourself — the front of the chain
- Why add at the front rather than at the end of the chain? How many nodes does adding at the front have to look at?
- What happens to the words already in a bin if you write
nodes[i] = newNode;but forgetnewNode.next = nodes[i];? - put calls find before it adds. What would happen to size, and to get, if it skipped find and always added a new node?
Copy, paste, and complete: add these lines inside your main method, and complete the TODOs.
// Task 3: Add these lines inside your main method, after the Task 2 lines.
HashMap<String, Integer> map = new HashMap<String, Integer>(8);
map.put("dog", 15);
map.put("bee", 8);
map.put("eel", 16);
System.out.print(map); // expected: bee in bin 2; eel and dog together in bin 4, eel first
System.out.println("put(\"ant\", 3) adds a NEW word, so there is no old value to return.");
System.out.println(" expected null, got " + map.put("ant", 3));
System.out.println("put(\"bee\", 80) replaces bee's value, so it returns the OLD value, 8.");
System.out.println(" expected 8, got " + map.put("bee", 80));
System.out.println("expected size 4, got " + map.size());
// TODO: Put "Aa" (1) and "BB" (2). Both hashCodes are 2112: predict their bin
// and their order in the chain, then print the map.
// TODO: Put "dog" again with a new value. Print what put returns, and print
// the map to check that no new node was added.
Type:
$ javac *.java $ java HashMap
You should see: your Task 2 hashCodes, then the table, then each "expected … got …" line with the two values the same. Then whatever your TODO lines print.
bin 0:
bin 1:
bin 2: <bee -> 8> |
bin 3:
bin 4: <eel -> 16> | <dog -> 15> |
...
put("ant", 3) adds a NEW word, so there is no old value to return.
expected null, got null
put("bee", 80) replaces bee's value, so it returns the OLD value, 8.
expected 8, got 8
expected size 4, got 4
If not: compare your table with the one you drew. dog listed before eel means put added at the end of the chain instead of the front.
Then: run java Lab07Tester. The Task 1 to Task 3 sections should pass.
Task 4 — resize: grow the table DESIGN
A hash map is fast because each chain is short. Put 1,000 words into 4 bins and the chains average 250 nodes: get becomes a walk down a long linked list. Lecture asked what makes a hash table slow (too many collisions, because the table is too full) and how to fix it (make the table bigger, re-hash everything; L27, slides 53–56). Your data structure must follow this rule:
With new HashMap(4, 0.75), fC = 0.75 × 4 = 3, so putting a 4th key makes the table grow to 8 bins; its new limit is 6.
Every key has to move. A key's bin is hashCode % capacity, so when the capacity changes, so does the bin. "ant" (96743) is in bin 96743 % 4 = 3 with 4 bins, but belongs in bin 96743 % 8 = 7 with 8 bins. The simplest way to re-insert every key in the right place is to put it again, into the new table:
The first lines and the loop over the old bins are given. Copy them into your HashMap.java, in place of the line that throws the exception, and finish the two TODOs:
private void resize(int newCapacity) {
Node[] oldNodes = nodes; // keep the old table, so we can still read its chains
nodes = makeTable(newCapacity); // a new, empty table: from now on, hash uses newCapacity
// TODO 1: set size to 0: put will count every key again
for (int i = 0; i < oldNodes.length; i++) { // every bin of the OLD table
Node node = oldNodes[i]; // the first node of this bin's chain
// TODO 2: while node is not null:
// put node's key and value into the new table,
// then move on to node.next
}
}
Why keep oldNodes? Once nodes refers to the new table, the old table can be reached only through oldNodes. Without it, every key would be lost.
Then finish put's TODO 6: if size > maxLoadFactor * capacity(), call resize(2 * capacity()). resize takes the new capacity as a parameter because Task 7 uses it to shrink the table, too.
size = 0. resize puts every key again, and put adds 1 to size for each one. Without resetting size, every key is counted twice, the new table looks full at once, and it grows again, and again. The tester reports this as a StackOverflowError or as a wrong size.Watch it grow: HashDemo
Download now:
HashDemo uses your HashMap to put the seven words from Lab 06 (dog, bee, fox, ant, cat, eel, gnu, with lecture's numbers as values) into new HashMap(4, 0.75), one word at a time. Like BSTDemo in Lab 06, it is a program for watching, not for changing: you don't need to read HashDemo.java.
Before each put, HashDemo stops and asks which bin the word goes in. Work it out on paper first: the word's hashCode, % the current capacity, Math.abs if negative. Also decide whether this put makes the table grow. You can type your answer before you press Enter, so that it shows on the screen next to HashDemo's. Then press Enter, and HashDemo shows:
- the arithmetic: the hashCode, the remainder, and the bin;
- the size compared with the limit, 0.75 × capacity, and whether the table grew;
- when it grows, every word's old bin and new bin, because resize put each one again;
- the whole table, printed by your
toString.
Type:
$ javac *.java $ java HashDemo
You should see: the empty 4-bin table and the first question. Press Enter 7 times, once for each word.
new HashMap(4, 0.75): a table with 4 bins, numbered 0 to 3.
It grows when a put makes size > 0.75 x capacity. With 4 bins that limit is 3,
so the 4th word will make it double.
bin 0:
bin 1:
bin 2:
bin 3:
------------------------------------------------------------
put("dog", 15): which bin? Work it out, then press Enter.
If not: if HashDemo stops with "not written yet", it names the method it needs. Write that method and run it again. At the end, HashDemo says "maxDepth: not written yet (Task 6)": that is expected until Task 6.
Ask Yourself — growing
- After which word does the table grow the first time? The second time?
- dog and eel shared bin 4 of the 8-bin table and share bin 12 of the 16-bin table. Why did they stay together? Could two keys that share a bin in an 8-bin table end up apart in a 16-bin table?
- resize calls put, and put can call resize. Can a resize ever cause a second resize? Why not?
- Putting 1,000 different keys into
new HashMap(4, 0.75)makes the table grow 9 times, ending with 2,048 bins. Each resize touches every key. Why is growing by doubling still fast overall? What if the table grew by just one bin each time?
Type:
$ javac *.java $ java Lab07Tester
You should see: the Task 1 to Task 4 sections pass; Task 5 says SKIP until you write get.
If not: a StackOverflowError or a size that is too big usually means resize doesn't set size to 0. Capacities that grow too soon mean put compares with >= instead of >.
Task 5 — get REUSE
get(K key) returns the value the key is mapped to, or null if the map contains no mapping for the key. find does the work:
public V get(K key) {
// TODO 1: use find to look for the node that holds key
// TODO 2: if find returned null, the key isn't in the map: return null
// TODO 3: otherwise, return that node's value
}
Do TODO 2 before TODO 3: reading .value from a null node crashes with a NullPointerException.
Copy, paste, and complete: add these lines inside your main method, after the Task 3 lines.
// Task 5: Add these lines inside your main method, after the Task 3 lines.
System.out.println("get(\"eel\"): eel is in the map with value 16.");
System.out.println(" expected 16, got " + map.get("eel"));
System.out.println("get(\"yak\"): yak was never put, so there is no value.");
System.out.println(" expected null, got " + map.get("yak"));
HashMap<String, Integer> onlyBB = new HashMap<String, Integer>(8);
onlyBB.put("BB", 2);
System.out.println("get(\"Aa\") from a map holding only BB: same bin, different word.");
System.out.println(" expected null, got " + onlyBB.get("Aa"));
// TODO: get "BB" from onlyBB. Predict the value first.
Type:
$ javac *.java $ java HashMap
You should see: after your Task 3 output, each new "expected … got …" line with the two values the same:
get("eel"): eel is in the map with value 16.
expected 16, got 16
get("yak"): yak was never put, so there is no value.
expected null, got null
get("Aa") from a map holding only BB: same bin, different word.
expected null, got null
If not: if get("Aa") returns 2, find is comparing hashCodes or bins instead of keys: compare with equals.
Then: run java Lab07Tester. The Task 1 to Task 5 sections should pass.
Task 6 — containsKey, keySet, values, and maxDepth REUSE
public boolean containsKey(K key) {
// TODO: return true if find finds a node holding key, and false otherwise
}
The other three visit every node: every bin, and each bin's whole chain. That's the loop in the provided toString; read it first.
public ArrayList<K> keySet() {
// TODO 1: make an empty ArrayList of keys
// TODO 2: for each bin index from 0 to capacity() - 1:
// TODO 3: walk that bin's chain, from nodes[i] until null
// TODO 4: add each node's key to the list
// TODO 5: return the list
}
public ArrayList<V> values() {
// TODO: the same as keySet, adding each node's value instead.
// Visit the bins and chains in the SAME order as keySet, so that
// values().get(i) is the value for keySet().get(i).
}
public int maxDepth() {
// TODO 1: keep the largest chain length found so far (start at 0)
// TODO 2: for each bin, count the nodes in its chain
// TODO 3: if this count is bigger than the largest so far, remember it (Math.max)
// TODO 4: return the largest count: the number of items in the biggest bin
}
maxDepth is the size of the biggest bin. MapSet defines maxDepth as the most nodes get may have to look at to find one key: for your tree that was the number of levels, and for a hash map it is the biggest bin. An empty map has 0.
Unlike BSTMap, keySet is not in alphabetical order. The order comes from the bins, and changes whenever the table grows.
Count a file: HashDemo
When all four methods are written, HashDemo can count the words of a file. It uses new HashMap() and your put and get. It prints how many words it read, how many are different, how many times the table grew, the load factor, the table itself, its maxDepth, and each word with its count from your keySet and values.
tiny.txt is the 60-word opening of A Tale of Two Cities, and sorted.txt holds its 20 different words, in alphabetical order. These are the files from Lab 06, but HashDemo reads files only from the folder it runs in. Download them into your Project07 folder now (or copy them there from your Project06 folder).
Download now:
Type:
$ javac *.java $ java HashDemo tiny.txt $ java HashDemo sorted.txt
You should see: for each file, a summary like this, then the table, its maxDepth, and every word with its count:
Counted tiny.txt with new HashMap(): 16 bins to start, growing when size > 0.75 x capacity. words read: 60 different words: 20 (the map's size: one key per different word) times it grew: 1 (16 -> 32 bins) load factor: 0.63 (size / capacity: the average number of items per bin)
If not: FileNotFoundException means the file isn't in your Project07 folder. "not written yet" names the Task 6 method HashDemo still needs.
Ask Yourself — order doesn't matter
- In Lab 06, your BSTMap had 6 levels for the words of tiny.txt and 20 for sorted.txt. What maxDepth does HashDemo report for each? Why does the order of the words make no difference to a hash map?
- Suppose every word had the same hashCode. What would the table look like, and what would maxDepth be? Which structure from earlier in the course would your HashMap have become?
Type:
$ javac *.java $ java Lab07Tester
You should see: the Task 1 to Task 6 sections pass; Task 7 says SKIP until you write remove.
If not: if keySet has fewer words than the size, the loop over a chain stops after the first node. If keySet and values don't line up, the two methods visit the bins in different orders.
Task 7 — remove, and shrinking the table DESIGN
remove(K key) removes the key and its value from the map and returns the value it was mapped to, or null if the key was not there. Lecture worked through the three situations (L28, slides 20–41): the key does not exist; the node is the first in its chain; the node is in the middle or at the end. Walk the chain with two references, node and prev, the node before it:
public V remove(K key) {
// TODO 1: find key's bin index with hash(key)
// TODO 2: start node at the first node of that bin, and prev at null
// TODO 3: walk the chain until node is null or node's key equals key,
// moving both: prev becomes node, node becomes node.next
// TODO 4: if node is null, the key isn't in the map: return null
// TODO 5: if prev is null, node is the FIRST node in its bin:
// make the bin start at node.next instead
// TODO 6: otherwise, link around node: prev's next becomes node.next
// TODO 7: subtract 1 from size
// TODO 8: shrink the table if it is too empty (see below)
// TODO 9: return the removed node's value
}
The other side of the rule. Task 4 grew the table when n became greater than fC. After a remove, n can become smaller than fC/4: a big table holding a few keys, where every keySet, values, and resize has to look through all the empty bins. Then halve the table, using the same resize. For TODO 8: if capacity() > initialCapacity and size < maxLoadFactor * capacity() / 4, call resize(capacity() / 2). Checking against initialCapacity keeps the table from shrinking below the size it started with, so the rule only fails for n smaller than the initial capacity, as Task 4's rule allows.
For example, lecture's 7 words in new HashMap(4, 0.75) grow the table to 16 bins. Removing them one at a time leaves the table at 16 until only 2 words are left (2 < 0.75 × 16 / 4 = 3); it halves to 8, then to 4 when 1 word is left, and stays at 4.
Ask Yourself — the other side of the coin
- Why does remove need
prev, when find only needednode? - Suppose the table shrank as soon as it was half full instead (n < fC/2). Start with a table that has just doubled, then remove one key, put one key, remove one key, and so on. What would happen on every step?
- Compare this remove with your BSTMap's remove in Project 06. Both have three cases. Which was harder, and why?
Type:
$ javac *.java $ java Lab07Tester
You should see: every section passes, and the summary at the end says:
Summary: 84 passed, 0 failed, 0 skipped. All checks passed.
If not: the first FAIL in the Task 7 section says which case of remove is wrong: the first node of a chain, a node in the middle, or the shrinking rule.
The tester: what each section checks
You have been running Lab07Tester at the end of every task. It runs every check, keeps going after a failure, and ends with a summary. Each line says what the tester did and what should happen, for example put("cat", 99): cat is already in the map, so put returns cat's OLD value, 10. When a check fails, it shows what the answer should be and what yours gave. Its sections follow the tasks:
| Section | What it checks |
|---|---|
| Task 1: the provided HashMap | the tester can find nodes and size; each constructor's starting capacity |
| Task 2: hash | dog's bin with 4 and 16 bins; a negative hashCode; the smallest int; 9,000 random words always in range |
| Task 3: find, put, size, clear | each word in the bin its hashCode gives; size; two words with the same hashCode sharing a chain; put's return values; replacing adds no node; a null value; the same word in a different String object; 300 random keys; clear |
| Task 4: resize | the capacity after each of lecture's 7 words (4, 4, 4, 8, 8, 8, 16); size after growing; every word moved to its new bin; last year's keys 5, 100, 30, 12, 4, 6; 1,000 random keys; clear going back to the starting capacity |
| Task 5: get | present and missing words, two words in one chain, a missing word in a busy bin, an empty map, and after the table grows |
| Task 6: containsKey, keySet, values, maxDepth | every key once, values lined up with keys, whole chains listed, empty lists, the biggest bin |
| Task 7: remove | the first, middle, and last node of a chain; missing keys; size; 20,000 random puts and removes checked against Java's own map; the capacity after each of 7 removes; the rule fC/4 ≤ n ≤ fC after each of 2,000 removes |
The table above lists every section and what it checks. How to read the results is in Task 1.
Before you leave lab
The lab checkpoint was at the end of Task 5: don't wait until the end of the page to show it. If you haven't shown it yet, show a TA or instructor your Lab07Tester output with the Task 1 through Task 5 sections passing. Finish Tasks 6 and 7 after the checkpoint, in lab or on your own, before you start Project 07; the project uses maxDepth, and its checklist asks for every Lab07Tester section to pass.
This is a required graded lab. After your checkpoint you may work on the project until the individual closed-book quiz; remain for the quiz. Make sure your code is in Projects/Project07 before the lab ends.