I experimented with hash codes in strings in TXR Lisp, but took it out after several days:
commit a136f37015cc2513878f75afcf8ba49fa61a88e5
Author: Kaz Kylheku <kaz@kylheku.com>
Date: Sat Oct 8 20:54:05 2022 -0700
strings: revert caching of hash value.
Research indicates that this is something useful in
languages that abuse strings for implementing symbols.
We have interned symbols.
* lib.h (struct string): Remove hash member.
* lib.c (string_own, string, string_utf8, mkustring,
string_extend, replace_str, chr_str_set): Remove
all initializations and updates of the removed
hash member.
* hash.c (equal_hash): Do not cache string hash value.
> This improvement will benefit any immutable Map<String, V> with Strings as keys and where values (of arbitrary type V) are looked up via constant Strings.
Wait, what? But, that's inherently constant foldable without reasoning about string hash codes; we don't need them at all.
We examine the expression [h "a"]: lookup the key "a" in hash table h, where h is a hash literal object, that we write as #H(() ("a" "b)). It contains the key "a", mapping it to "b":
> Wait, what? But, that's inherently constant foldable without reasoning about string hash codes; we don't need them at all.
Their goal wasn't to improve key lookups in hash tables, that is more or less just an example.It was to improve optimization of variables with lazy initialisation overall and the hash of String uses lazy initialisation.
Wait, what? But, that's inherently constant foldable without reasoning about string hash codes; we don't need them at all.
We examine the expression [h "a"]: lookup the key "a" in hash table h, where h is a hash literal object, that we write as #H(() ("a" "b)). It contains the key "a", mapping it to "b":
What's the code look like? One instruction: just return "b" from the static data register d0. The hash table is completely gone.The keys don't even have to be strings; that's a red herring.