Thread: Integer Hashing Function

  1. #1
    Registered User
    Join Date
    Dec 2010
    Posts
    2

    Integer Hashing Function

    Hi,

    I'm looking for a fast function that will take three signed integers as parameters and return a floating point number from -1.0 to 1.0. The function prototype I'd like to use is:

    double int_hash(int32_t x, int32_t y, int32_t z);

    The function should always return the same value for a given set of inputs, but adjacent inputs should return very different results. For example, int_hash(1,2,3) should produce a very different result than int_hash(1,2,4).

    I've tried using a plethora of different implementations that fit that definition - simple shift functions, the examples from the 'Random Numbers' section of 'Numerical Recipes in C', and others and they all seem to produce output that when mapped to an image are clearly not very random. The only class of functions that I've found that work well are true hash functions, like MD5, SHA1 and Paul Hsieh's hash function. However, these full-on hash functions are very slow. Using one of the weaker hashes, my program takes 5-10 seconds to run. Using Hsieh, it takes about 60 seconds, and MD5 and SHA take even longer.

    So, my question is:

    Does anyone know of a very fast integer hash function that output something somewhere between the "weak" outputs of the more simple algorithms and the cryptographically-secure values of SHA1 and MD5?

  2. #2
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    38,658
    Does the sign of the hash have anything to do with the sign of the inputs? Like say 3 positive integers can produce a negative result?

    Why +/- 1.0 instead of 0 to 2.0 ?
    Except that it gives you 25 bits of result (1 sign + 24 mantissa) rather than just 24 bits.

    Are the integers all full 32 bit (or do they have a sub-range)?
    Noting that at present, you appear to be compressing 96 bits into 24 bits.

    Rather than doing the full SHA1, why not take the code and just run it for say 5 rounds (rather than the full 80). If you don't care about the "crypto" which comes with all the rounds, but you get the mixing you need in a limited number of rounds, then it might work for you.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

  3. #3
    Registered User
    Join Date
    Dec 2010
    Posts
    2

    Integer Hashing Function

    Quote Originally Posted by Salem View Post
    Does the sign of the hash have anything to do with the sign of the inputs? Like say 3 positive integers can produce a negative result?

    Why +/- 1.0 instead of 0 to 2.0 ?
    Except that it gives you 25 bits of result (1 sign + 24 mantissa) rather than just 24 bits.

    Are the integers all full 32 bit (or do they have a sub-range)?
    Noting that at present, you appear to be compressing 96 bits into 24 bits.

    Rather than doing the full SHA1, why not take the code and just run it for say 5 rounds (rather than the full 80). If you don't care about the "crypto" which comes with all the rounds, but you get the mixing you need in a limited number of rounds, then it might work for you.
    No, the signs of the input do not have to be directly correlated to the sign of the output. 1,1,1 can produce a negative and 1,2,3 can produce a positive - that's fine (and actually good).

    -1.0 to 1.0 or 0.0 to 2.0 would be fine. (I can always to 1.0 - f(x,y,z) to get the proper range).

    The first two integers can be the full 32-bits, but initially they will be primarily in the range of about -10,000 - 10,000. The last integer will generally be a positive six digits, but ultimately can be anything.

    I could do an abbreviated SHA. I'll try that.

    It occurs to me that I should make a test suite that runs my algorithm with each of the different hash functions I've tried and produces an output image, and then post the results of that somewhere to better illustrate the lack of randomness that I'm talking about. I'll try to get that done this weekend, although we have a holiday party today so I'm not sure that will happen.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Compiling C in Visual Studio 2005
    By emanresu in forum C Programming
    Replies: 3
    Last Post: 11-16-2009, 04:25 AM
  2. Link List math
    By t014y in forum C Programming
    Replies: 17
    Last Post: 02-20-2009, 06:55 PM
  3. Compiling sample DarkGDK Program
    By Phyxashun in forum Game Programming
    Replies: 6
    Last Post: 01-27-2009, 03:07 AM
  4. We Got _DEBUG Errors
    By Tonto in forum Windows Programming
    Replies: 5
    Last Post: 12-22-2006, 05:45 PM
  5. Problem with Visual C++ Object-Oriented Programming Book.
    By GameGenie in forum C++ Programming
    Replies: 9
    Last Post: 08-29-2005, 11:21 PM