~skeeto/public-inbox

Re: Prospecting for Hash Functions

Yann Droneaud
Details
Message ID
<da2c4c2dc0000b054e014636be12326a1a532ec5.camel@opteya.com>
DKIM signature
missing
Download raw message
Hi,

I've recently looked up good, fast, simple integer hash function and
found those you prescribed in "Prospecting for Hash Functions" [0].
I'm using the ones you recommanded there.

Anyway I was curious if better, faster, simpler hash functions could
exist. Search engine (Google) didn't lead to my dream hash function,
but I found some interesting research that looks like it could be
useful to review.

In 'On the mixing functions in "Fast Splittable Pseudorandom Number 
Generators" , MurmurHash3 and David Stafford's improved variants on
the  MurmurHash3 finalizer.' [1], Pelle Evensen suggests hash function
of this form:

uint64_t rrmxmx(uint64_t v) {
  v ^= ror64(v, 49) ^ ror64(v, 24);
  v *= 0x9FB21C651E98DF25L;
  v ^= v >> 28;
  v *= 0x9FB21C651E98DF25L;
  return v ^ v >> 28;
}

An improved version is described in "Better, stronger mixer and a test
procedure" [2]:

uint64_t rrxmrrxmsx_0(uint64_t v) {
  v ^= ror64(v, 25) ^ ror64(v, 50);
  v *= 0xA24BAED4963EE407UL;
  v ^= ror64(v, 24) ^ ror64(v, 49);
  v *= 9FB21C651E98DF25UL;
  return v ^ v >> 28;
}

Latest iteration is described in "NASAM: Not Another Strange Acronym
Mixer!" [3]:

uint64_t nasam(uint64_t x) {
  x ^= ror64(x, 25) ^ ror64(x, 47);
  x *= 0x9E6C63D0676A9A99UL;
  x ^= x >> 23 ^ x >> 51;
  x *= 0x9E6D62D06F6A9A9BUL;
  x ^= x >> 23 ^ x >> 51;
  return x;
}

It should be noted those functions were evaluated using random number
generator tookit TestU01 and PractRand, which seems to be the gold
standard for RNG. And speed was evaluated with your tool prng64-
shootout :).

Unfortunately, hash prospector cannot generate such hash function
due to the x = f(x) ^ g(x) structure used in them. 

Are you aware of other "hash prospector" effort to develop toolkit to
found better, faster, simpler, general purpose integer hash function ?

[0] https://nullprogram.com/blog/2018/07/31/
[1] 
http://mostlymangling.blogspot.com/2018/07/on-mixing-functions-in-fast-splittable.html
[2] 
http://mostlymangling.blogspot.com/2019/01/better-stronger-mixer-and-test-procedure.html
[3] 
http://mostlymangling.blogspot.com/2020/01/nasam-not-another-strange-acronym-mixer.html

Regards.

-- 
Yann Droneaud
OPTEYA
Export thread (mbox)