In our open-address hash tables, we have used linear probing or double hashing. Another probing method, which avoids some clustering, is called quadratic probing. The simplest version of quadratic probing works like this: Start by hashing the key to an array index. If there is a collision, then move to the next array index. If there is a second collision, then move forward two more spots through the array. After a third collision, move forward three more spots, and so on. For example, suppose a new key hashes to location 327 and this location is full. The next location we try is 328. If 328 is a second collision, then we move two spots forward to location 330. If 330 is a third collision, then we move three spots forward to location 333. If our calculation of the next spot takes us beyond the end of the array, then we “wrap around” to the front of the array (similar to double hashing). In general, if location i has just caused a collision and we have already examined count elements, then we increase i according to the assignment:

i = (i + count) % data.length;

In this formula, the “% data.length” causes the “wraparound” to the front of the array. For this approach to work correctly, the capacity must be a power of 2, such as 210 = 1024. Otherwise, the sequence of probes does not correctly examine all array items.

For this project, use quadratic hashing to reimplement the hash table from Figure 11.5 on page 592.

Transcribed Image Text:

public boolean containskey(K key) || See the answer to Self-Test Exercise 5. private int findIndex (K key) // Postcondition: If the specified key is found in the table, then the return // value is the index of the specified key. Otherwise, the return value is - 1. int count - 0; int i - hash(key); while ((count < data.length) && (hasBeenUsed[i])) { if (key.equals(keys[i])) return i; count++; i = nextIndex(i); } %3! return -1; } // See the warnings discussion on page 265 @SuppressWarnings ("unchecked") public E get(K key) { int index = findIndex (key); if (index == -1) return null; else return (E) data[index]; } private int hash (Object key) // The return value is a valid index of the table's arrays. The index is // calculated as the remainder when the absolute value of the key's // hash code is divided by the size of the table's arrays. { return Math.abs (key.hashCode( )) % data.length; }