Hashing - Advanced Topics in Java: Core Concepts in Data Structures - page 287

Now, when searching, we still check for the key or an empty location; deleted locations are ignored. A common
error is to stop the search at a deleted location; doing so would lead to incorrect conclusions.
If our search reveals that an incoming key is not in the table, the key can be inserted in an empty location or a deleted
one, if one was encountered along the way. For example, suppose we had deleted 43 by setting num[8] to -1 . If we now
search for 55 , we will check locations 8 , 9 , 10 , and 11 . Since num[11] is empty, we conclude that 55 is not in the table.
We can, if we want, set num[11] to 55 . But we could write our algorithm to remember the deleted location at 8 .
If we do, we can then insert 55 in num[8] . This is better since we will find 55 faster than if it were in num[11] . We would
also be making better use of our available locations by reducing the number of deleted locations.
What if there are several deleted locations along the way? It is best to use the first one encountered since this will
reduce the search time for the key. With these ideas, we can rewrite our search/insert algorithm as follows:

//find or insert 'key' in the hash table, num[1..n]
loc = H(key)
deletedLoc = 0
while (num[loc] != Empty && num[loc] != key) {
if (deletedLoc == 0 && num[loc] == Deleted) deletedLoc = loc
loc = loc % n + 1
}

if (num[loc] == Empty) { //key not found
if (deletedLoc != 0) loc = deletedLoc
num[loc] = key
}
else print key, " found in location ", loc

Note that we still search until we find an empty location or the key. If we meet a deleted location and deletedLoc
is 0 , this means it's the first one. Of course, if we never meet a deleted location and the key is not in the table, it will be
inserted in an empty location.

10.3 Resolving Collisions
In Program P10.1, we resolve a collision by looking at the next location in the table. This is, perhaps, the simplest way
to resolve a collision. We say we resolve the collision using linear probing , and we will discuss this in more detail in
the next section. After this, we will take a look at more sophisticated ways of resolving collisions. Among these are
quadratic probing , chaining , and double hashing .

10.3.1 Linear Probing
Linear probing is characterized by the statement loc = loc + 1 . Consider, again, the state of num after the nine
numbers have been added:

num

84 23 61 52 16 43 31 33 59

1

2 3 4 5 6 7 8 9 10 11 12

As you can see, the chances of hashing a new key to an empty location decreases as the table fills up.
Suppose a key hashes to location 12 . It will be placed in num[4] after trying locations 12 , 1 , 2 , and 3 . In fact, any new
key that hashes to 12 , 1 , 2 , 3 , or 4 will end up in num[4] . When that happens, we will have a long, unbroken chain of keys
from location 12 to location 6 . Any new key hashing to this chain will end up in num[7] , creating an even longer chain.