World's most popular travel blog for travel bloggers.

Choosing a non-cryptographic hash function for language with no unsigned integers

, , No Comments
Problem Detail: 

I'm implementing a hash table in pure UnrealScript, which only has support for signed 32-bit integers. This means no 64-bit integers and no unsigned integers. I was in the middle of implementing an FNV hash function, but ran into a potential problem.

The offset_basis for FNV-1 is dependent on n, the size of the hash: 32 bit offset_basis = 2166136261

Well, 2166136261 converts to -2128831035 when the bits are turned into an signed integer representation. My question is whether or not this will negatively affect the hash distribution and result in more collisions.

For quick reference, here is the psuedo-code for the FNV hash:

hash = offset_basis for each octet_of_data to be hashed     hash = hash * FNV_prime     hash = hash xor octet_of_data return hash 

Thank you for your time.

Asked By : Colin Basnett
Answered By : D.W.

The offset is unlikely to matter. As the FNV web page says:

almost any offset_basis will serve so long as it is non-zero

The multiplication is potentially more important. The FNV-1 hash is defined to use unsigned multiplication modulo $2^{32}$, but if UnrealScript only has signed 32-bit integers, presumably you have no way to do that kind of unsigned multiplication. At that point you're no longer using the official FNV-1 hash; you're using something different. I suspect it's still fine, though.

Best Answer from StackOverflow

Question Source :

3200 people like this

 Download Related Notes/Documents


Post a Comment

Let us know your responses and feedback