Pseudorandom (MAD) Collision Resolution

This method uses a pseudorandom number to resolve the collision. We saw the pseudorandom number generator as a hashing method in “Pseudorandom Method”. We now use it as a collision resolution method. In this case, rather than using the key as a factor in the random number calculation, we use the collision address. Consider the collision we created in Figure 10. We now resolve the collision using the following pseudorandom number generator, where a is 3 and c is 5 :

y = (ax + c) modulo listSize
= (3 x 1 + 5) Modulo 307
= 8, next addresses are 29, 92, and so on

In this example, we resolve the collision by placing the new data in element 008 (Figure 11). Pseudorandom numbers are a relatively simple solution, but they have one significant limitation: All keys follow only one collision resolution path through the list. (This deficiency also occurs in the linear and quadratic probes.) Because pseudorandom collision resolution can create significant secondary