A very simple variation on the middle-square method that alleviates its deficiencies is the so-called, multiplication hashing method . Instead of multiplying the key x by itself, we multiply the key by a carefully chosen constant a, and then extract the middle k bits from the result. In this case, the hashing function is
What is a suitable choice for the constant a? If we want to avoid the problems that the middle-square method encounters with keys having a large number of leading or trailing zeroes, then we should choose an a that has neither leading nor trailing zeroes.
Furthermore, if we choose an a that is
relatively prime
to W,
then there exists another number a' such that
.
In other words, a' is the inverse
of a modulo W,
since the product of a and its inverse is one.
Such a number has the nice property that if we take a key x,
and multiply it by a to get ax,
we can recover the original key by multiplying the product again by a',
since axa'=aa'x=1x.
There are many possible constants which the desired properties.
One possibility which is suited for 32-bit arithmetic (i.e., )
is
.
The binary representation of a is
This number has neither many leading nor trailing zeroes.
Also, this value of a and are relatively prime
and the inverse of a modulo W is
.
The following code fragment illustrates the multiplication method of hashing:
unsigned int const k = 10; // M==1024 unsigned int const w = bitsizeof (unsigned int); unsigned int const a = 2654435769U; unsigned int h (unsigned int x) { return (x * a) >> (w - k); }Note, this implementation assumes that