Re: Good hash for pointers

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.