[tromp]

You probably don't need the hash to be cryptographically secure. The simplest solution might be to use several uniquely keyed siphash instances, as siphash is quite cheap to compute, was designed for use in hash tables, and two siphashes with different keys behave pairwise independent, which roughly means there are no observable correlations between them.

[1] https://en.wikipedia.org/wiki/SipHash

[lmb]

I think we tried siphash at some point, unfortunately it's significantly slower than the two hash functions we ended up using.