Algorithms For Dummies

 

»

Open addressing: The code stores the value in the next open slot by looking 

through the slots sequentially until it finds an open slot to use. The problem 

with this approach is that it assumes an open slot for each potential value, 

which may not be the case. In addition, open addressing means that the 

search slows considerably after the load factor increases. You can no longer 

find the needed value on the first comparison.

 

»

Rehashing: The code hashes the hash value plus a constant. For example, 

consider the value 1,020 when working with a hash table containing 30 slots 

and a constant of 100. The hash value in this case is 22. However, if slot 22 

already contains a value, rehashing (

(22 + 100) % 30

) produces a new hash 

value of 2. In this case, you don’t need to search the hash table sequentially 

for a value. When implemented correctly, a search might still include a low 

number of comparisons to find the target value.