Path: ...!feeds.phibee-telecom.net!2.eu.feeder.erje.net!feeder.erje.net!eternal-september.org!feeder3.eternal-september.org!news.eternal-september.org!.POSTED!not-for-mail
From: bart <bc@freeuk.com>
Newsgroups: comp.lang.c
Subject: Re: Good hash for pointers
Date: Mon, 3 Jun 2024 17:24:36 +0100
Organization: A noiseless patient Spider
Lines: 39
Message-ID: <v3kqo3$3v9m2$1@dont-email.me>
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=UTF-8; format=flowed
Content-Transfer-Encoding: 7bit
Injection-Date: Mon, 03 Jun 2024 18:24:35 +0200 (CEST)
Injection-Info: dont-email.me; posting-host="d2cae1aa4235874fd2214b538c145732";
	logging-data="4171458"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX1/ClMBuel+3iPn4LlSwb9mI"
User-Agent: Mozilla Thunderbird
Cancel-Lock: sha1:SQUBA4Land5+tRV/DZbmpZHjLOo=
Content-Language: en-GB
In-Reply-To: <v3kovm$3v2ie$1@raubtier-asyl.eternal-september.org>
Bytes: 3057

On 03/06/2024 16:54, Bonita Montero 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.
> 

A pointer with 8-byte or 16-byte alignment will have the bottom 3-4 bits 
zero.

No matter what number you multiply them by, prime or otherwise, those 
3-4 bits will always be zero.

If you mask the result to fit a table of size power-of-two, then the 
resulting index will can only ever refer to every 8th or every 16th 
slot; there will 8-16x as many clashes as there ought to be.

So some extra work is needed to get around that, for example 
right-shifting before masking as some here have done, something you have 
never mentioned.