Java Reference
In-Depth Information
Locating an open location in the hash table is called
probing
, and various probing techniques
are possible. With
linear probing
, if a collision occurs at
hashTable[k]
, we see whether
hashTable[k
+
1]
is available. If not, we look at
hashTable[k
+
2]
, and so on. The table locations
that we consider in this search make up the
probe sequence
. If a probe sequence reaches the end of
the hash table, it continues at the beginning of the table. Thus, we treat the hash table as if it were
circular: The first location in the table comes immediately after the last location.
Note:
Linear probing
resolves a collision during hashing by examining consecutive loca-
tions in the hash table—beginning at the original hash index—to find the next available one.
21.14
Additions that collide.
Recall the example illustrated in Figure 21-2. The search keys 555-1214
and 555-8132 both mapped into the index 52. Suppose that 555-4294 and 555-2072 also map into
that same index, and we make the following additions to an empty dictionary
addressBook
:
addressBook.add("555-1214", "150 Main Street");
addressBook.add("555-8132", "75 Center Court");
addressBook.add("555-4294", "205 Ocean Road");
addressBook.add("555-2072", "82 Campus Way");
The first addition would use
hashTable[52]
. The second addition would find
hashTable[52]
occupied,
and so it would probe ahead and use
hashTable[53]
. The third addition would find both
hashTable[52]
and
hashTable[53]
occupied, and so it would probe ahead and use
hashTable[54]
. Finally, the fourth
addition would probe the locations at indices 52, 53, and 54 before using
hashTable[55]
for the addition.
Figure 21-3 shows the result of these additions to the hash table.
FIGURE 21-3
The effect of linear probing after adding four entries whose
search keys hash to the same index
h
(555-1214)
h
(555-8132)
h
(555-4294)
h
(555-2072)
52
150 Main Street
53
75 Center Court
54
205 Ocean Road
55
82 Campus Way
56
null
Hash table
Note:
Linear probing can examine every location in a hash table. As a result, this type of
probing ensures the success of the
add
operation as long as the hash table is not full.
