Key Offset

Key offset is a double hashing method that produces different collision paths for different keys. Whereas the pseudorandom number generator produces a new address as a function of the previous address, key offset calculates the new address as a function of the old address and the key. One of the simplest versions simply adds the quotient of the key divided by the list size to the address to determine the next collision resolution address, as shown in the formula below.

Offset = key/listSize
address = ((offset + old address) modulo listSize)

For example, when the key is 166703 and the list size is 307, using the modulo-division hashing method we generate an address of 1. As shown in Figure 11, this synonym of 070919 produces a collision at address 1. Using key offset to calculate the next address, we get 237, as shown below.

Offset = 166703/307 = 543
address = ((543 + 001) modulo 307)= 237


If 237 were also a collision, we would repeat the process to locate the next address, as shown below.

Offset = 166703/307 = 543
address = ((543 + 237) modulo 307)= 166

To really see the effect of key offset, we need to calculate several different keys, all hashing to the same home address. In Table 2. We calculate the next two collision probe addresses for three keys that collide at address 001.