Re: Good hash for pointers

On Mon, 3 Jun 2024 17:54:30 +0200
Bonita Montero <Bonita.Montero@gmail.com> wrote:

Am 03.06.2024 um 16:46 schrieb Michael S:

On Mon, 3 Jun 2024 16:34:37 +0200
Bonita Montero <Bonita.Montero@gmail.com> wrote:
 

Am 02.06.2024 um 09:45 schrieb Michael S:
 

So, what were your conclusions?
Ignoring the speed of computation, would something like
cryptographic hash scaled to bucket size be a best hash for this
type of application? Or some sort of less thorough grinding of the
bits is better? 

>
There's no need for a crypto-hash here.
 

 
Do you think I don't know?
Crypto hash is just an example of near-ideal pseudo-random
uniformity.

 
As I've shown for pointers you get a perfect equal distribution with
multiplying by an appropriate prime.
 

What you had shown is, if we borrow terminology from characterization
of analog-to-digital converters, integral uniformity for ramp input.
That is not sufficient. Good hash need both integral and differential
uniformity.
According to Tim Rentsch, your method does not have the later.

What do you do exactly? Multiply by big prime modulo 2**64?
By intuition, without testing, I'd say that it does not sound as enough.
By intuition, without testing, doing it twice with two different primes,
then adding (or xoring) results together and doing multiplication again
with third prime sounds like enough.
By intuition, without testing, I'd rather use composite multiplication
factors instead of primes, choosing each factor as product of 3-4
non-small primes with all 9-12 primes involved being different.

But there should be simpler procedures that are just as good.