Hash function: Difference between revisions

Revision as of 00:14, 15 May 2025

Revision as of 13:52, 23 May 2025

Line 154:

=== Multiplicative hashing ===

Standard multiplicative hashing uses the formula {{Math|1=''h''_''a''(''K'') = {{floor|(''aK'' mod ''W'') / (''W''/''M'')}}}}, which produces a hash value in {{Math|{{mset|0, …, ''M'' − 1}}}}. The value {{Mvar|a}} is an appropriately chosen value that should be [[Coprime integers|relatively prime]] to {{Mvar|W}}; it should be large,{{Clarify|reason=How large?|date=January 2021}} and its binary representation a random mix{{Clarify|reason="a" is a constant, so it cannot be random|date=January 2021}} of 1s and 0s. An important practical special case occurs when {{Math|1=''W'' = 2^''w''}} and {{Math|1=''M'' = 2^''m''}} are powers of 2 and {{Mvar|w}} is the machine [[word size]]. In this case, this formula becomes {{Math|1=''h''_''a''(''K'') = {{floor|(''aK'' mod 2^''w'') / 2^{''w''−''m''}}}}}. This is special because arithmetic modulo {{Math|2^''w''}} is done by default in low-level programming languages and integer division by a power of 2 is simply a right-shift, so, in [[C (programming language)|C]], for example, this function becomes

<syntaxhighlight lang="c">

unsigned hash(unsigned K) {

return (a * K) >> (w - m);

}

</syntaxhighlight>

and for fixed {{Mvar|m}} and {{Mvar|w}} this translates into a single integer multiplication and right-shift, making it one of the fastest hash functions to compute.

Multiplicative hashing is susceptible to a "common mistake" that leads to poor diffusion&mdash;higher-value input bits do not affect lower-value output bits.<ref>

{{cite web |url=http://www.cs.cornell.edu/courses/cs3110/2008fa/lectures/lec21.html |title=CS 3110 Lecture 21: Hash functions |at=Section "Multiplicative hashing"}}</ref> A transmutation on the input which shifts the span of retained top bits down and XORs or ADDs them to the key before the multiplication step corrects for this. The resulting function looks like:<ref name="fibonacci-hashing"/>

<syntaxhighlight lang="c">

unsigned hash(unsigned K) {

K ^= K >> (w-m);

returnK ^= (a*K) >> (w - m);

Kreturn ^=(a * K) >> (w - m);

}

</syntaxhighlight>

=== Fibonacci hashing ===