（评论）

（评论）
(comments)

原始链接: https://news.ycombinator.com/item?id=40261681

异或移位算法通过解决哈希函数的两个主要弱点来增强哈希函数：高位缺乏来自上方的影响，低位缺乏来自下方的影响。异或移位使散列函数可逆，这是有利的，因为它会产生优异的混合函数。可逆性保留数据，避免信息逐渐减少，并生成更大的状态空间，减少冲突。哈希函数在为哈希表中的数据项创建唯一的“哈希代码”方面发挥着不可或缺的作用，从而提高了效率。使用简单方法（例如仅使用字符序列的 ASCII 值）的一个常见问题是，由于多个字符串产生相同的哈希码，会发生大量冲突。为了防止此类冲突，哈希函数组合并转换整个数据集中的位组合，保持独特性，同时最大限度地减少计算开销。各种哈希函数在速度和最小化冲突的能力方面有所不同。世界一流的哈希函数采用复杂的数学运算，包括乘法、异或和位移位，以实现最佳的冲突避免。提供的代码对各种哈希函数进行了实验，将它们相互比较，以寻找对现实世界哈希表功能的潜在改进。通过发现用于处理集合和映射的高效哈希函数（整数哈希函数），额外的好处扩展到布隆过滤器更快的哈希功能。然而，偏见对密码操作的影响及其与密码分析的关系仍不清楚。涉及可定制输入生成器的进一步探索可能会暴露隐藏的机会，特别是在处理非二进制或结构化数据时。

Skeeto is a legend. Up there with Febrice Bellard in my book. I've followed him on GH for years and he just drops bangers of weird niche little tools that are always interesting.

Branchless UTF-8 is a famous one, for example.

Xor-shift counteracts the two weaknesses of a multiply: the high bits have nothing above them to influence, and the low bits have nothing below them to be influenced by.

I've often thought about the idea of auto hash finding based on my experiences developing good hash functions^0

Cool to see this! I think it would be cool to hook it up with SMHasher3^1 (a much improved, and faster variant of the venerable hash test suite developed by Frank J. T. Wojcik) to automatically evaluate its output. You could use a subset of tests and fail fast for speed.

It would also be cool to expand it to 64 and 128 bit hashes (tho obviously the search space is larger).

Somewhat related I created some NodeJS code to measure avalanche under multiplication for 64-bit primes in order to select the values for Rain.

[Rain]: https://github.com/dosyago/rain

[SMHasher3]: https://gitlab.com/fwojcik/smhasher3

It seems to be a tool that generates instructions for building hash functions, then evaluates the hash functions to see how good they are. The goal metric has been chosen to be that as many output bits as possible should change as randomly as possible with every changed input bit.

It outputs C code for the best hash function it generated.

So it's useful if you want a hash function, and don't think any of the existing ones are good enough. Or if you're researching hash functions, and want new ideas for structures.

Cool? Well, generating code is cool. Doing it randomly is a first step towards genetic programming, which would be even cooler. ... and making computers burn CPU cycles computing (mostly unused) hashes seems to be something we humans want to do since around 15 years ago.

> [...] making computers burn CPU cycles computing (mostly unused) hashes seems to be something we humans want to do since around 15 years ago.

Keep in mind that there's a big difference between cryptographic hash functions and the kind of hash functions investigated here.

Haha! :) No, not overall, but you do want reversible steps in a crypto hash as Reversible steps make better mixing functions, Because you’re not losing information so you avoid iteratively diminishing that information leading to a smaller state space, and more state collisions.

These functions are essential to a hash tables (other related names are hash maps, hash sets).

A hash table is a remarkable data structure that can be used to implement many algorithms simply and efficiently.

This efficiency depends on being able to create small (say 32- or 64-bit) and nearly-unique “hashes” for your data. For example, to hash user names, it wouldn’t work very well to just use the ASCII code for the first letter of the names, because then a lot of usernames would map to the same number. That’s called a collision. If there are a lot of collisions, hash tables become very inefficient.

A better approach would be to grab bits from the entire username, and smash them together somehow so that “throwaway_1237” and “throwaway_12373” still username different numbers.

Hash functions do this mapping. The property of “avalanche” describes how good of a job they do at avoiding collisions.

There’s generally a tradeoff between (1) how fast the actual hash function is, and (2) how good of a job it does of avoiding collisions.

World-class hash functions look remarkably weird, multiplying and xoring and shifting by strange amounts. It’s very hard for humans to look at these cryptic functions and guess how well they will do.

So this code is trying out a bunch of hash functions at random and baking them off against each other. This is cool because success here could improve real-world performance of a core data structure used across many languages and libraries.

Hash functions on integers, so if you want a fast integer hash for a set or map. If the functions diverge sufficiently it also provides fast hashes for a bloom filter.

I implemented the 1brc in go a few weeks back [1] and this repo was inspiration to try to find a custom perfect hash function that put each station into its own bucket with no collisions. Then I noticed the rule that you can't customize the hash function to the data before the program starts and dropped the idea.

I made a test harness to check random constants (start values, multiplication constants, shift/rotate amounts, etc) and print out the best constants found so far based on the number of colliding buckets and how many collisions. I think I got it down to 1 bucket with just two colliding values with a ~40% fill rate. Interestingly, I found that the best performing constants included similar values for the number of positions to shift regardless of the other constants, so I ended up hard coding them.

[1]: https://github.com/infogulch/1brc-go

It's unclear to me what this is doing exactly -- is it finding the best ever? If not, why would the best change every time you run this?

Also, does anyone have pointers to a hash function discovery mechanism that discovers a good hash function for integer values within a specific range (i.e I know that my integer values are between, say, 10,000 and 200,000, for example) and I want to hash them into some optimal number of hash buckets?

It's randomly trying values to find the best of the ones it has tried that run. The values would change between runs because you can't feasibly exhaust the search space in a single run to find the absolute best (+the order you try is random).

If you're just looking for "good" the best approach is almost always to just use a normal hash function. If your numbers are extremely large and the range extremely small you can offset so the minimum becomes 0 again and use a smaller/faster hash. If you're more looking for "perfect choice of the exact range" I think the closest you'll get is something like this randomized approach but modify the tests to occur on your interval.

Limiting itself to reversible operations gives some mathematical niceties, but also locks out a lot of things.

When I did something similar, I was thinking about perfect hashing, where the set of inputs is known ahead of time. The usual approach uses a constant array, but I wanted to - in particular, if the inputs are already small integers, if I could compact them further (obviously this is possible: hash -= hash > > gap_index). I sat down and wrote out a list of ... probably 100? ... primitive operations (some of which are admittedly redundant with each other, but which are useful thinking of separately). And then I got bored and never did anything with the project.

> Limiting itself to reversible operations gives some mathematical niceties

What are those niceties, why is a reversible operation desirable in this context?

"One of the important properties of an integer hash function is that it maps its inputs to outputs 1:1. In other words, there are no collisions. If there’s a collision, then some outputs aren’t possible, and the function isn’t making efficient use of its entropy.

This is actually a lot easier than it sounds. As long as every n-bit integer operation used in the hash function is reversible, then the hash function has this property. An operation is reversible if, given its output, you can unambiguously compute its input."

https://nullprogram.com/blog/2018/07/31/

I know I’m comparing oranges to apples here as these functions are not well suited for cryptographic operations, but how does the measured “bias” affect cryptanalysis? Can someone familiar with differential cryptography explain if a hash function with a lower bias defeats cryptanalysis with lower rounds or with less compute? Will this thing help find better cryptographic hash functions?

This bias testing is essentially ruling out candidates with very high probability truncated differentials of Hamming weight 1. In a cryptographic primitive you want to rule out _all_ high-probability differentials, which requires different methods. You also want to rule out other high-probability statistical distinguishing properties, such as linear approximations, higher-order differentials, etc.

That being said, this sort of quick-and-dirty testing is useful to filter out obviously bad candidates at the early design phase of, say, an ARX primitive.

> Three round functions: [...] this hash function is indistinguishable from a perfect PRF

I assume this means "indistinguishable through naive statistical tests", because any more literal meaning would surprise me

No, I mean in the sense given on the page (I should've included the parenthetical in my quote)

> (e.g. a random permutation of all 32-bit integers)

Since they only use bijective primitives, it's trivially "perfect" in the "perfect hash function" sense.

To elaborate further on the definition I was going off (which may well not be what the author meant):

> A PRF is considered to be good if its behavior is indistinguishable from a truly random function. Therefore, given an output from either the truly random function or a PRF, there should be no efficient method to correctly determine whether the output was produced by the truly random function or the PRF.

https://en.wikipedia.org/wiki/Pseudorandom_function_family

What would make this really interesting is if you can give it a generator for input data yourself. Very often you don't have random binary data but structured in some way. The structure might imply you can get a very nice hash function for it.

It would be interesting to generalize this with the operations available in the riscv bitmanip extension-- it might discover some strong functions for use in the future when those instructions are more widely available.

carryless multiply would also allow extending the set of reversible operations and are fast on some existent hardware (CRC too, somewhat a wider set of hardware but should be a strict subset of what CLMUL could find).

Many applications of hashes only care about the LSB or MSB of the hashes so evaluating the bias on MSB or LSB windows would be interesting (or mod varrious numbers), and some overall unbiased functions will look better or worse for metrics that don't gauge the entire output. (or for non-uniform inputs, for that matter, e.g. ascii text).

OMG, is it finally something useful, not in Rust for RISC-V?

I saw at the top in the comments "Skeeto is a legend", this is the best compliment.

My sincere gratitude to the author.

（评论） (comments)

（评论）
(comments)