
**********************************************************************
files: Arrays.TXT, Arrays.TAP
       Array_Sort1.BAS, Array_Sort2.BAS, Array_Sort2.ASM, agessort.asm
       Array_Rotate1.BAS, Array_Rotate2.BAS, Array_Rotate2.ASM
       Array_Populate.BAS, Array_Compact.BAS
       http://www.users.globalnet.co.uk/~jg27paw4/pourri/hash-key.tap
**********************************************************************


** Sorting an array
   ================
ShellSort
This BASIC version is just to make it easy to understand the structure of the routine; it's too slow for practical use. Even pre-defining some variables so that those referenced most often are defined first, it still takes about 10 seconds to sort 50 bytes, which is painfully slow. I'd wanted it to sort an 80*32 array on selected 4-byte columns, but it took about 5 minutes, so it needed rewriting in machine code before it could be of any practical use.

Array_Sort1.BAS [code]
   5 REM Shell Sort
  10 DIM l$(1): INPUT n: DIM v$(n,1): LET j=0: LET t=0:
     FOR s=1 TO n: LET v$(s)=CHR$ (65+RND*25): NEXT s
  20 FOR s=1 TO n: LET a=2^s: IF a<n THEN  NEXT s
  21 LET m=a/2-1
  25 GO SUB 90: LET st=time:
     PRINT AT 4,0;"Start    : ";st

  40 FOR s=1 TO n-m:
          LET j=s
  50      LET t=j+m: LET l$=v$(j):
          IF l$>v$(t) THEN
               LET v$(j)=v$(t): LET v$(t)=l$: LET j=j-m:
               IF j>0 THEN
                    GO TO 50
  60 NEXT s
  65 LET m=(m-1)/2: IF m THEN GO TO 40

  70 GO SUB 90: LET ft=time:
     PRINT AT 5,0;"Finish   : ";ft'"Duration : ";ft-st:
     FOR s=1 TO n: PRINT v$(s);: NEXT s:
     PRINT : STOP
  90 LET t1=(65536*PEEK 23674+256*PEEK 23673+PEEK 23672)/50:
     LET t2=(65536*PEEK 23674+256*PEEK 23673+PEEK 23672)/50:
     LET time=t1-(t1-t2 AND t1<t2):
     RETURN
[/code]

   ================

This is a demo using a 52-byte array of the m/c conversion of my shell sort. I used 52 bytes so that I could put in the upper & lower case letters and then jumble them up, so that I could easily check that the sorted result was correct. It runs the timing loop 200 times, 100 with the USR call and 100 without, and takes the difference/100 to get the USR time (.02 second).

Array_Sort2.BAS [code]
   5 CLEAR 29999: REM M/C Shell Sort demo
   6 DEF FN t()=(65536*PEEK 23674+256*PEEK 23673+PEEK 23672)/50
  10 DIM v$(52,1): DIM t(2,3)
     FOR i=1 TO 52:
          LET v$(i)=CHR$ (i+64+(6 AND i>26)):
     NEXT i: GO SUB 80
  15 FOR i=1 TO 50:
          LET o=INT (RND*50)+1: LET n=INT (RND*50)+1:
          LET o$=v$(o): LET v$(o)=v$(n): LET v$(n)=o$:
     NEXT i: GO SUB 80
  25 FOR t=1 TO 2:
       GO SUB 90: LET t(t,1)=time: PRINT t;":Start    : ";t(t,1)
       FOR r=1 TO 100
  35      IF t=1 THEN LET bc=0
  40      IF t=2 THEN LET bc=0: LET bc=USR 30010
  45   NEXT r:
       GO SUB 90: LET t(t,2)=time: LET t(t,3)=t(t,2)-t(t,1)
       PRINT t;":Finish   : ";t(t,2)'t;":Duration : ";t(t,3)
     NEXT t
  75 GO SUB 80:
     PRINT "  Sort Time: ";(t(2,3)-t(1,3))/100: STOP
  80 FOR i=1 TO 52:
          PRINT v$(i);:
     NEXT i: PRINT : RETURN
  90 LET t1=FN t(): LET t2=FN t():
     LET time=t1-(t1-t2 AND t1<t2): RETURN
[/code]

*****

Array_Sort2.ASM [code]
        org  30000

CH_ADD: equ  23645
        defm "v$()"
JLMT:   defs 4
LH:     defs 2

        ld   bc,(CH_ADD)
        push bc
        ld   bc,30000
        ld   (CH_ADD),bc
        call $28b2
        pop  bc              ;HL=address of v$()
        ld   (CH_ADD),bc
        ld   bc,8
        add  hl,bc
        dec  hl              ;HL=address of 1st element in v$()-1
        ld   (LH),hl
        ld   ix,JLMT
        ld   d,0
        ld   (IX+2),31       ;  =m initial value
SETEND: ld   a,52
        sub  (IX+2)
        ld   b,a             ;B =52-m
        ld   c,0
FORS:   inc  c               ;C =s
        ld   (IX+0),c        ;  =j=s             ROW j INDEX
        ld   a,c
LINE50: add  a,(IX+2)        ;A =t=j+m
        ld   (IX+3),a        ;                   ROW t INDEX
        ld   hl,(LH)         ;                   BASE ADDRESS
        ld   e,(IX+0)        ;E =j               ROW j INDEX
        add  hl,de           ;                   ROW j ADDRESS
        ld   a,(hl)          ;A =l$=v$(j)
        ld   (IX+1),a        ;  =l$=v$(j)
        push hl              ;                   ROW j ADDRESS
        ld   hl,(LH)         ;                   BASE ADDRESS
        ld   e,(IX+3)        ;E =t               ROW t INDEX
        add  hl,de           ;                   ROW t ADDRESS
        cp   (hl)            ;A=l$ cp (hl)=v$(t)
        jr   c,NEXTS1

SWITCH: ld   a,(hl)          ;A = v$(t)
        pop  hl              ;                   ROW j ADDRESS
        ld   (hl),a          ;(hl)=v$(j)=v$(t)
        ld   hl,(LH)         ;                   BASE ADDRESS
        ld   e,(IX+3)        ;E =t               ROW t INDEX
        add  hl,de           ;                   ROW t ADDRESS
        ld   a,(IX+1)        ;  =l$
        ld   (hl),a          ;LET v$(t)=l$

        ld   a,(IX+2)        ;  =m
        sub  (IX+0)          ;  =m-j
        jr   nc,NEXTS2       ;if m>=j
        neg                  ;  =j-m
        ld   (IX+0),a        ; j=j-m
        jr   LINE50

NEXTS1: pop  hl
NEXTS2: dec  b
        jr   nz,FORS
        ld   a,1
        cp   (IX+2)
        ret  z               ;ret if m=1
        dec  (IX+2)
        srl  (IX+2)
        jr   SETEND
[/code]

   ================

My m/c sort on a 4-char column in an 80,32 array takes about 3 seconds, rather than the 5 minutes for the BASIC version. Here's the full listing.

agessort.asm [code]
        org  60117
SET_T:  equ  60032
STORES: equ  $2ab6           ;to calculator stack: string
STAKA:  equ  $2d28           ;to calculator stack: A
FPTOBC: equ  $2dA2           ;from calculator stack: BC

SORT:   call SET_T           ;***
        ld   bc,8
        add  hl,bc           ;HL=address of 1st element in c$()
        ld   ix,JLMT         ;***
        ld   (IX+1),e        ;  =key offset in row: 0,4,8,12
        ld   (IX+2),63       ;  =m initial value
        ld   (IX+4),l
        ld   (IX+5),h
SETEND: ld   a,80
        sub  (IX+2)
        ld   d,a             ;D =80-m
        ld   e,0
FORS:   inc  e               ;E =s
        ld   (IX+0),e        ;  =j=s             ROW j INDEX
        ld   a,e
LINE50: add  a,(IX+2)        ;A =t=j+m
        ld   (IX+3),a        ;                   ROW t INDEX
        push de
        ld   a,(IX+0)        ;A =j               ROW j INDEX
        call GETROW          ;***HL=c$(j) address
        push hl              ;save c$(j) address
        ld   de,TMPROW       ;***
        ld   bc,32
        ldir                 ;  =l$=c$(j)        TMPROW=c$(j)
        ld   a,(IX+3)        ;A =t               ROW t INDEX
        call GETROW          ;***HL=c$(t) address
        push hl              ;save c$(t) address
        call STAKEY          ;***
        ld   hl,TMPROW       ;***
        call STAKEY          ;***
        ld   b,$12
        rst  $28             ;start calculator
        defb $12             ;x$>=y$
        defb $38
        call FPTOBC          ;BC=TRUE or FALSE
        ld   a,c
        or   b
        jr   nz,NEXTS1       ;jump if c$(t)>=c$(j)
SWITCH: pop  hl              ;get c$(t) address
        pop  de              ;get c$(j) address
        push hl              ;save c$(t) address
        ld   bc,32
        ldir
        ld   hl,TMPROW       ;***
        pop  de              ;get c$(t) address
        ld   bc,32
        ldir
        ld   a,(IX+2)        ;  =m
        sub  (IX+0)          ;  =m-j
        jr   nc,NEXTS2       ;if m>=j
        neg                  ;  =j-m
        ld   (IX+0),a        ; j=j-m
        pop  de
        jr   LINE50
NEXTS1: pop  hl
        pop  hl
NEXTS2: pop  de
        dec  d
        jr   nz,FORS
        ld   a,1
        cp   (IX+2)
        ret  z               ;ret if m=1
        dec  (IX+2)
        srl  (IX+2)
        jr   SETEND
GETROW: dec  a               ;A =row index-1
        call STAKA
        ld   a,32
        call STAKA
        rst  $28             ;start calculator
        defb $04             ;multiply           (ROW INDEX-1)*32
        defb $38
        call FPTOBC          ;BC=row offset
        ld   l,(IX+4)
        ld   h,(IX+5)        ;HL=                BASE ADDRESS
        add  hl,bc           ;                   ROW ADDRESS
        ret
STAKEY: ld   d,0
        ld   e,(IX+1)
        add  hl,de
        ex   de,hl           ;DE=c$(?) key address
        ld   bc,4            ;BC=c$(?) key length
        call STORES
        ret

JLMT:   defs 4               ;(IX+0)=j;(IX+1)=e;(IX+2)=m;(IX+3)=t;
LH:     defs 2               ;(IX+4,5)=c$() base address;
TMPROW: defs 32              ;(IX+6,37)=c$(j)
[/code]

The call to SET_T is to get the array location and key offset from the DEFADD workspace, putting them in HL & DE respectively. Other called routines are either in the listing or in the ROM. The ROM calculator is used for multiplication and comparing keys. The starting values at 60131 & 60141 are dependent on the number of rows in the array; plus there are various places where the row length of 32 is explicit. Lines marked '***' use absolute addresses which would need to be altered if the routine was moved. It would work with up to 255 rows of up to 255 chars long (presuming that it were altered to take the dimensions as additional FN parameters, as 80,32 is hard-coded at present).



**********************************************************************


** Rotate a 3x3 array through 90 degrees
   =====================================

Here's a little BASIC demo of a routine which will rotate any 2D square array clockwise by 90 degrees. As Z80 assembler doesn't know about arrays I'm just using a simple 1D string as the "array", plus a separate one for the rotated result. So it's just rearranging stuff in a sequential string of bytes; the "rotation" is in the eye of the beholder.

Line 30 is the line which would be converted to assembler; the rest is just setup and presentation.

Array_Rotate1.BAS [code]
  10 FOR d=2 TO 5:
       DIM a$(d*d): DIM b$(d*d): LET c=CODE "A"
  20   FOR a=1 TO d: FOR b=1 TO d:
         LET a$((a-1)*d+b)=CHR$ c: LET c=c+1:
       NEXT b: NEXT a
  25   FOR z=1 TO d: PRINT a$((z-1)*d+1 TO z*d): NEXT z: PRINT
  30   LET c=1: FOR a=d TO d*d STEP d: LET k=c:
         FOR b=a TO a-d+1 STEP -1:
           LET b$(b)=a$(k): LET k=k+d:
         NEXT b:
       LET c=c+1: NEXT a
  35   FOR z=1 TO d: PRINT b$((z-1)*d+1 TO z*d): NEXT z: PRINT
  40 PAUSE 0: CLS: NEXT d: STOP
[/code]

   =======================================

Here's an assembler version of my BASIC routine which will work for squares up to 16x16, with a little BASIC demo to show that it works (the demo only works up to 5x5, as 'array' is 25 long).

Array_Rotate2.BAS [code]
  10 CLEAR 65399: LET dims=5: LET m=dims*dims: DIM a$(m)
  15 FOR s=0 TO 0 STEP 0
  20 FOR a=1 TO m: LET a$(a)=CHR$ (PEEK (65399+a)): NEXT a
  25 FOR a=1 TO dims: PRINT a$((a-1)*dims+1 TO a*dims): NEXT a: PRINT
  30 RANDOMIZE USR 65450
  35 FOR a=65425 TO 65449: POKE a-25,PEEK a: NEXT a
  40 NEXT s
[/code]

Array_Rotate2.ASM [code]
        org  65400
dims:   equ  5
array:  defm "ABCDEFGHIJKLMNOPQRSTUVWXY"
brray:  defs dims*dims

        org  65450
rotate: exx
        ld   c,1             ;C'=c
        ld   a,dims          ;A =a
LOOPA:  ld   e,c             ;E'=k =C'
        ld   b,a             ;B'=a =A
        sub  dims
        inc  a
        ld   d,a             ;D'=a-d+1
        ld   a,b             ;A =b
LOOPB:  ex   af,af'
        ld   a,e             ;A'=k =E'

        exx
        ld   b,0             ;B =0
        ex   af,af'          ;A =b
        ld   hl,brray-1      ;HL=b$() pointer
        ld   c,a             ;C =b
        add  hl,bc
        ex   de,hl           ;DE=b$(b) pointer
        ld   hl,array-1      ;HL=a$() pointer
        ex   af,af'
        ld   c,a             ;A'=k
        add  hl,bc           ;HL=a$(k) pointer
        ld   c,(hl)
        ex   de,hl
        ld   (hl),c

        ex   af,af'
        dec  a               ;A =b-1
        exx
        cp   d               ;D'=a-d+1
        ex   af,af'
        ld   a,e             ;A'=E'
        add  a,dims
        ld   e,a             ;E'=k =k+d
        ex   af,af'
        jr   nc,LOOPB
        inc  c               ;C'=c =c+1
        ld   a,b             ;A =B'=a
        add  a,dims          ;A =a =a+d
       ;ld   b,a             ;B'=A =a+d
        cp   dims*dims
        jr   z,LOOPA
        jr   c,LOOPA
        exx
        ret
[/code]


**********************************************************************


** saving time populating large arrays
   ===================================

I use a variation on this idea for storing machine code at the end of programs without interfering with LIST, then it occurred to me that it would also be useful for avoiding having to re-populate arrays once they have been defined, and also for protecting variables from CLEAR.

The general idea is that variables to be preserved are stored between the end of PROG and the beginning of VARS. If a program uses a large array which would normally be populated at the start of the program every time, this routine enables it to be populated just once, after which it is saved, hidden at the end of the program, and then restored at the start, which is a lot quicker than reloading it every time. As long as it's re-hidden before the end of the program (or else by calling the routine as a direct command) it will be preserved from RUN and CLEAR and saved along with the program ...

... except when using BASin. Whereas a normal Speccy program SAVE saves a continuous block from the start of PROG to the end of VARS, BASin appears to save the two segments contiguously but separately, thus missing out anything in between.

Here's the routine. It just uses a small array as an example to make it easy to check. The variables offset, hlen, alen & check need to be set appropriately for the dimensions of the array. The idea could be expanded fairly easily to cater for multiple arrays. RUN 9991 to populate the array then RUN to test.

Array_Populate.BAS [code]
     REM check if array d$(6,4) is already in place
     REM header: 1+2+1+2+2 = 8 bytes + 6*4 = length 32
     REM  byte1 = 11000000 + CODE "d" - 96 = 196
     REM  bytes2,3 = length of dims + elements + 1 = 29 (header-3)
     REM  byte4 = dims# = 2
     REM  bytes5,6 = 6
     REM  bytes7,8 = 4
     REM header: 196,29,0,2,6,0,4,0
     REM checksum: 196*8 + 29*7 + 0*6 + 2*5 + 6*4 + 0*3 + 4*2 + 0*1 = 1813

  10 DEF FN p(a)=PEEK a+256*PEEK (a+1):
     DEF FN g(v)=v-FN h(v)*256: DEF FN h(v)=INT (v/256)

  11 LET offset=24: LET hlen=8: LET alen=32: GO SUB 9999:
     IF check<>sum THEN PRINT "d$() undefined": STOP
  12 LET vars=FN p(23627)-alen:
     POKE 23670,FN g(vars): POKE 23671,FN h(vars):
     POKE 23627,PEEK 23670: POKE 23628,PEEK 23671: PRINT "d$() available":
     FOR a=1 TO 6: PRINT d$(a): NEXT a

9990 GO TO 9998

9991 LET offset=24: LET hlen=8: LET alen=32: GO SUB 9999:
     IF check=sum THEN PRINT "d$() hidden": STOP
9992 LET offset=-hlen: GO SUB 9999:
     IF check=sum THEN PRINT "d$() available": GO TO 9998
9993 CLEAR: DIM d$(6,4): PRINT "populating d$()"
9994 FOR a=1 TO 6: READ d$(a): NEXT a:
     DATA "aaaa","bbbb","cccc","dddd","eeee","ffff"
9998 LET alen=32: LET vars=FN p(23627)+alen:
     POKE 23670,FN g(vars): POKE 23671,FN h(vars):
     POKE 23627,PEEK 23670: POKE 23628,PEEK 23671: PRINT "d$() hidden":
     STOP
9999 LET vars=FN p(23627): LET check=1813: LET sum=0:
     FOR n=hlen TO 1 STEP -1: LET sum=sum+PEEK (vars-offset-n)*n: NEXT n:
     RETURN
[/code]


**********************************************************************


** Compact a String Array
   ======================

Here's a routine to compact a multi-dimensional string array into an indexed 1D string array with trailing spaces removed from every item. These can then be saved & loaded separately, or embedded in BASIC as explained in "saving time populating large arrays".

9900 populates the DATA array (put your own code here).
9902 saves various DATA array info in FN x().
9903 moves VARS past the DATA array so that it's protected from CLEAR.
9904 DIMs the index array and changes the DATA array to 1-dimensional.
9920-9935 compact the DATA array.
9942 updates the DATA array header to match its new size.
9950 moves down the index array to be immediately after the DATA array.
9952 CLEARs the variables except for the compacted DATA array & index.
9959 lists the items in the compacted DATA array.

Note that FN x() in line 2 doesn't actually do anything; it's just used to allocate a protected area for those variables in its parameter list. Lines in [color=blue]blue[/color] would need altering if different array names were to be used. Each DATA array item's entry in the index array consists of a 2-byte pointer and a 1-byte length.

Array_Compact.BAS [code]
  10 DEF FN x(y$,z$,d,f,l,n,o,s,t,v,x)=0:
  11 REM protected variables area:
  12 REM y$= new index parameters; z$ = old index parameters:
  13 REM f = FN x() variables address; d = number of dims in DATA array:
  14 REM s = space used in DATA array header for 2nd,etc. dims:
  15 REM t = total length of data in DATA array; l = last element length:
  16 REM x = required number of index entries; v = VARS:
  17 REM o = old index address; n = new index address
  23 DEF FN g(v)=v-FN h(v)*256: DEF FN h(v)=INT (v/256):
     DEF FN p(a)=PEEK a+256*PEEK (a+1): DEF FN c()=FN p(23621)
9899 REM RUN 9900 to load & compact the array:
     REM the compacted array + index will overwrite the original array:
     REM any letters may be used for the DATA array & index names:
     REM the DATA array should have two or more dimensions
9900 {10}{01}DIM a$(3,3,9): RESTORE 9900:{10}{00}
     {10}{01}FOR a=1 TO 3: FOR b=1 TO 3: READ a$(a,b): NEXT b: NEXT a:{10}{00}
     DATA "The","quick","brown","fox","jumps","over","the","lazy","dog.":
     REM replace line 9900 with code to DIM & load DATA into array
9902 RESTORE 2: LET defa=FN p(23639)+8:
     POKE 23563,FN g(defa): POKE 23564,FN h(defa):
     LET f=defa: LET v=FN p(23627): LET d=PEEK (v+3): LET s=(d-1)*2:
     LET t=FN p(v+1)-1-d*2: LET l=FN p(v+4+(d*2)-2): LET x=t/l:
     REM total element length / last element length = index entries
9903 LET o=v+3+FN p(v+1): POKE 23627,FN g(o): POKE 23628,FN h(o):
     REM shift VARS past DATA array while adjusting header
9904 {10}{01}CLEAR: DIM b$(x,3): POKE v+1,FN g(t+3+s): POKE v+2,FN h(t+3+s):{10}{00}
     POKE v+3,1: POKE v+4,FN g(t+s): POKE v+5,FN h(t+s):
     POKE 23627,FN g(v): POKE 23628,FN h(v): REM restore VARS
9920 LET xs=1: LET xa=xs: FOR a=s+1 TO s+t-l+1 STEP l: FOR b=l TO 1 STEP -1:
     {10}{01}IF a$(a+b-1)<>" " THEN LET a$(xs TO xs+b-1)=a$(a TO a+b-1): GO TO 9932{10}{00}
9931 NEXT b
9932 {10}{01}LET b$(xa)=CHR$ FN g(xs)+CHR$ FN h(xs)+CHR$ b: LET xs=xs+b: LET xa=xa+1{10}{00}
9935 NEXT a
9940 PRINT "Old size = ";t: LET t=xs-1:
9942 POKE v+1,FN g(t+3): POKE v+2,FN h(t+3): POKE v+4,FN g(t): POKE v+5,FN h(t)
9944 PRINT "New size = ";t;" + ";x*3;" = ";t+x*3: LET n=v+3+FN p(v+1): LET x=x*3+8
9950 POKE f+4,FN g(n): POKE f+5,FN h(n): POKE f+6,FN g(x): POKE f+7,FN h(x):
     POKE f+13,FN g(o): POKE f+14,FN h(o): POKE f+15,FN g(x): POKE f+16,FN h(x):
     LET y$=z$: REM move down index to be immediately after DATA array
9952 POKE 23627,FN g(n+x): POKE 23628,FN h(n+x): INPUT "Press ENTER ";z$:
     CLEAR: POKE 23627,FN g(v): POKE 23628,FN h(v):
     LET vars=v: POKE 23563,0: POKE 23564,0:
     REM restore VARS & reset DEFADD, retaining compacted DATA array & index
9958 REM check DATA array & index
9959 FOR a=1 TO FN p(vars+3+FN p(vars+1)+4):
       {10}{01}LET s=CODE b$(a,1)+256*CODE b$(a,2):{10}{00}
       {10}{01}PRINT a;TAB 3;a$(s TO s+CODE b$(a,3)-1);TAB 16;s;TAB 24;CODE b$(a,3):{10}{00}
     NEXT a
[/code]


**********************************************************************


** What's the deal with hash tables, anyway?
   =========================================

I've just discovered this document:
http://www.cs.cmu.edu/~tcortina/15-121sp10/Unit08B.pdf
from Carnegie Melon University, which gives a simple introduction to the topic without going anywhere near any 35-page C programs or having pages littered with inscrutable mathematical formulae. Any additional (simple) techniques for working with hash tables are welcome.

A hash table is the means of implementing an associative array. Those familiar with the awk programming language will be familiar with these, although (like me) might not have thought much about how they worked. They're a means of associating data identified by a complex key with a table of data identified by a simple key.

For example, I might have a menagerie containing various species of dog, cat, pig, cow, ant, bee, hen, emu, fox, elk, rat & yak. If I want to look up information about my cows, how do I do that? Look up the "cow'th" record? Using a simple numeric mapping based upon the names would produce keys with widely disparate values which would require a table with lots of wasted space. Alternatively, the data records could be stored contiguously and some method of searching employed to find the correct one, which saves space but wastes time.

It would be useful to be able to combine the best elements of both these options, to save both space & time, and be able to determine that the "cow'th" record was the 4th record and then to refer directly to record 4 whenever cows were mentioned. This is what an associative array does, by means of a hash table.

It's probably worth mentioning here that, although I'm using a very small table as an example, in practice hash tables do not give good performance with small tables, as the time taken to compute the hash function each time will probably be longer than a simple search through the data for the key.

So, we have:
[list]
[*]a set of input records, each with an input key: ant,bee,cat,...
[*]a hash function, converting input keys to hash keys:
[*]a hash table, associating hash keys with data keys:
[*]a data table, each record with a data key: 1,2,3,...
[/list]

The hash function can be any function which maps input keys to hash keys; for numeric keys the simplest would be "key MOD hashtablesize"; for strings it would be "hashcode MOD hashtablesize", where hashcode for a string of length 'n' characters is calculated by:
s0*31^(n-1) + s1*31^(n-2) + ... + sn-1
(I don't know how the base 31 modifier is arrived at; this is from the CMU document. It works, anyway. This also applies to the limiting of hash table sizes to prime numbers.) Remember that "MOD x" gives results in the range 0 to x-1, so all results should be +1 to work as Spectrum array pointers.

This short program demonstrates a simple routine for building a hash table.
http://www.users.globalnet.co.uk/~jg27paw4/pourri/hash-k4.bas
The smallest hash table for the menagerie which has no collisions (ie. every input key generates a different hash key) has 47 entries, although table sizes 13,19,37 produce only 2,2,1 collisions respectively. So a better option might be to choose one of the smaller tables and alter the hash function slightly to avoid the collisions - let's say table 19.

One way to do this is to use a second function which calculates a pointer to a table of modifiers, such that one of the hash keys of a colliding pair is altered and one isn't. A list of unassigned hash keys is needed in order to choose suitable modifier values. This next program uses the original function in reverse (less the middle letter) to generate the secondary key, shows the range of secondary key values, and lists the nearest unassigned hash keys both above & below the primary key for table 19.
http://www.users.globalnet.co.uk/~jg27paw4/pourri/hash-k4b.bas
The "fox" & "cow" entries have collisions in the 'h' column but not in the 'm' column, so modifiers should be assigned for "fox" & "cow".

Free hash keys are: 1,2,3,4,5,6,11,13,18; so "fox" can use 10+1=11 and "cow" can use 14+4=18. The modifier table has 19 entries, with entry m=17 for "fox" =1 and the entry m=3 for "cow" =4, the rest zero. It might be noted that this makes the hash key range 7-19, so the size of the hash table could be reduced to 13 entries by appending "-6" to the primary hash function. Similarly for the modifier table, as its key range is 2-18.

This next program shows the modified hash function and the application of the modifier table to give a hash table with no collisions. It also does a timing comparison between selecting all 12 data records by hash key and by sequential search.
http://www.users.globalnet.co.uk/~jg27paw4/pourri/hash-k4c.bas
It might be noted that all the calculations and adjustments could be programmed and done automatically; only the specification of the hash functions themselves require manual intervention.

For a slightly more substantial test I've included a version of Kweepa's routine for the Spectrum keywords, converted to BASIC. It builds the hash table and then compares searching for every keyword both sequentially and via the hash table. The times are 75 seconds and 49 seconds respectively, so it can be seen that the data table doesn't have to be particularly big before some advantage can be obtained from using a hash table for lookups.
http://www.users.globalnet.co.uk/~jg27paw4/pourri/hash-key.bas
Here's a TAP file with the four programs:
http://www.users.globalnet.co.uk/~jg27paw4/pourri/hash-key.tap

There's a shed load of vastly more complicated & confusing stuff about hash tables on the web. This Wiki page is as good a starting point as any:
http://en.wikipedia.org/wiki/Hash_table
That 35-page C program which I mentioned at the start is here:
http://burtleburtle.net/bob/hash/perfect.html
http://burtleburtle.net/bob/c/perfect.c


**********************************************************************
