001package algs34; 002import stdlib.*; 003import algs13.Queue; 004/* *********************************************************************** 005 * Compilation: javac LinearProbingHashST.java 006 * Execution: java LinearProbingHashST 007 * 008 * Symbol table implementation with linear probing hash table. 009 * 010 * % java LinearProbingHashST 011 * 128.112.136.11 012 * 208.216.181.15 013 * null 014 * 015 * 016 *************************************************************************/ 017 018 019public class LinearProbingHashST<K, V> { 020 private static final int INIT_CAPACITY = 4; 021 022 private int N; // number of key-value pairs in the symbol table 023 private int M; // size of linear probing table 024 private K[] keys; // the keys 025 private V[] vals; // the values 026 027 028 // create an empty hash table - use 16 as default size 029 public LinearProbingHashST() { 030 this(INIT_CAPACITY); 031 } 032 033 // create linear proving hash table of given capacity 034 @SuppressWarnings("unchecked") 035 public LinearProbingHashST(int capacity) { 036 M = capacity; 037 keys = (K[]) new Object[M]; 038 vals = (V[]) new Object[M]; 039 } 040 041 // return the number of key-value pairs in the symbol table 042 public int size() { return N; } 043 044 // is the symbol table empty? 045 public boolean isEmpty() { return size() == 0; } 046 047 // does a key-value pair with the given key exist in the symbol table? 048 public boolean contains(K key) { return get(key) != null; } 049 050 // hash function for keys - returns value between 0 and M-1 051 private int hash(K key) { 052 return (key.hashCode() & 0x7fffffff) % M; 053 } 054 055 // resize the hash table to the given capacity by re-hashing all of the keys 056 private void resize(int capacity) { 057 LinearProbingHashST<K, V> temp = new LinearProbingHashST<>(capacity); 058 for (int i = 0; i < M; i++) { 059 if (keys[i] != null) { 060 temp.put(keys[i], vals[i]); 061 } 062 } 063 keys = temp.keys; 064 vals = temp.vals; 065 M = temp.M; 066 } 067 068 // insert the key-value pair into the symbol table 069 public void put(K key, V val) { 070 if (val == null) delete(key); 071 072 // double table size if 50% full 073 if (N >= M/2) resize(2*M); 074 075 int i; 076 for (i = hash(key); keys[i] != null; i = (i + 1) % M) { 077 if (keys[i].equals(key)) { vals[i] = val; return; } 078 } 079 keys[i] = key; 080 vals[i] = val; 081 N++; 082 } 083 084 // return the value associated with the given key, null if no such value 085 public V get(K key) { 086 for (int i = hash(key); keys[i] != null; i = (i + 1) % M) 087 if (keys[i].equals(key)) 088 return vals[i]; 089 return null; 090 } 091 092 // delete the key (and associated value) from the symbol table 093 public void delete(K key) { 094 if (!contains(key)) return; 095 096 // find position i of key 097 int i = hash(key); 098 while (!key.equals(keys[i])) { 099 i = (i + 1) % M; 100 } 101 102 // delete key and associated value 103 keys[i] = null; 104 vals[i] = null; 105 106 // rehash all keys in same cluster 107 i = (i + 1) % M; 108 while (keys[i] != null) { 109 // delete keys[i] an vals[i] and reinsert 110 K keyToRehash = keys[i]; 111 V valToRehash = vals[i]; 112 keys[i] = null; 113 vals[i] = null; 114 N--; 115 put(keyToRehash, valToRehash); 116 i = (i + 1) % M; 117 } 118 119 N--; 120 121 // halves size of array if it's 12.5% full or less 122 if (N > 0 && N <= M/8) resize(M/2); 123 124 assert check(); 125 } 126 127 // return all of the keys as in Iterable 128 public Iterable<K> keys() { 129 Queue<K> queue = new Queue<>(); 130 for (int i = 0; i < M; i++) 131 if (keys[i] != null) queue.enqueue(keys[i]); 132 return queue; 133 } 134 135 // integrity check - don't check after each put() because 136 // integrity not maintained during a delete() 137 private boolean check() { 138 139 // check that hash table is at most 50% full 140 if (M < 2*N) { 141 System.err.println("Hash table size M = " + M + "; array size N = " + N); 142 return false; 143 } 144 145 // check that each key in table can be found by get() 146 for (int i = 0; i < M; i++) { 147 if (keys[i] == null) continue; 148 else if (get(keys[i]) != vals[i]) { 149 System.err.println("get[" + keys[i] + "] = " + get(keys[i]) + "; vals[i] = " + vals[i]); 150 return false; 151 } 152 } 153 return true; 154 } 155 156 157 /* ********************************************************************* 158 * Unit test client. 159 ***********************************************************************/ 160 public static void main(String[] args) { 161 StdIn.fromFile("data/tiny.txt"); 162 163 LinearProbingHashST<String, Integer> st = new LinearProbingHashST<>(); 164 for (int i = 0; !StdIn.isEmpty(); i++) { 165 String key = StdIn.readString(); 166 st.put(key, i); 167 } 168 169 // print keys 170 for (String s : st.keys()) 171 StdOut.println(s + " " + st.get(s)); 172 } 173}