I want to map a set of long integers (say around 100 different values) that can span the entire 64 bit integer range to a much smaller range such as from 0 to 25000 deterministically with almost zero collisions. This operation has to be very fast as well.

Please not that, generating random numbers in the expected range is not a solution, as the original numbers are created by an external system.

EDIT: Would a pairing function such as following qualify above criteria. From this article, it seem to qualify, but I would like some expert advice. http://en.wikipedia.org/wiki/Pairing_function


  • $\begingroup$ Does the "deterministically" part rule out universal hashing? $\;$ $\endgroup$ – user991 May 6 '15 at 9:52
  • $\begingroup$ I am not familiar with universal hashing, but if this involves picking up the hashing function based on data, it might, as in my case the order in which the system encounter original Numbers may differ. $\endgroup$ – user3612009 May 6 '15 at 10:42
  • $\begingroup$ It specifically can avoid picking the hashing function based on data. $\;$ $\endgroup$ – user991 May 6 '15 at 10:49
  • 1
    $\begingroup$ If you know the 100 different integers beforehand, this is known as "perfect hashing"; google for that $\endgroup$ – poncho May 6 '15 at 12:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.