HASHING - Introduction to Java Programming: Comprehensive Version - page 1008

163 }
164
165

/** Hash function */

166 private int hash( int hashCode) {

hash

167 return supplementalHash(hashCode) & (capacity - 1 );

168 }
169
170 /** Ensure the hashing is evenly distributed */
171 private static int supplementalHash( int h) {
172 h ^= (h >>> 20 ) ^ (h >>> 12 );
173

supplementalHash

return h ^ (h >>> 7 ) ^ (h >>> 4 );

174 }
175
176 /** Return a power of 2 for initialCapacity */
177 private int trimToPowerOf2( int initialCapacity) {
178 int capacity = 1 ;
179 while (capacity < initialCapacity) {
180 capacity <<= 1 ; // Same as capacity *= 2. <= is more efficient
181 }
182
183

trimToPowerOf2

return capacity;

184 }
185
186 /** Remove all e from each bucket */
187 private void removeElements() {
188 for ( int i = 0 ; i < capacity; i++) {
189 if (table[i] != null ) {
190 table[i].clear();
191 }
192 }
193 }
194
195 /** Rehash the set */
196 private void rehash() {
197 java.util.ArrayList<E> list = setToList(); // Copy to a list
198 capacity <<= 1 ; // Same as capacity *= 2. <= is more efficient
199 table = new LinkedList[capacity]; // Create a new hash table
200 size = 0 ;
201
202 for (E element: list) {
203 add(element); // Add from the old table to the new table
204 }
205 }
206
207 /** Copy elements in the hash set to an array list */
208 private java.util.ArrayList<E> setToList() {
209 java.util.ArrayList<E> list = new java.util.ArrayList<>();
210
211 for ( int i = 0 ; i < capacity; i++) {
212 if (table[i] != null ) {
213 for (E e: table[i]) {
214 list.add(e);
215 }
216 }
217 }
218
219

rehash

setToList

return list;

220 }
221
222 @Override /** Return a string representation for this set */