Path: ...!2.eu.feeder.erje.net!feeder.erje.net!eternal-september.org!feeder3.eternal-september.org!news.eternal-september.org!.POSTED!not-for-mail
From: Michael S <already5chosen@yahoo.com>
Newsgroups: comp.lang.c
Subject: Re: Good hash for pointers
Date: Mon, 3 Jun 2024 19:50:22 +0300
Organization: A noiseless patient Spider
Lines: 45
Message-ID: <20240603195022.0000183a@yahoo.com>
References: <v2n88p$1nlcc$1@dont-email.me>
	<v2qm8m$2el55$1@raubtier-asyl.eternal-september.org>
	<v2qnue$2evlu$1@dont-email.me>
	<v2r9br$2hva2$1@dont-email.me>
	<86fru6gsqr.fsf@linuxsc.com>
	<v2sudq$2trh1$1@raubtier-asyl.eternal-september.org>
	<8634q5hjsp.fsf@linuxsc.com>
	<v2vmhr$3ffjk$1@raubtier-asyl.eternal-september.org>
	<86le3wfsmd.fsf@linuxsc.com>
	<v2voe7$3fr50$1@raubtier-asyl.eternal-september.org>
	<86ed9ofq14.fsf@linuxsc.com>
	<v2vs40$3gflh$1@raubtier-asyl.eternal-september.org>
	<86sexypvff.fsf@linuxsc.com>
	<20240602104506.000072e4@yahoo.com>
	<v3kk9p$3u8qu$1@raubtier-asyl.eternal-september.org>
	<20240603174604.000014d4@yahoo.com>
	<v3kovm$3v2ie$1@raubtier-asyl.eternal-september.org>
MIME-Version: 1.0
Content-Type: text/plain; charset=US-ASCII
Content-Transfer-Encoding: 7bit
Injection-Date: Mon, 03 Jun 2024 18:50:10 +0200 (CEST)
Injection-Info: dont-email.me; posting-host="2e115e67b3843932598c276339879624";
	logging-data="4002254"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX1/fnjGrUJvJweBcJextkm81c30iDUn3yx4="
Cancel-Lock: sha1:Hg3YnZZScES/KFjkzl/3dFJdwaM=
X-Newsreader: Claws Mail 3.19.1 (GTK+ 2.24.33; x86_64-w64-mingw32)
Bytes: 3404

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.