Multiplicative method

The multiplicative method is a scheme according to which hash functions can be developed. The product of the key is formed with a number and the integer part is cut off so that the key is mapped into the interval . The result is multiplied by the number of hash table addresses and rounded down. In formula notation, a hash function that implements the multiplicative method is defined as: ${\ displaystyle A}$ ${\ displaystyle [0,1]}$ ${\ displaystyle m}$ ${\ displaystyle h}$

{\ displaystyle h (k) = \ left \ lfloor m \ cdot \ left (kA {\ bmod {1}} \ right) \ right \ rfloor = \ left \ lfloor m \ cdot \ left (kA- \ left \ lfloor kA \ right \ rfloor \ right) \ right \ rfloor, \ qquad 0 <A <1}

algorithm

With this method, the choice of , which is independent of the choice of, is decisive for the distribution of the keys to the address range of the hash table . In the literature, the golden ratio is suggested for a good choice of , with which in practice with a lot of typical input data the distribution of the hash values of the keys is almost evenly distributed . If this number is used, the resulting hash function is also called the Fibonacci hash . ${\ displaystyle A}$ ${\ displaystyle m}$ ${\ displaystyle A}$

${\ displaystyle A = \ Phi ^ {- 1} = {\ frac {{\ sqrt {5}} - 1} {2}} \ approx 0 {,} 6180339887 \ ldots}$

The multiplicative method can be seen as a generalization of the residual division method . If you put it so is ${\ displaystyle A = {\ frac {1} {m}}}$

${\ displaystyle h (k) = \ left \ lfloor m \ left (k {\ frac {1} {m}} - \ left \ lfloor k {\ frac {1} {m}} \ right \ rfloor \ right) \ right \ rfloor = \ left \ lfloor m \ left (\ left (k {\ frac {1} {m}} \ right) \ {\ bmod {\}} 1 \ right) \ right \ rfloor = \ left \ lfloor m {\ frac {(k \ {\ bmod {\}} m)} {m}} \ right \ rfloor = k \ {\ bmod {\}} m}$

In the theory of hashing, by distributing the keys equally to the addresses in the hash table, an attempt is usually made to distribute the keys evenly across the table and thereby minimize collisions.

The equal distribution is a random experiment with the probability when there is an elementary event and the number of elementary events , e.g. B. the coin toss or the dice . ${\ displaystyle P (\ omega) = {\ frac {1} {n}}}$ ${\ displaystyle \ omega}$ ${\ displaystyle n}$ ${\ displaystyle p = {\ frac {1} {2}}}$ ${\ displaystyle p = {\ frac {1} {6}}}$

The golden ratio is an irrational number ; H. it is off , and it achieves a good distribution of the keys over the address range of the hash table through the following property of irrational numbers: ${\ displaystyle \ mathbb {R} \ setminus \ mathbb {Q}}$

Be an irrational number. If you place the points in the interval , then the interval parts have at most three different lengths. In addition, the next point,, falls in one of the largest parts of the interval. ${\ displaystyle A}$ ${\ displaystyle A- \ lfloor A \ rfloor, 2A- \ lfloor 2A \ rfloor, 3A- \ lfloor 3A \ rfloor, \ ldots, nA- \ lfloor nA \ rfloor}$ ${\ displaystyle [0,1]}$ ${\ displaystyle n + 1}$ ${\ displaystyle (n + 1) A- \ lfloor (n + 1) A \ rfloor}$

Every periodic decimal fraction or dual fraction represents a rational number. Natural or rational numbers with a finite number of digits, e.g. B. are 0-periodic, i.e. H. the remaining infinite digits are set equal to 0. ${\ displaystyle {\ frac {1} {2}} = 0 {,} 5}$

Every irrational number can only be represented by a non-periodic infinite decimal fraction or dual fraction. If it is off , it can be represented as the limit value of a - -dic fraction. ${\ displaystyle A}$ ${\ displaystyle \ mathbb {R} \ setminus \ mathbb {Q}}$ ${\ displaystyle b}$ ${\ displaystyle a}$

The equal distribution and the golden ratio can therefore only be calculated approximately using algorithms.

rating

The equal distribution can only be achieved insufficiently, and as a result the keys, especially of well-sorted sets (e.g. 1, 2, 3, ...), are distributed unevenly over the hash table, which can result in long chains and empty address spaces and thus slower access to the data.

The golden ratio can be calculated precisely to any number of places and thus approximated well, but has the problem that evenly distributed quantities are not optimally distributed over the hash table, since, according to Vera Turan Sós' theorem, only well-sorted quantities are optimally distributed between . ${\ displaystyle [0,1]}$

Since one generally finds neither uniformly distributed nor sorted quantities in practice, the golden ratio is a good choice for the multiplicative method.

Lum, Yuen and Dodd compared the behavior of different hash functions and found that the residual division method does not produce any worse results than other hash functions.

implementation

For example, be with . Then is . ${\ displaystyle A = b / w = ({\ sqrt {5}} - 1) /2=0.6180339887}$ ${\ displaystyle w = 2 ^ {32}}$ ${\ displaystyle s = 2654435769}$

Then the associated multiplicative hash function is ${\ displaystyle h}$

${\ displaystyle h (k) = \ left \ lfloor m ({\ frac {ks} {w}} {\ bmod {1}}) \ right \ rfloor = \ left \ lfloor m {\ frac {ks {\ bmod {w}}} {w}} \ right \ rfloor}$

where with denotes the hash table size and with denotes a key value. ${\ displaystyle m}$ ${\ displaystyle 0 <m <2 ^ {32} -1}$ ${\ displaystyle k}$ ${\ displaystyle 0 \ leq k <2 ^ {32}}$

A general implementation in the C programming language :

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <inttypes.h>

static const double s = 2654435769.0,  w = 4294967296.0;

uint32_t mult_hash(uint32_t k, uint32_t m)
{
  return (uint32_t) floor( ( (double) m * fmod( s * (double) k, w) ) / w );
}

int main(int argc, char **argv)
{
  uint32_t l = mult_hash(atoi(argv[1]), 1024);
  printf("%" PRIu32 "\n", l);
  return 0;
}

If you choose a power of two, the algorithm can be implemented much more efficiently: ${\ displaystyle m = 2 ^ {i}}$

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <inttypes.h>

static const uint32_t s = 2654435769;

uint32_t mult_hash(uint32_t kk, uint32_t i)
{
  uint64_t k = kk;
  uint64_t t = s * k & 0x00000000FFFFFFFF;
  return t >> (32 - i);
}

int main(int argc, char **argv)
{
  uint32_t l = mult_hash(atoi(argv[1]), 10);
  printf("%" PRIu32 "\n", l);
  return 0;
}

literature

Donald E. Knuth : The Art of Computer Programming . 3. Edition. Volume 2. Addison-Wesley, 1998, ISBN 0-201-89684-2 , pp. 70 ff .
Donald E. Knuth : The Art of Computer Programming . 2nd Edition. Volume 3. Addison-Wesley, 1998, ISBN 0-201-89685-0 , pp. 516 ff .
Cormen et al .: Introduction to Algorithms . 2nd Edition. MIT Press, 2001, ISBN 0-262-03293-7 , pp. 231 ff .
William H. Press, Saul A. Teukolsky, William T. Vetterling, Brian P. Flannery: Numerical Recipes in C ++ / The Art of Scientific Computing . Cambridge University Press, 2nd edition, 1988.

Individual evidence

^ Donald E. Knuth: The Art of Computer Programming / Sorting and Searching . Volume 3. Addison-Wesley, Massachusetts, 2nd edition, 1997; Page 516
↑ Thomas Ottmann, Peter Widmayer: Algorithms and Data Structures . second edition. BI Wissenschaftsverlag, Mannheim / Leipzig / Vienna / Zurich 1993
↑ ^a ^b Vera Turan Sós (Acta Math. Acad. Sci. Hung. 8 (1957), 461–471)
↑ VY Lum, PST Yuen, M. Dodd: Key-to-address transform techniques: Performance study on large existing formatted files . In: Communications of the ACM , 14 (4), April 1971, pp. 228-239.

[1] Donald E. Knuth: The Art of Computer Programming / Sorting and Searching . Volume 3. Addison-Wesley, Massachusetts, 2nd edition, 1997; Page 516

[2] Thomas Ottmann, Peter Widmayer: Algorithms and Data Structures . second edition. BI Wissenschaftsverlag, Mannheim / Leipzig / Vienna / Zurich 1993

[sos-3] Vera Turan Sós (Acta Math. Acad. Sci. Hung. 8 (1957), 461–471)

[4] VY Lum, PST Yuen, M. Dodd: Key-to-address transform techniques: Performance study on large existing formatted files . In: Communications of the ACM , 14 (4), April 1971, pp. 228-239.