4 ms·

@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 wh

@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 10y ago
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/demerphq/smhasher https://github.com/rurban/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.txt 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/FNV_Comparison.long.svg https://github.com/demerphq/smhasher/blob/master/doc/graph/F... https://github.com/demerphq/smhasher/blob/master/doc/graph/FNV_Comparison.medium.svg https://github.com/demerphq/smhasher/blob/master/doc/graph/F... https://github.com/demerphq/smhasher/blob/master/doc/graph/FNV_Comparison.short.svg https://github.com/demerphq/smhasher/blob/master/doc/graph/F... https://github.com/demerphq/smhasher/blob/master/doc/graph/FNV_Comparison.tiny.svg 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.md https://github.com/demerphq/smhasher/blob/master/HashAnatomy... Good luck!
- andai 10y ago
  Wow! How did you create BeagleHash? I took a look at your repos but could only find the end result.
  - demerphq 10y ago
    BeagleHash IMO is less interesting than Zaphod64 and StadtX. With all of them I used genetic algorithm techniques to search the space of possible minimal mix functions to find ones that minimized error from the strict avalanche test. I will publish my tooling to do this at one point, but it is a bit hacky to release just now.
- ot 10y ago
  Thanks for saying this! It is incredible how widespread still is the belief that FNV is a good hash function, when much better ones exist that are faster even on short keys.
  - demerphq 10y ago
    I am only repeating what my tests say. I was surprised frankly, given FNV's reputation, to see it fail so many tests. Also I put a lot of effort into improving the quality of testing that smhasher does, so there are many hashes that would pass the old version which will fail the new one.
- ArashPartow 10y ago
  @demerphq: Thank-you for these stats, and the links. I'll definitely be updating the article with the missing hash functions and adding some of the links you've provided to the links section. My intent is to over time make the article as comprehensive as possible, but to also keep it accessible to the general public.

demerphq 10y ago

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/demerphq/smhasher https://github.com/rurban/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.txt 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/FNV_Comparison.long.svg https://github.com/demerphq/smhasher/blob/master/doc/graph/F... https://github.com/demerphq/smhasher/blob/master/doc/graph/FNV_Comparison.medium.svg https://github.com/demerphq/smhasher/blob/master/doc/graph/F... https://github.com/demerphq/smhasher/blob/master/doc/graph/FNV_Comparison.short.svg https://github.com/demerphq/smhasher/blob/master/doc/graph/F... https://github.com/demerphq/smhasher/blob/master/doc/graph/FNV_Comparison.tiny.svg 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.md https://github.com/demerphq/smhasher/blob/master/HashAnatomy... Good luck!

andai 10y ago
Wow! How did you create BeagleHash? I took a look at your repos but could only find the end result.
- demerphq 10y ago
  BeagleHash IMO is less interesting than Zaphod64 and StadtX. With all of them I used genetic algorithm techniques to search the space of possible minimal mix functions to find ones that minimized error from the strict avalanche test. I will publish my tooling to do this at one point, but it is a bit hacky to release just now.
ot 10y ago
Thanks for saying this! It is incredible how widespread still is the belief that FNV is a good hash function, when much better ones exist that are faster even on short keys.
- demerphq 10y ago
  I am only repeating what my tests say. I was surprised frankly, given FNV's reputation, to see it fail so many tests. Also I put a lot of effort into improving the quality of testing that smhasher does, so there are many hashes that would pass the old version which will fail the new one.
ArashPartow 10y ago
@demerphq: Thank-you for these stats, and the links. I'll definitely be updating the article with the missing hash functions and adding some of the links you've provided to the links section. My intent is to over time make the article as comprehensive as possible, but to also keep it accessible to the general public.