Multiplication Method

Data Structures and Algorithms with Object-Oriented Design Patterns in C#

Multiplication Method

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:

public class MultiplicationMethod
{
    private const int k = 10; // M==1024
    private const int w = 32;
    private const uint a = 2654435769U;

    public static int H(int x)
	{ return (int)((uint)(x * a) >> (w - k)); }
}

The code is a simple modification of the middle-square version. Nevertheless, the running time remains O(1).