Hacker Newsnew | past | comments | ask | show | jobs | submitlogin

It's true that you can use AES instructions now on some computers, bit I honestly don't see why you'd use a heuristic hash (even if cryptographic) when you can get provable guarantees with k-wise independent hashing. Our paper makes these even faster than they already were.

See section 5.7 and 5.8 in the paper for experiments against other hashes.



You benchmarked a really old heuristic hash in Murmur and xxh64. xxh3 is ~1.6x to 1.8x faster than xxh64 - extrapolating that to 5.7 in your paper puts it at ~18-27% faster. WyHash and UMash sometimes report faster numbers.

Even xxh3 isn't the cutting edge - gxhash (~1.8x faster) and aesni (~1.5x faster) use AES instructions. Compared to your approach that perf disparity should grow to ~30-40%.

Hopefully that answers your question about why someone might still choose to use heuristic hashing rather than k-wise independent hashing when collision resistance isn't critical.


> Hopefully that answers your question about why someone might still choose to use heuristic hashing

Not really. Our method is also 2x faster than xxh3.

Sure, AES make the heuristic hashes harder to break, but they still provide (1) slower performance, (2) no guarantees.




Consider applying for YC's Winter 2027 batch! Applications are open till November 2.

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

Search: