64-bit multiplicative hashing

I'm working on fast 64-bit hash. Many existing secure hash functions are too way slow, some non-cryptographic hash functions like FNV are just bad.

Well, I came up with a FNV-like hash:

开发者_开发知识库UINT64 hash=0;

// for each input byte
hash=(hash^(input_byte+1))*HASH_PRIME;

Main question is about HASH_PRIME. Often, we may see a "golden ratio" term for multiplicative hashing. For 64-bit hash, golden ratio is 0x9e3779b97f4a7c13.

I tested the 32-bit golden ratio for period in PRNG:

DWORD hash=0;
// loop
hash=(hash^1)*0x9e3779b9;
rnd_out=hash>>24;

A good value here may produce the period of 0xFFFFFFFF - i.e. max possible. This golden ratio produces notably smaller period.

or just

DWORD hash=~0;
// loop
hash*=0x9e3779b9;
rnd_out=hash>>24;

And again, a good enough multiplier can produce period of 0x3FFFFFFF bytes. Golden ratio here produces again much shorter period.

Never tested the 64-bit primes - too computationally expensive.

Is period important for my hash? And where to find a good 64-bit HASH_PRIMES and how to test such stuff?

---

Are you doing this is as an exercise? otherwise I would advise having a looking at well known hash functions as Bob Jenkin's lookup8 and lookup family (http://burtleburtle.net/bob/hash/ ) and Austin Appleby's murmur http://code.google.com/p/smhasher/ (a speed killer and my favorite). Good hash functions are hard to build... and if you are after a rolling type of hash, Rabin fingerprints are hard to beat. And to make sure that your hashes are decent if you really want to roll your own, use either Appleby and Jenkins hash tests (torture and smhasher )

---

Not sure about the first two examples. But in the third to get a full period out of the code you need to add an odd number. Otherwise this will have a maximum period of 65537, It could be as low as 3. There may even be a fixed point.

Wherever you got the 0x3FFFFFFF for a good period is not correct. One of the Knuth volumes discusses this in excessive detail.

The multiplier must be of the form 4n+1 and there must be an odd addend