How to resolve Hash Collision?
Hashing with separate chaining.
A hash function converts keys into array indices. The second component of a hashing algorithm is collision resolution: a strategy for handling the case when two or more keys to be inserted hash to the same index. A straightforward approach to collision resolution is to build, for each of the M array indices, a linked list of the key-value pairs whose keys hash to that index. The basic idea is to choose M to be sufficiently large that the lists are sufficiently short to enable efficient search through a two-step process: hash to find the list that could contain the key, then sequentially search through that list for the key.
Code (Java):1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 | /************************************************************************* * Compilation: javac SeparateChainingHashST.java * Execution: java SeparateChainingHashST * * A symbol table implemented with a separate-chaining hash table. * * % java SeparateChainingHashST * *************************************************************************/public class SeparateChainingHashST＆lt;Key, Value> { private static final int INIT_CAPACITY = 4; // largest prime <= 2^i for i = 3 to 31 // not currently used for doubling and shrinking // private static final int[] PRIMES = { // 7, 13, 31, 61, 127, 251, 509, 1021, 2039, 4093, 8191, 16381, // 32749, 65521, 131071, 262139, 524287, 1048573, 2097143, 4194301, // 8388593, 16777213, 33554393, 67108859, 134217689, 268435399, // 536870909, 1073741789, 2147483647 // }; private int N; // number of key-value pairs private int M; // hash table size private SequentialSearchST<Key, Value>[] st; // array of linked-list symbol tables // create separate chaining hash table public SeparateChainingHashST() { this(INIT_CAPACITY); } // create separate chaining hash table with M lists public SeparateChainingHashST(int M) { this.M = M; st = (SequentialSearchST<Key, Value>[]) new SequentialSearchST[M]; for (int i = 0; i < M; i++) st[i] = new SequentialSearchST<Key, Value>(); } // resize the hash table to have the given number of chains b rehashing all of the keys private void resize(int chains) { SeparateChainingHashST<Key, Value> temp = new SeparateChainingHashST<Key, Value>(chains); for (int i = 0; i < M; i++) { for (Key key : st[i].keys()) { temp.put(key, st[i].get(key)); } } 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; } // return number of key-value pairs in symbol table public int size() { return N; } // is the symbol table empty? public boolean isEmpty() { return size() == 0; } // is the key in the symbol table? public boolean contains(Key key) { return get(key) != null; } // return value associated with key, null if no such key public Value get(Key key) { int i = hash(key); return st[i].get(key); } // insert key-value pair into the table public void put(Key key, Value val) { if (val == null) { delete(key); return; } // double table size if average length of list >= 10 if (N >= 10*M) resize(2*M); int i = hash(key); if (!st[i].contains(key)) N++; st[i].put(key, val); } // delete key (and associated value) if key is in the table public void delete(Key key) { int i = hash(key); if (st[i].contains(key)) N--; st[i].delete(key); // halve table size if average length of list <= 2 if (M > INIT_CAPACITY && N <= 2*M) resize(M/2); } // return keys in symbol table as an Iterable public Iterable<Key> keys() { Queue<Key> queue = new Queue<Key>(); for (int i = 0; i < M; i++) { for (Key key : st[i].keys()) queue.enqueue(key); } return queue; } /*********************************************************************** * Unit test client. ***********************************************************************/ public static void main(String[] args) { SeparateChainingHashST<String, Integer> st = new SeparateChainingHashST<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)); }} |
Hashing with linear probing.
Another approach to implementing hashing is to store N key-value pairs in a hash table of size M > N, relying on empty entries in the table to help with with collision resolution. Such methods are called open-addressing hashing methods. The simplest open-addressing method is called linear probing: when there is a collision (when we hash to a table index that is already occupied with a key different from the search key), then we just check the next entry in the table (by incrementing the index). There are three possible outcomes:- key equal to search key: search hit
- empty position (null key at indexed position): search miss
- key not equal to search key: try next entry
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 | /************************************************************************* * Compilation: javac LinearProbingHashST.java * Execution: java LinearProbingHashST * * Symbol table implementation with linear probing hash table. * * % java LinearProbingHashST * 128.112.136.11 * 208.216.181.15 * null * * *************************************************************************/public class LinearProbingHashST<Key, Value> { private static final int INIT_CAPACITY = 4; private int N; // number of key-value pairs in the symbol table private int M; // size of linear probing table private Key[] keys; // the keys private Value[] vals; // the values // create an empty hash table - use 16 as default size public LinearProbingHashST() { this(INIT_CAPACITY); } // create linear proving hash table of given capacity public LinearProbingHashST(int capacity) { M = capacity; keys = (Key[]) new Object[M]; vals = (Value[]) new Object[M]; } // return the number of key-value pairs in the symbol table public int size() { return N; } // is the symbol table empty? public boolean isEmpty() { return size() == 0; } // does a key-value pair with the given key exist in the symbol table? public boolean contains(Key key) { return get(key) != null; } // hash function for keys - returns value between 0 and M-1 private int hash(Key key) { return (key.hashCode() & 0x7fffffff) % M; } // resize the hash table to the given capacity by re-hashing all of the keys private void resize(int capacity) { LinearProbingHashST<Key, Value> temp = new LinearProbingHashST<Key, Value>(capacity); for (int i = 0; i < M; i++) { if (keys[i] != null) { temp.put(keys[i], vals[i]); } } keys = temp.keys; vals = temp.vals; M = temp.M; } // insert the key-value pair into the symbol table public void put(Key key, Value val) { if (val == null) { delete(key); return; } // double table size if 50% full if (N >= M/2) resize(2*M); int i; for (i = hash(key); keys[i] != null; i = (i + 1) % M) { if (keys[i].equals(key)) { vals[i] = val; return; } } keys[i] = key; vals[i] = val; N++; } // return the value associated with the given key, null if no such value public Value get(Key key) { for (int i = hash(key); keys[i] != null; i = (i + 1) % M) if (keys[i].equals(key)) return vals[i]; return null; } // delete the key (and associated value) from the symbol table public void delete(Key key) { if (!contains(key)) return; // find position i of key int i = hash(key); while (!key.equals(keys[i])) { i = (i + 1) % M; } // delete key and associated value keys[i] = null; vals[i] = null; // rehash all keys in same cluster i = (i + 1) % M; while (keys[i] != null) { // delete keys[i] an vals[i] and reinsert Key keyToRehash = keys[i]; Value valToRehash = vals[i]; keys[i] = null; vals[i] = null; N--; put(keyToRehash, valToRehash); i = (i + 1) % M; } N--; // halves size of array if it's 12.5% full or less if (N > 0 && N <= M/8) resize(M/2); assert check(); } // return all of the keys as in Iterable public Iterable<Key> keys() { Queue<Key> queue = new Queue<Key>(); for (int i = 0; i < M; i++) if (keys[i] != null) queue.enqueue(keys[i]); return queue; } // integrity check - don't check after each put() because // integrity not maintained during a delete() private boolean check() { // check that hash table is at most 50% full if (M < 2*N) { System.err.println("Hash table size M = " + M + "; array size N = " + N); return false; } // check that each key in table can be found by get() for (int i = 0; i < M; i++) { if (keys[i] == null) continue; else if (get(keys[i]) != vals[i]) { System.err.println("get[" + keys[i] + "] = " + get(keys[i]) + "; vals[i] = " + vals[i]); return false; } } return true; }/*********************************************************************** * Unit test client. ***********************************************************************/ public static void main(String[] args) { LinearProbingHashST<String, Integer> st = new LinearProbingHashST<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)); }} |
No comments:
Post a Comment