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}