• Advertisement
Sign in to follow this  

Hash value for an int array?

This topic is 2647 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

(This may be better placed under math and physics, but I put it here in case it doesn't get too deep in the math weeds... we'll see how it goes.)

I have some objects that have 2 arrays of values associated with them. To calculate a unique value for these objects I am doing something like this:


UINT32 hash1 = 0;
for (int i = 0; i < list1Size; i++)
hash1 = hash1 * PRIME_NUMBER + i;

UINT32 hash2 = 0;
for (int i = 0; i < list2Size; i++)
hash2 = hash2 * PRIME_NUMBER + i;

UINT64 objectHash = (UINT64)(hash1) << 32 + hash2;


Obviously, not very sophisticated, but it seems to work well and from what little I've found it seems to be a favored approach and people seem to think it produces well-mixed results. It seemed like the combination of 2 values in the upper/lower 32-bits of a UINT64 would make collisions even less likely.

Questions:

1) Is there a name for this technique? (meaning the "val * PRIME + a[i]" approach)? I'd like some solid answers for people who want to know how well distributed the outputs are. Something better than "its this thing I found on the internet" would be great! :-)

2) Is there a better technique that is not significantly slower?

Share this post


Link to post
Share on other sites
Advertisement
There's an obvious issue with your hash - if the data is all zeros, then the result will be zero regardless of the length of the data. That can be worked around by starting with a non-zero initial value.

However, why not go for a well known good hash like one of the better ones that are compared here.

Share this post


Link to post
Share on other sites
Yes, sorry, I just typed the example too quickly... I actually seed it with a prime number. Turns out, this is basically the djb2 hash function.

Thanks for the link!

Share this post


Link to post
Share on other sites
These hashes work well

http://isthe.com/chongo/tech/comp/fnv/

Make sure you read the info there before using them. It's important that the hash is "XOR folded", which allows all the bits to contribute to the result in the likely case where your hash is smaller than 32 bits.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement