Below is the syntax highlighted version of HashST.java
from §4.4 Symbol Tables.
/****************************************************************************** * Compilation: javac HashST.java * Execution: java HashST * Dependencies: StdIn.java StdOut.java * * A symbol table implemented with a separate-chaining hash table. * ******************************************************************************/ /** * The {@code HashST} class represents a symbol table of generic * key-value pairs. * It supports the usual <em>put</em>, <em>get</em>, <em>contains</em>, * <em>remove</em>, <em>size</em>, and <em>is-empty</em> methods. * It also provides a <em>keys</em> method for iterating over all the keys. * A symbol table implements the <em>associative array</em> abstraction: * when associating a value with a key that is already in the symbol table, * the convention is to replace the old value with the new value. * Unlike {@link java.util.Map}, this class uses the convention that * values cannot be {@code null}; setting the * value associated with a key to {@code null} is equivalent to deleting the key * from the symbol table. * <p> * This implementation uses a separate-chaining hash table. It requires that * the key type overrides the {@code equals()} and {@code hashCode()} methods. * The expected time per <em>put</em>, <em>contains</em>, or <em>remove</em> * operation is constant, subject to the uniform hashing assumption. * The <em>size</em>, and <em>is-empty</em> operations take constant time. * Construction takes constant time. * <p> * For additional documentation, * see <a href="https://introcs.cs.princeton.edu/44st">Section 4.4</a> of * <i>Computer Science: An Interdisciplinary Approach</i> * by Robert Sedgewick and Kevin Wayne. * For other implementations, see {@link ST} and {@link BST}. * * @author Robert Sedgewick * @author Kevin Wayne */ public class HashST<Key, Value> { private static final int INIT_CAPACITY = 4; private int n; // number of key-value pairs private int m; // number of chains private Node[] st; // array of linked-list symbol tables // a helper linked list data type private static class Node { private final Object key; private Object val; private Node next; public Node(Object key, Object val, Node next) { this.key = key; this.val = val; this.next = next; } } /** * Initializes an empty symbol table. */ public HashST() { this(INIT_CAPACITY); } /** * Initializes an empty symbol table with {@code m} chains. * @param m the initial number of chains */ public HashST(int m) { this.m = m; st = new Node[m]; } // resize the hash table to have the given number of chains, // rehashing all the keys @SuppressWarnings("unchecked") private void resize(int chains) { HashST<Key, Value> temp = new HashST<Key, Value>(chains); for (int i = 0; i < m; i++) { for (Node x = st[i]; x != null; x = x.next) { temp.put((Key) x.key, (Value) x.val); } } this.m = temp.m; this.n = temp.n; this.st = temp.st; } // hash value between 0 and m-1 private int hash(Key key) { return (key.hashCode() & 0x7fffffff) % m; } /** * Returns the number of key-value pairs in this symbol table. * * @return the number of key-value pairs in this symbol table */ public int size() { return n; } /** * Returns true if this symbol table is empty. * * @return {@code true} if this symbol table is empty; * {@code false} otherwise */ public boolean isEmpty() { return size() == 0; } /** * Returns true if this symbol table contains the specified key. * * @param key the key * @return {@code true} if this symbol table contains {@code key}; * {@code false} otherwise * @throws IllegalArgumentException if {@code key} is {@code null} */ public boolean contains(Key key) { if (key == null) throw new IllegalArgumentException("argument to contains() is null"); return get(key) != null; } /** * Returns the value associated with the specified key in this symbol table. * * @param key the key * @return the value associated with {@code key} in the symbol table; * {@code null} if no such value * @throws IllegalArgumentException if {@code key} is {@code null} */ @SuppressWarnings("unchecked") public Value get(Key key) { if (key == null) throw new IllegalArgumentException("argument to get() is null"); int i = hash(key); for (Node x = st[i]; x != null; x = x.next) { if (key.equals(x.key)) return (Value) x.val; } return null; } /** * Inserts the specified key-value pair into the symbol table, overwriting the old * value with the new value if the symbol table already contains the specified key. * Removes the specified key (and its associated value) from this symbol table * if the specified value is {@code null}. * * @param key the key * @param val the value * @throws IllegalArgumentException if {@code key} is {@code null} */ public void put(Key key, Value val) { if (key == null) throw new IllegalArgumentException("first argument to put() is null"); if (val == null) { remove(key); return; } // double table size if average length of list >= 10 if (n >= 10*m) resize(2*m); int i = hash(key); for (Node x = st[i]; x != null; x = x.next) { if (key.equals(x.key)) { x.val = val; return; } } n++; st[i] = new Node(key, val, st[i]); } /** * Removes the specified key and its associated value from this symbol table * (if the key is in this symbol table). * * @param key the key * @throws IllegalArgumentException if {@code key} is {@code null} */ public void remove(Key key) { if (key == null) throw new IllegalArgumentException("argument to remove() is null"); int i = hash(key); st[i] = remove(st[i], key); // halve table size if average length of list <= 2 if (m > INIT_CAPACITY && n <= 2*m) resize(m/2); } // remove key in linked list beginning at Node x // warning: function call stack too large if table is large private Node remove(Node x, Key key) { if (x == null) return null; if (key.equals(x.key)) { n--; return x.next; } x.next = remove(x.next, key); return x; } /** * Returns all keys in the symbol table. * * @return all keys in the symbol table, as in iterable */ @SuppressWarnings("unchecked") public Iterable<Key> keys() { Queue<Key> queue = new Queue<Key>(); for (int i = 0; i < m; i++) { for (Node x = st[i]; x != null; x = x.next) { queue.enqueue((Key) x.key); } } return queue; } /** * Unit tests the {@code HashST} data type. */ public static void main(String[] args) { HashST<String, Integer> st = new HashST<String, Integer>(); for (int i = 0; !StdIn.isEmpty(); i++) { String key = StdIn.readString(); st.put(key, i); } // print keys for (String s : st.keys()) StdOut.println(s + " " + st.get(s)); } }