Accelerating hashing

Revision en1, by Kinderr, 2017-03-30 17:19:53

The classical hashing way of hashing a number is keeping it as the reminder of the division with two distinct prime numbers i.e. hash(X) = (X mod prime1, X mod prime2), same thing with strings (considering them as polynomials). But modulo is a very heavy operation, and using a power of 2 (e.g. 2^64, using unsigned long long overflow) instead of a prime number fails when you hash a Thue-Morse sequence, so... Do you know any way of replacing the modulo with a smart bitwise operation or something else? I'd find it extremely useful :)

Tags hash, number theory

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English Kinderr 2017-03-30 17:21:15 2
en1 English Kinderr 2017-03-30 17:19:53 617 Initial revision (published)