Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > alt.hackers > #86 > unrolled thread

hashing for Forth dictionaries and address books (was Re: ciforth model)

Back to article view | Back to alt.hackers

This discussion starts older than the indexed window; earlier articles aren't shown. The article labeled Started by below is the oldest one visible, not the original post.

Contents

  hashing for Forth dictionaries and address books (was Re: ciforth model) Kragen Javier Sitaker <kragen@canonical.org> - 2026-09-01 15:09 -0300
    Re: hashing for Forth dictionaries and address books (was Re: ciforth model) Eli the Bearded <*@eli.users.panix.com> - 2026-09-02 19:10 +0000

#86 — hashing for Forth dictionaries and address books (was Re: ciforth model)

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

[toc] | [next] | [standalone]

#87

[Dropped from distribution: comp.lang.forth]

In alt.hackers, Kragen Javier Sitaker  <kragen@canonical.org> wrote:
> 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

I don't think I've been in 737 Allston, but I have been in 727 Allston.
As a corner location, the building was using the Fourth St address
instead of the Allston one. And it did have some space in the next door
building on Allston, but I don't think that is 737.

This was back when Vik's was a restaurant in a warehouse across the
street. (Vik's was a restaurant in the back of a store before then, and
is a restaurant a few blocks north now, where Sweet Potatoes used to
be. The old JET Co spot is the parking lot, never rebuilt after the
fire.)

ObHack:
Using a pair of pop rivets to create both a single point hinge and a
snap closure in a couple of pieces of sheetmetal used to cover a hole.
Drilled two holes in ~0.25mm aluminum sheet, one I riveted through both
layers with an inside stop washer, and one I did only one layer with a
stop washer and the hole in the other layer can snap on/off the part of
the rivet extending out of the washer. I'm using this as an escutcheon
flange over a large hole near a pipe.

Elijah
------
now wants some samosas and chole from Vik's

[toc] | [prev] | [standalone]

Back to top | Article view | alt.hackers

csiph-web