Re: Good hash for pointers

On 2024-05-23, Malcolm McLean <malcolm.arthur.mclean@gmail.com> wrote:

>
What is a good hash function for pointers to use in portable ANSI C?

I don't think that it's practical to try to do this in some portable
way, let alone to an old dialect of C from 1989.

Let's say we have a type uintptr_t to which we can convert a void *
pointer.

In the TXR Lisp run time, here is what I did (paraphrased):

    switch (CHAR_BIT * sizeof (void *)) {
    case 32:
       return ((uintptr_t) ptr) >> 4;
    case 64:
       return ((uintptr_t) ptr) >> 5;
    }

The idea is that on 32 bits, we suspect that pointers from malloc may be
aligned on 16 bits, so the least significant four bits don't tell us
anything useful; they are likely all zero, which is bad. On 64 bits, we
throw away five bits.

This is actually an important hashing function because it's used
for hashing objects that use eq equality even when compared using
equal.

For instance, all structs for which an equality substitute is not
defined.

--
TXR Programming Language: http://nongnu.org/txr
Cygnal: Cygwin Native Application Library: http://kylheku.com/cygnal
Mastodon: @Kazinator@mstdn.ca