import java.util.ArrayList; /** * A map built on a hash table that uses separate chaining. * * The table is an array of bins. Each bin holds a chain: a singly linked list * of Nodes, like the LinkedList you built earlier in the course. To find a * key, hash it to pick one bin, then walk that bin's chain. * * Every method below that you write starts with a "throw" line. It is a * placeholder: it lets this file compile and tells the tester the method is not * written yet. Delete that line when you write the method. */ public class HashMap implements MapSet { /** One entry of a chain: a key, its value, and the next node in the same bin. */ private class Node { K key; V value; Node next; Node(K key, V value) { this.key = key; this.value = value; this.next = null; } public String toString() { return "<" + key + " -> " + value + ">"; } } private Node[] nodes; // nodes[i] is the first node of bin i's chain, or null private int size; // the number of keys in the map private double maxLoadFactor; // the table grows when size > maxLoadFactor * capacity() private int initialCapacity; // the capacity the map started with /** A map with 16 bins that grows when it is 75% full (Java's own defaults). */ public HashMap() { this(16); } /** A map with the given number of bins that grows when it is 75% full. */ public HashMap(int capacity) { this(capacity, 0.75); } /** A map with the given number of bins that grows when size > loadFactor * capacity. */ public HashMap(int capacity, double loadFactor) { nodes = makeTable(capacity); size = 0; maxLoadFactor = loadFactor; initialCapacity = capacity; } /** * Makes an array of empty bins. Java does not allow "new Node[capacity]" * here, for a technical reason about generic types, so this method uses a * line that does the same thing. Use it as it is. */ @SuppressWarnings({"unchecked", "rawtypes"}) private Node[] makeTable(int capacity) { return (Node[]) new HashMap.Node[capacity]; } /** The length of the array: the number of bins, used or not. */ public int capacity() { return nodes.length; } /** Prints every bin and its chain, for example "bin 4: 15> | 16> | ". */ public String toString() { String output = ""; for (int i = 0; i < this.capacity(); i++) { Node node = this.nodes[i]; output += "bin " + i + ": "; while (node != null) { output += node.toString() + " | "; node = node.next; } output += "\n"; } return output; } // ------------------------------------------------------------------ // Task 2 // ------------------------------------------------------------------ /** The index of the bin where key belongs: a number from 0 to capacity() - 1. */ private int hash(K key) { throw new UnsupportedOperationException("hash is not written yet (Task 2)"); } // ------------------------------------------------------------------ // Task 3 // ------------------------------------------------------------------ /** The node holding key, or null if key is not in the map. */ private Node find(K key) { throw new UnsupportedOperationException("find is not written yet (Task 3)"); } public V put(K key, V value) { throw new UnsupportedOperationException("put is not written yet (Task 3)"); } public int size() { throw new UnsupportedOperationException("size is not written yet (Task 3)"); } public void clear() { throw new UnsupportedOperationException("clear is not written yet (Task 3)"); } // ------------------------------------------------------------------ // Task 4 // ------------------------------------------------------------------ /** Moves every key and value into a new table with newCapacity bins. */ private void resize(int newCapacity) { throw new UnsupportedOperationException("resize is not written yet (Task 4)"); } // ------------------------------------------------------------------ // Task 5 // ------------------------------------------------------------------ public V get(K key) { throw new UnsupportedOperationException("get is not written yet (Task 5)"); } // ------------------------------------------------------------------ // Task 6 // ------------------------------------------------------------------ public boolean containsKey(K key) { throw new UnsupportedOperationException("containsKey is not written yet (Task 6)"); } public ArrayList keySet() { throw new UnsupportedOperationException("keySet is not written yet (Task 6)"); } public ArrayList values() { throw new UnsupportedOperationException("values is not written yet (Task 6)"); } public int maxDepth() { throw new UnsupportedOperationException("maxDepth is not written yet (Task 6)"); } // ------------------------------------------------------------------ // Task 7 // ------------------------------------------------------------------ public V remove(K key) { throw new UnsupportedOperationException("remove is not written yet (Task 7)"); } }