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 goescompare with compareTo, go left or right, level by levelturn the key into a bin number with hashCode, go straight there
Inside one spotone nodea chain: a linked list of every key that landed in that bin
What keys must havecompareTo (that's the K extends Comparable<K>)hashCode and equals, which every Java object has
Order of keySet()sortedbin by bin, which looks random
maxDepth(): the most nodes get may look atthe number of levelsthe 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.

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.

CommandWhat it runsWhen
java Lab07TesterThe tester: checks your HashMap, one section per taskAt the end of every task, starting with Task 1
java HashMapYour 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 HashDemo
java 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.

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.javaWhat 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:

MethodWhat it doesTask
private int hash(K key)the bin where key belongs: its hashCode, brought into the range 0 to capacity() - 12
private Node find(K key)a helper: the node holding key, or null3
put(K key, V value)stores the value under the key; returns the old value, or null3
size(), clear()the number of keys; empty the map3
private void resize(int newCapacity)a helper: moves every key into a table with newCapacity bins4
get(K key)the value stored under key, or null5
containsKey, keySet, values, maxDepthis the key there; every key; every value; the size of the biggest bin6
remove(K key)removes the key, returns its value, and shrinks the table if it gets too empty7

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:

Run it in Terminal, in your Project07 folder

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.

Task 2 — Implement hash: from a key to a bin READ AND EXPERIMENT

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.

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?
}
Run it in Terminal, in your Project07 folder

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 equals to 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.

KeyhashCode% 4% 8% 16
dog996440412
bee97410222
eel1003000412

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?

  1. With 4 bins, which bin does "bee" (97410) go in? With 8 bins? Check your answers against the table above.
  2. 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?
  3. "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:

Run it in Terminal, in your Project07 folder

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.

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

  1. 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?
  2. What happens to the words already in a bin if you write nodes[i] = newNode; but forget newNode.next = nodes[i];?
  3. 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.
Run it in Terminal, in your Project07 folder

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.

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.
Run it in Terminal, in your Project07 folder

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

  1. After which word does the table grow the first time? The second time?
  2. 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?
  3. resize calls put, and put can call resize. Can a resize ever cause a second resize? Why not?
  4. 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?
Run it in Terminal, in your Project07 folder

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.
Run it in Terminal, in your Project07 folder

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:

Run it in Terminal, in your Project07 folder

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

  1. 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?
  2. 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?
Run it in Terminal, in your Project07 folder

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

  1. Why does remove need prev, when find only needed node?
  2. 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?
  3. Compare this remove with your BSTMap's remove in Project 06. Both have three cases. Which was harder, and why?
Run it in Terminal, in your Project07 folder

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:

SectionWhat it checks
Task 1: the provided HashMapthe tester can find nodes and size; each constructor's starting capacity
Task 2: hashdog'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, cleareach 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: resizethe 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: getpresent 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, maxDepthevery key once, values lined up with keys, whole chains listed, empty lists, the biggest bin
Task 7: removethe 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.

Begin Project 07 →