Path: csiph.com!eternal-september.org!feeder.eternal-september.org!nntp.eternal-september.org!.POSTED!not-for-mail From: Kragen Javier Sitaker Newsgroups: comp.lang.forth,alt.hackers Subject: hashing for Forth dictionaries and address books (was Re: ciforth model) Date: Tue, 01 Sep 2026 15:09:42 -0300 Organization: Primarily biological and memetic Lines: 84 Approved: unreservedly Message-ID: <87bjag4zdl.fsf_-_@debian> References: <69e19091$1@news.ausics.net> <2026Apr17.092944@mips.complang.tuwien.ac.at> MIME-Version: 1.0 Content-Type: text/plain; charset=utf-8 Content-Transfer-Encoding: 8bit Injection-Date: Tue, 01 Sep 2026 18:12:01 +0000 (UTC) Injection-Info: dont-email.me; logging-data="2179632"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX19JP42tdHXb+cj/31h6tVbg"; posting-host="fa8aa933a678f631da317852f835fb16" User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/28.2 (gnu/linux) Cancel-Lock: sha1:KsUQV7AzACLZa3ZrpEYFvuBLMS4= sha1:thRMt9B2IljwyEAA3lexAGLLgdk= sha256:4PO0/1Kbda+YJO7WVyUbPKz8+maXLaySp/01gPvq59k= sha1:4I118ZIT3cqNohfsWahIkeNDd2Q= sha256:EGSWdwFiMlmUOE8lHdBAq3Vl2+Z3X4f+L1P3n2FyDdo= Xref: csiph.com comp.lang.forth:135509 alt.hackers:86 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 “flavors” of the first and third letters of the person’s given name, where the “flavor” of a letter is its ordinal position in the alphabet, divided by 2, rounded up. So “a” and “b” are flavor 1, “c” and “d” are flavor 2, etc. (I forget what I did for one- and two-letter names.) This gave a 13×13 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 ⋮ So, for example, to look up “Angela”, you would start at entry 105 (from the “A” and “g”), and if that wasn’t 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 Forth’s traditional case-smashing behavior; it costs you an extra FIGS shift when you use punctuation or digits, and there are some ASCII punctuation characters you’d 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