search

skeeto / hash-prospector

Automated integer hash function discovery
The Unlicense
672 stars 27 forks source link

[Q] could you add some 64 bit examples too #5

Open rofl0r opened 3 years ago

rofl0r commented 3 years ago

since the README lacks anything 64bit, i compiled a GCC with openmp support to run prospector myself. interestingly, only one thread is used. is the omp parallel pragma only used for a section of code that's rarely run ? i'm running ./prospector -8, ftr. how long will i have to wait in average until a usable hash func is printed on a modern ryzen core ?

skeeto commented 3 years ago

The problem is that it's not practical to measure the entire 64-bit space, and the Monte Carlo method estimates have too much variance to reveal any differences between 64-bit permutations. You really end up measuring the PRNG as much as the hash. So effectively any 64-bit permutation with reasonable parameters is the same as any other. (This issue makes me skeptical about other people making measurement-based claims about 64-bit permutations.)

Though now that I think about it, maybe a more reasonable estimate could be made using a quasirandom sequence rather than a straight PRNG…

rofl0r commented 3 years ago

thanks for your reply. for the moment i ended up using the 64bit method from this stackoverflow post that links here: https://stackoverflow.com/questions/664014/what-integer-hash-function-are-good-that-accepts-an-integer-hash-key (second answer with 157 upvotes), though i'd certainly appreciate if you find a way to improve the 64bit algorithm and post some results.

btw, is there an explanation somewhere how the hash functions using the values of your recent README additions can be reversed ? i've not seen an obvious relationship between the values used in the hash and reversal functions.

skeeto commented 3 years ago

At line 410 in hillclimb.c there's a little routine for computing the hash inversions. I forget how I learned this, but when I did I put it in such precise terms so that I'd never have to figure it out again! It only does 32-bit inversions, so if you want to invert a 64-bit hash you'll have to work out the 64-bit xorshifts from the 32-bit xorshift inversion. I only supplied a 32-bit multiplicative inverse (modinv32()), but you can upgrade to a 64-bit multiplicative inverse with just one more iteration.

Logan007 commented 3 years ago

computing the hash inversions

I found Marc B. Reynolds' explanations to be extremely helpful.