From Newsgroup: comp.lang.forth

anton@mips.complang.tuwien.ac.at (Anton Ertl) writes:

Looking at the traditional length+3 chars and
albert@spenarnc.xs4all.nl's 3 first and last, at least one pair of
words in Forth-94 conflicts
(...)

Another option would be to store a hash value that is computed using
all characters in the name. If a good hash function is used, (...)
The disadvantage of this approach is that WORDS or SEE cannot even
show the little about the name that Chuck Moore's approaches or albert@spenarnc.xs4all.nl's approach shows.

I think I have some relevant, though highly eccentric, experience here.
Bear with me.

For a number of years, I used a hash table for a address book
handwritten with pen on paper. This may sound impossible, so I'll
include some explanation here that isn't relevant to the Forth
dictionary use case. I used linked-list chaining between entries
appended to a chronologically ordered numbered array:

105. 153 Angela Lark +54 11 4844 3938 Tronador 371, Buenos Aires
106. Erik Stauffer +1 415 310 0531 737 Allston, Berkeley CA
107. ...

The pen-on-paper medium has the WORM characteristic: you cannot really
erase ink from the paper, so I represented the linked-list pointers as next-entry numbers, terminating the list with an empty space. This
makes it possible to append to the list without erasing anything.

The heads of the chains (the number of the first entry in a chain) were
held in a fixed-size table addressed by the hash value of the address
book entry.

Hash function choice was constrained by what I could easily evaluate in
my head. After evaluating a few different hash functions, I settled on
the rCLflavorsrCY of the first and third letters of the personrCOs given name, where the rCLflavorrCY of a letter is its ordinal position in the alphabet, divided by 2, rounded up. So rCLarCY and rCLbrCY are flavor 1, rCLcrCY and rCLdrCY are
flavor 2, etc. (I forget what I did for one- and two-letter names.)

This gave a 13|u13 hash table that fit easily on one page of the
notebook, beginning more or less as follows:

ab cd ef gh ...
ab 7
cd 12
ef 5
gh 105
ri<

So, for example, to look up rCLAngelarCY, you would start at entry 105
(from the rCLArCY and rCLgrCY), and if that wasnrCOt the right Angela, but there
was a next-pointer of 153, you would check entry 153.

With 169 hash chains and under 200 people in my address book, lookup
seemed a little faster than with an alphabetized list, but the real
benefit was that insertion of new entries was possible without leaving a
great deal of blank space.

The first and third letter worked better than the first two letters
because they were less correlated.

If you wanted to maximize the human-interpretable information of the
32-bit hash value of a Forth identifier, maybe the solution is to
transcode the name lossily into 5-bit Baudot-Murray code and take, like
old Fortran linkers, the first six characters of the name. This gives
you ForthrCOs traditional case-smashing behavior; it costs you an extra
FIGS shift when you use punctuation or digits, and there are some ASCII punctuation characters yourCOd have to map to something else on input,
such as `?` or `/`. Maybe map the specially important characters `<`
and `>` to `=(` and `=)`.

So, for example, `s>f` might be 00101 11011 11110 10010 11111 01101,
using up all 30 of the character bits. But `words` is just 10011 11000
01010 01001 00101 and can be padded out with nulls. A `words` or `see`
could render both of those without truncation, as too with any purely-alphabetic word of up to 6 letters.

...but it might be worthwhile to skip characters at some point, or store
the last character instead of the sixth, in cases where truncation is
needed.

Kragen
--- Synchronet 3.22a-Linux NewsLink 1.2