CODEWITHSUNDEEP
algorithmdouble-hashing
tobi
tobi

Reputation: 2002

Double hashing in open addressing, what hash function and table length

In Cormen's book "Introduction to algorithms" I read that double hashing (in open addressing) function is in the form of:

h(k, i) = (h1(k) + i * h2(k)) mod m

where k is a key, i is a next index in the case of a collision, m is the table length and hX are hash functions.

He says that the main problem in double hashing is to utilize all indices in the table. To solve that problem we should set m to the power of 2 and h2 function should return odd values. Why (I can't see him explaining it)?

Upvotes: 0

Views: 729

Answers (1)

btilly
btilly

Reputation: 46408

The general rule is that modulo m, adding h_2(k) repeatedly is a cycle that repeats with period m/GCD(m, h_2(k)). If there are no common factors between m and h_2(k) then it will repeat with period m which means that you can reach all m indices. So you want no common factors.

The "no common factors" rule is easily satisfied by making m a power of 2 and h_2(k) odd.

Upvotes: 2

Related Questions