Hacker News new | past | comments | ask | show | jobs | submit login
Prospecting for Hash Functions (nullprogram.com)
116 points by abbeyj on Aug 2, 2018 | hide | past | favorite | 14 comments



I think a non-cryptographic hash function which leverages AES-NI instructions (e.g. by performing one round of AES using a fixed key) will perform better in every possible way: high avalanche effect, low bias AND possibly better performance.


Go does this for its native map (dictionary) type. https://codereview.appspot.com/7543043


A fun exercice would be to compare this to SipHash.


The problem is that AES-NI instructions have high throughput, but also high latency, 4 to 8 cycles.

It also means that your hash is basically incompatible with any platform that does not implement AES-NI instructions, as it will be excruciatingly slow.


It will be slow, but will still be compatible.


It also has the advantage of being capable of generating a family of independent hash functions. There are a lot of algorithms which require multiple hash functions to work correctly.


falkhash[0] does this.

[0] https://github.com/gamozolabs/falkhash


Really cool project! This is a wonderful way to approach a problem. Before thinking too hard about it, cleverly applying the brute strength of the machine and saving a lot of work. I'd read more posts like this


This article is about finding non-crypto hash functions that will be implemented on a general-purpose computer. Quite a lot of people have written on that subject. A different question is how to implement a non-crypto hash function in hardware; I only know about one paper on that, from 2011: "Non-crypto hardware hash functions for high-performance networking ASICs". Perhaps crypto accelerators are sufficiently fast and sufficiently widely available on different architectures that they should be used instead in most cases?


Makes you wonder how the constants for the winning hash functions were chosen... (The 32/64 bit "ones to beat", not the best ones produced by this guy's project)


Not an expert but the "sloshing" construct looks like multiple xorshift* operations. https://en.m.wikipedia.org/wiki/Xorshift


One reason I really like this is it gives me confidence in the results when multiple independent researchers end up at the same result.


A brief look at the Linux-kernel random generator interfaces https://nikmav.blogspot.com/2016/10/random-generator-linux.h...


I'll add it to smhasher, but it looks like Murmur3 to me.




Consider applying for YC's Spring batch! Applications are open till Feb 11.

Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: