001package algs34; 002import stdlib.*; 003import algs13.Queue; 004import algs31.SequentialSearchST; 005/* *********************************************************************** 006 * Compilation: javac SeparateChainingHashST.java 007 * Execution: java SeparateChainingHashST 008 * 009 * A symbol table implemented with a separate-chaining hash table. 010 * 011 * % java SeparateChainingHashST 012 * 013 *************************************************************************/ 014 015public class SeparateChainingHashST<K, V> { 016 private static final int INIT_CAPACITY = 4; 017 018 // largest prime <= 2^i for i = 3 to 31 019 // not currently used for doubling and shrinking 020 // private static final int[] PRIMES = { 021 // 7, 13, 31, 61, 127, 251, 509, 1021, 2039, 4093, 8191, 16381, 022 // 32749, 65521, 131071, 262139, 524287, 1048573, 2097143, 4194301, 023 // 8388593, 16777213, 33554393, 67108859, 134217689, 268435399, 024 // 536870909, 1073741789, 2147483647 025 // }; 026 027 private int N; // number of key-value pairs 028 private int M; // hash table size 029 private SequentialSearchST<K, V>[] st; // array of linked-list symbol tables 030 031 032 // create separate chaining hash table 033 public SeparateChainingHashST() { 034 this(INIT_CAPACITY); 035 } 036 037 // create separate chaining hash table with M lists 038 @SuppressWarnings("unchecked") 039 public SeparateChainingHashST(int M) { 040 this.M = M; 041 st = new SequentialSearchST[M]; 042 for (int i = 0; i < M; i++) 043 st[i] = new SequentialSearchST<>(); 044 } 045 046 // resize the hash table to have the given number of chains b rehashing all of the keys 047 private void resize(int chains) { 048 SeparateChainingHashST<K, V> temp = new SeparateChainingHashST<>(chains); 049 for (int i = 0; i < M; i++) { 050 for (K key : st[i].keys()) { 051 temp.put(key, st[i].get(key)); 052 } 053 } 054 this.M = temp.M; 055 this.N = temp.N; 056 this.st = temp.st; 057 } 058 059 // hash value between 0 and M-1 060 private int hash(K key) { 061 return (key.hashCode() & 0x7fffffff) % M; 062 } 063 064 // return number of key-value pairs in symbol table 065 public int size() { 066 return N; 067 } 068 069 // is the symbol table empty? 070 public boolean isEmpty() { return size() == 0; } 071 072 // is the key in the symbol table? 073 public boolean contains(K key) { return get(key) != null; } 074 075 // return value associated with key, null if no such key 076 public V get(K key) { 077 int i = hash(key); 078 return st[i].get(key); 079 } 080 081 // insert key-value pair into the table 082 public void put(K key, V val) { 083 if (val == null) { delete(key); return; } 084 085 // double table size if average length of list >= 10 086 if (N >= 10*M) resize(2*M); 087 088 int i = hash(key); 089 if (!st[i].contains(key)) N++; 090 st[i].put(key, val); 091 } 092 093 // delete key (and associated value) if key is in the table 094 public void delete(K key) { 095 int i = hash(key); 096 if (st[i].contains(key)) N--; 097 st[i].delete(key); 098 099 // halve table size if average length of list <= 1 100 if (M > INIT_CAPACITY && N <= 2*M) resize(M/2); 101 } 102 103 // return keys in symbol table as an Iterable 104 public Iterable<K> keys() { 105 Queue<K> queue = new Queue<>(); 106 for (int i = 0; i < M; i++) { 107 for (K key : st[i].keys()) 108 queue.enqueue(key); 109 } 110 return queue; 111 } 112 113 114 /* ********************************************************************* 115 * Unit test client. 116 ***********************************************************************/ 117 public static void main(String[] args) { 118 SeparateChainingHashST<String, Integer> st = new SeparateChainingHashST<>(); 119 for (int i = 0; !StdIn.isEmpty(); i++) { 120 String key = StdIn.readString(); 121 st.put(key, i); 122 } 123 124 // print keys 125 for (String s : st.keys()) 126 StdOut.println(s + " " + st.get(s)); 127 128 } 129 130}