70 mod 10 = 0
80 mod 10 = 0
120 mod 10 = 0
all keys hash to the same value
then h ( k ) = k mod 2b
just extracts the bottom b bits from k
Rule of thumb -- select table size
such that table is never more than 80% full
Let Mmin = expected-number-of-entries / 0.8
Choose M = smallest prime > Mmin
where A is some real positive constant.
note that ( k * A - |_ k * A _| ) is between 0.0 and
1.0
golden ratio Ø =
( 1 + sqrt (5) ) / 2 = 1.618033989....
so Ø-1 = 1 / 1.618033989...
= 0.618033989
h ( k ) = |_ M * ( k * Ø-1 - |_ k * Ø-1 _| ) _|
Some values for k and h ( k )
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|