import java.io.BufferedReader; import java.io.FileReader; import java.io.IOException; import java.util.ArrayList; import java.util.Scanner; /** * Shows your HashMap at work, one step at a time. * * java HashDemo puts the seven words from Lab 06 into new HashMap(4, 0.75), * pausing before each put so you can predict its bin * java HashDemo tiny.txt counts the words of a file with new HashMap() and * shows the table, its maxDepth, and every count * * Press Enter in the Terminal to take each step. * It uses your put, get, size, capacity, toString, keySet, values, and maxDepth. * You don't need to read or change this file. */ public class HashDemo { // Reads the Enter key presses from the Terminal. private static final Scanner in = new Scanner(System.in); /** * Runs the lecture words when there is no file name, or counts the words of a file. * If a method HashDemo needs is not written yet, your HashMap throws an * UnsupportedOperationException that names it; HashDemo prints that name and stops. */ public static void main(String[] args) throws IOException { try { if (args.length == 0) { lectureWords(); } else { countWords(args[0]); } } catch (UnsupportedOperationException e) { System.out.println(); System.out.println("Stopped: " + e.getMessage() + "."); System.out.println("Write that method, then run HashDemo again."); } } /** Prints a prompt and waits for Enter, so you can make a prediction before each step. */ private static void pause(String prompt) { System.out.print(prompt); if (in.hasNextLine()) { // false only when input is piped in and has run out in.nextLine(); } } /** * The bin a key belongs in, by the same rule as your hash method: * Math.abs(key.hashCode() % capacity). HashDemo uses it to report * each key's bin before and after the table grows. */ private static int bin(String key, int capacity) { return Math.abs(key.hashCode() % capacity); } /** * Explains, in one sentence, how a key's hashCode becomes a bin number: * the hashCode, the remainder after dividing by the capacity, and, * when the remainder is negative, what Math.abs makes it. */ private static String arithmetic(String key, int capacity) { int code = key.hashCode(); int remainder = code % capacity; // negative when the hashCode is negative String text = "\"" + key + "\".hashCode() is " + code + ", and " + code + " % " + capacity + " is " + remainder; if (remainder < 0) { text += "; Math.abs makes it " + Math.abs(remainder); } return text + ", so \"" + key + "\" goes in bin " + Math.abs(remainder) + "."; } /** * Puts lecture's seven words from Lab 06 into a small table, one at a time. * Before each put it waits for your prediction; after it, it shows the arithmetic, * whether the table grew, where every key moved if it did, and the whole table. */ private static void lectureWords() { // The same words and numbers as BSTDemo in Lab 06. Each word's value is its lecture number. String[] words = {"dog", "bee", "fox", "ant", "cat", "eel", "gnu"}; int[] numbers = {15, 8, 17, 3, 10, 16, 20}; double loadFactor = 0.75; // Start with only 4 bins so the table has to grow twice during seven puts. HashMap map = new HashMap(4, loadFactor); System.out.println("new HashMap(4, 0.75): a table with 4 bins, numbered 0 to 3."); System.out.println("It grows when a put makes size > 0.75 x capacity. With 4 bins that limit is 3,"); System.out.println("so the 4th word will make it double."); System.out.println(); System.out.print(map); // your toString: one line per bin // The words put so far, in order, so we can show where each one moves when the table grows. ArrayList stored = new ArrayList(); for (int i = 0; i < words.length; i++) { String word = words[i]; int before = map.capacity(); // remember the capacity so we can tell whether put grew the table System.out.println(); System.out.println("------------------------------------------------------------"); pause("put(\"" + word + "\", " + numbers[i] + "): which bin? Work it out, then press Enter. "); System.out.println(arithmetic(word, before)); // the answer to the prediction map.put(word, numbers[i]); stored.add(word); if (map.capacity() == before) { // No resize: the size is still within the limit. System.out.println("size is now " + map.size() + ", not more than 0.75 x " + before + " = " + (loadFactor * before) + ", so the table keeps its " + before + " bins."); } else { // put called resize: show each stored key's bin in the old table and in the new one. int after = map.capacity(); System.out.println("size is now " + map.size() + ", MORE than 0.75 x " + before + " = " + (loadFactor * before) + ", so the table grew from " + before + " to " + after + " bins."); System.out.println("A key's bin is hashCode % capacity, and the capacity changed, so resize put"); System.out.println("every key again. Where each one went:"); for (String key : stored) { int from = bin(key, before); int to = bin(key, after); System.out.println(" " + key + ": bin " + from + " of " + before + " -> bin " + to + " of " + after + (from == to ? " (the same number)" : "")); } System.out.println("The new limit is 0.75 x " + after + " = " + (loadFactor * after) + "."); } System.out.print(map); } // Explain the one collision in the final 16-bin table. System.out.println(); System.out.println("------------------------------------------------------------"); System.out.println("Done: size " + map.size() + ", capacity " + map.capacity() + "."); System.out.println("dog (99644) and eel (100300) have different hashCodes, but both leave a"); System.out.println("remainder of 12 when divided by 16, so they share bin 12: a collision. Their"); System.out.println("bin holds a chain of two nodes, and get tells them apart with equals."); try { System.out.println("maxDepth (the number of items in the biggest bin): " + map.maxDepth()); } catch (UnsupportedOperationException e) { // maxDepth comes in Task 6, after the rest of this demo already works. System.out.println("maxDepth: not written yet (Task 6)."); } } /** * Counts the words in a file with your get and put, the same way WordCounter will, * then reports the size, how often the table grew, the load factor, the table * (if it is small enough to read), its maxDepth, and every word with its count. */ private static void countWords(String filename) throws IOException { HashMap map = new HashMap(); // 16 bins, load factor 0.75 int total = 0; // words read, counting repeats int grew = 0; // times the table doubled int capacity = map.capacity(); // the capacity before the latest put // Read the file one line at a time and split each line into words at the spaces. BufferedReader reader = new BufferedReader(new FileReader(filename)); String line = reader.readLine(); while (line != null) { for (String word : line.split("\\s+")) { if (word.length() > 0) { // A new word starts at 1; a word already in the map gets its count plus 1. Integer count = map.get(word); if (count == null) { map.put(word, 1); } else { map.put(word, count + 1); } total++; // If the capacity changed, that put made the table grow. if (map.capacity() != capacity) { grew++; capacity = map.capacity(); } } } line = reader.readLine(); } reader.close(); // Summary of what the map holds. System.out.println("Counted " + filename + " with new HashMap(): 16 bins to start, growing when"); System.out.println("size > 0.75 x capacity."); System.out.println(" words read: " + total); System.out.println(" different words: " + map.size() + " (the map's size: one key per different word)"); System.out.println(" times it grew: " + grew + " (16 -> " + map.capacity() + " bins)"); System.out.printf(" load factor: %.2f (size / capacity: the average number of items per bin)%n", (double) map.size() / map.capacity()); System.out.println(); // Print the table only when it is small enough to read in the Terminal. if (map.capacity() <= 64) { System.out.print(map); System.out.println(); } System.out.println("maxDepth: " + map.maxDepth() + " (the number of items in the biggest bin: the most nodes"); System.out.println(" get may have to look at to find one word)"); System.out.println(); // keySet and values list the map bin by bin, so the same index gives a word and its count. System.out.println("Each word and its count, in keySet order. That is bin by bin, not alphabetical:"); ArrayList keys = map.keySet(); ArrayList values = map.values(); for (int i = 0; i < keys.size(); i++) { System.out.println(" " + keys.get(i) + " " + values.get(i)); } } }