demerphq

I think you have confused "ideal hash function" and "perfect hash function". A perfect hash function is one that maps a finite set of keys into the same number of buckets with no collisions. They have to be tailor constructed for the keys they are intended for and are not for general purpose use.

An ideal hash function on the other hand produces output that is indistinguishable from choosing the hash value for every key independently and randomly. In particular an ideal hash function should be a PRF, and it should handle any input size, and any keyset.

They aren't the same thing at all, and you should not confuse them. You cannot substitute an ideal hash function for a perfect hash function, or vice versa.

ArashPartow

@demerphq (Yves Orton):

> "They aren't the same thing at all, and you should not confuse them. "

You're absolutely right. The term "idea hash function" was what I was after all along - I just couldn't find a formal definition of it. In any case I've updated the article accordingly. Thank-you for your review and comment.

demerphq
You are welcome. I wanted add another point. rurban does have a bit of a point. The hash functions you referenced in your article are generally old and low quality, and slow. FNV is neither a good hash, nor is it fast. FNV_yt is very fast, but not the best quality hash function, it fails many tests in SMHasher, including some I personally consider dealbreaker: failing avalanche tests is unacceptable.

Both rurban and I have (independently) spent considerable time testing about 100 hash functions using the hash test suite smhasher. In addition I have greatly enhanced smhasher, and included test results and graphs in my version. Included in my fork is the --stream option so you can test different hash functions in counter mode with tools like the dieharder RNG test suite.

https://github.com/demerphq/smhasher https://github.com/rurban/smhasher

These are the FNV test results from my version of SMHasher:

FNV1a 32 32 32 FAILED 99 of 183 tests. Avalanche: 17-41, Crc-MultiCollision: 81, 83, 85-86, 88-91, 94, 96-98, 100, Cyclic: 42-52, Hi-Lo: 157-158, HiBit-Null: 150-152, Highbits2: 147-149, Highbits: 144-146, LowBit-Null: 153-155, Lowbits: 142-143, Murmur2-MultiCollision: 101-110, Murmur3A-MultiCollision: 111, 113, 117, 119-120, Murmur3F-MultiCollision: 122-127, 129-130, OverAll: 183, Text: 160-165, TwoBytes: 54-56, 63, Zeroes: 167-168

FNV1a_YT 32 32 32 FAILED 67 of 181 tests. Avalanche: 15-39, Differential: 9-14, Hi-Lo: 154-156, HiBit-Null: 148-150, Highbits2: 145-147, Highbits: 142-144, Lowbits: 139-141, OverAll: 181, Sparse: 74-78, Text: 157-158, 160-163, TwoBytes: 51, 53-61

FNV64 64 64 64 FAILED 66 of 183 tests. Avalanche: 17-41, Cyclic: 43-45, 47, 49, 51-52, Hi-Lo: 157-158, HiBit-Null: 151-152, Highbits2: 148-149, Highbits: 145-146, LowBit-Null: 154-155, Lowbits: 142-143, OverAll: 183, Sparse: 65-67, 69, 71, 73, 75, 77, 79-80, Text: 160-162, 164-165, TwoBytes: 54-56, 58, 60, 62-63, Words: 182, Zeroes: 167-168

You can see text view of the full list at:

https://github.com/demerphq/smhasher/blob/master/doc/summary...

Also after reading this thread I added some graphs comparing performance of other hashes, including some that I have developed using genetic algorithm for use in Perl. Some of those hashes have hash-time performance at the top of the envelope (StadtX is very fast).

https://github.com/demerphq/smhasher/blob/master/doc/graph/F... https://github.com/demerphq/smhasher/blob/master/doc/graph/F... https://github.com/demerphq/smhasher/blob/master/doc/graph/F... https://github.com/demerphq/smhasher/blob/master/doc/graph/F...

You may also be interested in looking at

https://github.com/demerphq/smhasher/blob/master/HashAnatomy...

Good luck!