3 ms·
Prospecting for Hash Functions
- amenghra 8y agoI 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.
- andrewf 8y agoGo does this for its native map (dictionary) type. https://codereview.appspot.com/7543043 https://codereview.appspot.com/7543043
- amenghra 8y agoA fun exercice would be to compare this to SipHash.
- nightcracker 8y agoThe 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.
- rurban 8y agoIt will be slow, but will still be compatible.
- tjalfi 8y agofalkhash[0] does this. [0] https://github.com/gamozolabs/falkhash https://github.com/gamozolabs/falkhash
- slaymaker1907 8y agoIt 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.
- tehsauce 8y agoReally 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
- jnurmine 8y agoNot an expert but the "sloshing" construct looks like multiple xorshift* operations. https://en.m.wikipedia.org/wiki/Xorshift https://en.m.wikipedia.org/wiki/Xorshift
- known 8y agoA brief look at the Linux-kernel random generator interfaces https://nikmav.blogspot.com/2016/10/random-generator-linux.html https://nikmav.blogspot.com/2016/10/random-generator-linux.h...
- nielsbot 8y agoMakes 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)
- rurban 8y agoI'll add it to smhasher, but it looks like Murmur3 to me.
- bloak 8y agoThis 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?
- CJefferson 8y agoOne reason I really like this is it gives me confidence in the results when multiple independent researchers end up at the same result.