Path: ...!eternal-september.org!feeder3.eternal-september.org!news.eternal-september.org!.POSTED!not-for-mail
From: Janis Papanagnou <janis_papanagnou+ng@hotmail.com>
Newsgroups: comp.lang.c
Subject: Re: Good hash for pointers
Date: Sat, 25 May 2024 23:13:31 +0200
Organization: A noiseless patient Spider
Lines: 38
Message-ID: <v2tk9s$31qv4$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> <v2t8od$2vpp7$1@dont-email.me>
MIME-Version: 1.0
Content-Type: text/plain; charset=utf-8
Content-Transfer-Encoding: 7bit
Injection-Date: Sat, 25 May 2024 23:13:33 +0200 (CEST)
Injection-Info: dont-email.me; posting-host="766ef45e35616bea7a8985f732a78eeb";
	logging-data="3206116"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX18ySAeF+dd71PTtbGKSYagz"
User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:45.0) Gecko/20100101
 Thunderbird/45.8.0
Cancel-Lock: sha1:QAoRDhdfEbFZ7xfxd2XMWxlQ3ic=
In-Reply-To: <v2t8od$2vpp7$1@dont-email.me>
X-Enigmail-Draft-Status: N1110
Bytes: 2838

On 25.05.2024 19:56, Malcolm McLean wrote:
> 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.

I haven't read all the thread, but if I'd be going to tackle that
I'd first try to map the pointer onto a fitting integral type (if
that's possible; sizeof()), or first "fold" (XOR) the upper/lower
parts of the pointer (so that zero-sequences, if they appear, also
won't affect the outcome too badly as a side effect) to reduce the
size of the data, and finally use any established hash algorithm
on the (folded/reduced) integral type.

Shall the created hash codes also be portable across platforms?

Janis