Re: Good hash for pointers

On 2024-05-25, bart <bc@freeuk.com> wrote:

It's not clear to me what the hashing is for on the nodes. What exactly
is the input being looked up, and what is being compared? Because
something sounds off: you don't normally look up a pointer to try and
find it in a table; you already have the pointer pointing at the data!

This happens when you need to associate objects with external
information which is not in those objects.

One such situation is when you replace use of strings as hash keys with
interned strings (atoms).  Atoms are typically pointers and so hash that way. 

This is a smart thing to do because atoms are faster to work with.
Comparing whether two values are the same atom is just a pointer
comparison, and hashing the atom is just a pointer hash: much faster
than a string hash, and with more easily assured good behavior.

The interning mechanism maintains its own hash table which maps the
strings to the atoms. By that mechanism, two identical strings are
mapped to the same atom. That table is only used at the boundaries of
the system when external data is read. The data contains identifiers
which are interned, and then they are manipulated as atoms.

Lisp languages have a symbol type, which is a kind of interned
string. Symbols are regularly used as keys into dictionary structures
like hash tables or assocation lists.

Certain important properties are put into the symbol itself, so
that no hashing is required to find them.

In classical Lisps, the global value of a variable named by a symbol
is stored in the symbol itself. The property list of a symbol is also
stored in the symbol.

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