Path: ...!eternal-september.org!feeder3.eternal-september.org!news.eternal-september.org!raubtier-asyl.eternal-september.org!.POSTED!not-for-mail
From: Bonita Montero <Bonita.Montero@gmail.com>
Newsgroups: comp.lang.c
Subject: Re: Good hash for pointers
Date: Sun, 26 May 2024 18:07:32 +0200
Organization: A noiseless patient Spider
Lines: 35
Message-ID: <v2vmo2$3fgiv$1@raubtier-asyl.eternal-september.org>
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> <v2t8od$2vpp7$1@dont-email.me>
 <v2vmje$3ffjk$2@raubtier-asyl.eternal-september.org>
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 8bit
Injection-Date: Sun, 26 May 2024 18:07:31 +0200 (CEST)
Injection-Info: raubtier-asyl.eternal-september.org; posting-host="861c1998cc926dd42c778978d59780b8";
	logging-data="3654239"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX196g0ptLpGxwHCvWMPRg3pKnnEMfIB8pC8="
User-Agent: Mozilla Thunderbird
Cancel-Lock: sha1:Jxe5pGoZFBpNmwhD+8WjqkTz/dM=
In-Reply-To: <v2vmje$3ffjk$2@raubtier-asyl.eternal-september.org>
Content-Language: de-DE
Bytes: 2805

Am 26.05.2024 um 18:05 schrieb Bonita Montero:
> Am 25.05.2024 um 19:56 schrieb Malcolm McLean:
>> On 25/05/2024 18:40, Tim Rentsch wrote:
>>> Bonita Montero <Bonita.Montero@gmail.com> writes:
>>>
>>>> Am 25.05.2024 um 11:12 schrieb Tim Rentsch:
>>>>
>>>>> Your hash function is expensive to compute, moreso even
>>>>> than the "FNV" function shown earlier.  In a case like
>>>>> this one where the compares are cheap, it's better to
>>>>> have a dumb-but-fast hash function that might need a
>>>>> few more looks to find an open slot, because the cost
>>>>> of looking is so cheap compared to computing the hash
>>>>> function.
>>>>
>>>> A (size_t)pointer * LARGE_PRIME can be sufficient,
>>>> ignoring the overflow.
>>>
>>> Plenty fast but the output quality is poor.  I tested
>>> this scheme against four other hash functions, and in
>>> four out of five workloads it was always dead last, by
>>> a noticeable margin.
>>  >
>>
>> The lower bits of a pointer are often all zeroes. And mutlipying by
>> any  integer will not set them. And that is catastrophic for a hash.
>>
> 
> If you take a large integer they will be scrambled and if the
> prime is large enough there will be a good equal distribution.

If you've got a 64 bit uintptr_t and take the largest prime that
fits into 64 bit - 18446744073709551557 - the equal distribution
should be perfect.