Path: ...!eternal-september.org!feeder3.eternal-september.org!news.eternal-september.org!.POSTED!not-for-mail
From: Malcolm McLean <malcolm.arthur.mclean@gmail.com>
Newsgroups: comp.lang.c
Subject: Re: Good hash for pointers
Date: Sat, 25 May 2024 18:56:29 +0100
Organization: A noiseless patient Spider
Lines: 29
Message-ID: <v2t8od$2vpp7$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>
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 7bit
Injection-Date: Sat, 25 May 2024 19:56:29 +0200 (CEST)
Injection-Info: dont-email.me; posting-host="b71cdde5a6bb5a9f68351e380f6d099c";
	logging-data="3139367"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX18v0yzrTEyLo0MipVT1am/DU0DZDROR4RY="
User-Agent: Mozilla Thunderbird
Cancel-Lock: sha1:fLOX/uxLv4+Kv4RsM8jqDk5SduU=
In-Reply-To: <8634q5hjsp.fsf@linuxsc.com>
Content-Language: en-GB
Bytes: 2271

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.

-- 
Check out Basic Algorithms and my other books:
https://www.lulu.com/spotlight/bgy1mm