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

Groups > comp.lang.forth > #135509

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

Cross-posted to 2 groups.

Show all headers | View raw

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

Back to comp.lang.forth | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

ciforth model albert@spenarnc.xs4all.nl - 2026-04-16 15:38 +0200
  Re: ciforth model dxf <dxforth@gmail.com> - 2026-04-17 11:44 +1000
    Re: ciforth model anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2026-04-17 07:29 +0000
      Re: ciforth model albert@spenarnc.xs4all.nl - 2026-04-17 12:10 +0200
        Re: ciforth model anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2026-04-18 10:26 +0000
          Re: ciforth model peter <peter.noreply@tin.it> - 2026-04-18 18:11 +0200
          Re: ciforth model albert@spenarnc.xs4all.nl - 2026-04-18 20:57 +0200
            Re: ciforth model anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2026-04-19 11:08 +0000
              Re: ciforth model albert@spenarnc.xs4all.nl - 2026-04-20 13:39 +0200
          Re: ciforth model peter <peter.noreply@tin.it> - 2026-05-21 10:28 +0200
            Re: ciforth model minforth <minforth@gmx.net> - 2026-05-22 12:04 +0200
            Re: ciforth model anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2026-05-23 18:12 +0000
              Re: ciforth model peter <peter.noreply@tin.it> - 2026-05-23 23:09 +0200
              Re: ciforth model peter <peter.noreply@tin.it> - 2026-05-24 10:07 +0200
                Re: ciforth model anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2026-05-25 13:34 +0000
                Re: ciforth model peter <peter.noreply@tin.it> - 2026-05-27 10:42 +0200
      Re: ciforth model Hans Bezemer <the.beez.speaks@gmail.com> - 2026-04-21 19:39 +0200
      Re: ciforth model albert@spenarnc.xs4all.nl - 2026-04-22 22:48 +0200
        Re: ciforth model Paul Rubin <no.email@nospam.invalid> - 2026-04-24 10:38 -0700
          Re: ciforth model albert@spenarnc.xs4all.nl - 2026-04-25 11:54 +0200
            Re: ciforth model Paul Rubin <no.email@nospam.invalid> - 2026-04-25 13:22 -0700
              Re: ciforth model albert@spenarnc.xs4all.nl - 2026-04-26 14:05 +0200
      hashing for Forth dictionaries and address books (was Re: ciforth model) Kragen Javier Sitaker <kragen@canonical.org> - 2026-09-01 15:09 -0300
  Re: ciforth model Paul Rubin <no.email@nospam.invalid> - 2026-04-17 00:27 -0700
    Re: ciforth model albert@spenarnc.xs4all.nl - 2026-04-17 12:13 +0200

csiph-web