Re: HASHING

 BBS: Inland Empire Archive
Date: 06-30-92 (23:23)             Number: 1953
From: JOHN PAYSON                  Refer#: NONE
  To: DARYL POSNETT                 Recvd: NO  
Subj: Re: HASHING                    Conf: (2) Quik_Bas

Nice post on the subject of hashing.  I would also suggest
that for people interested in algorithms, the
Communications of the ACM is a very useful publication.
An excellent hashing function, for example, is as follows:
[please excuse the fact that I've never programmed in
QuickBasic, so this is sort of pseudo-GW-BASIC notreally...

' Hash function: hashes a string into a number from 0 - 255

'Initialization procedure:
  DIM H%(255)
  For I=0 to 255
    H%(I) = I
  Next
  For I=1 to 255
    SwapLoc = Int(Rnd(I))
    XX = H%(I) : H%(I) = H%(SwapLoc) : H%(SwapLoc) = XX
  Next

The important thing this procedure does is to make H% a
permuation.  The exact permutation is unimportant so long
as it's "vaguely randomish".

' DoHash: Sets Result% = Hash of St$
Result% = 0
For I=1 to Len(St$)
  Result% = H%( Result% xor Asc( Mid$( St$, I, 1)) )
Next

This hash function can easily be adapted for other powers
of two by chanching the size of H%.  I forget the original
article this hash function appeared in. It was about two
years ago in COMMUNICATIONS OF THE ACM, I think.  Very
worth reading.

Hope this all is helpful.


--- TBBS v2.1/NM
 * Origin: Chicago Syslink - Berwyn, IL. -   (708)-795-4442 (1:115/622)