From: Ingo.Wilken@arbi.informatik.uni-oldenburg.de (Ingo Wilken)
Subject: Re: Befehlsliste geschickt durchsuchen, wie?
Organization: University of Oldenburg, Germany
Date: Fri, 28 Aug 1992 01:16:22 GMT

Moin moin,

stesch@sks.ppc.sub.org (Stefan Scholl) writes:
>Ab wieviel Eintraegen wuerde sich der "Aufwand" fuer Hashing rentieren?
>Ich bin naemlich auch grad am rexxeln. :-) Weiss im Moment noch nicht
>wieviel Befehle es am Ende werden, aber fuer poplige 20 Stueck waere der
>Aufwand wohl zu gross? Dazu muss man sagen, dass die Soft auch auf 68000er
>(lahm) laufen soll.

Hmm.  Je nach Hash-Funktion schon ab wenigen Eintraegen.  Eine simple
Funktion waere z.B. sowas:

#define NUM(c)	(c - 'a')

int hash(s, len)
char *s;
int len;   /* Laenge von s */
{
    int h;
    h = (NUM(s[0]) + 5*NUM(s[3]) + 7*NUM(s[len]) + 11*len) % TABLE_SIZE;
    return(h);
}

Also wir berechnen einen Wert aus dem 1.Buchstaben, dem 3.Buchstaben, dem
letzten Buchstaben und der Laenge des gesuchten Wortes und bilden dieses
mittels modulo auf die Hash-Tabelle ab.

Will man nun wissen, ob ein Wort in der Tabelle ist, so berechnet man den
Hash-Wert und vergleicht mit dem entsprechenden Tabellen-Eintrag (dieser
eine Vergleich ist immer noch noetig, z.B. haben in der obigen Hash-Funktion
die Worte "Bingo" und "Bongo" denselben Hash-Wert):

int is_keyword(s)
char *s;
{
    int h;

    h = hash(s, strlen(s));
    return( strcmp(table[h], s) == 0 );
}


Das Problem ist natuerlich, eine Hash-Funktion zu finden, die 
  (a) fuer zwei verschiedene keywords nie denselben Hash-Wert liefert.
      (Also die Funktion muss injektiv sein.) Man spricht in diesem Fall
      von "pefektem Hashing".
  (b) einen Wertebereich moeglichst vollstaendig ausfuellt (also am besten
      alle Werte von 0 bis ANZAHL_KEYWORDS-1), da die Hash-Werte als Index
      fuer eine Tabelle genommen wird, damit man keine "Loecher" in dieser
      Tabelle hat.  Man spricht dann von "minimalem perfektem Hashing".

Bei einem statischen Datensatz (wie einer Liste von keywords) ist (a) noch
relativ leicht zu erreichen, mit (b) wirds schon schwieriger.  [Lustig wirds
erst bei einem dynamischen Datensatz, wo man sich dann mit der Frage rum-
schlagen muss, was machen wenn zwei Worte denselben Hash-Wert haben und beide
in die Tabelle eingetragen werden muessen.  Aber das ist ja hier nicht das
Problem.]

Puuh, langsam wirds zuviel zu schreiben .  Wer mehr ueber Hashing wissen 
moechte findet genug Stoff in der Informatik-Literatur.  Consult your
local library :-)

Ein kleines Bonbon habe ich aber noch:  Einen Programm-Generator fuer
"fast" minimale perfekte Hash-Funktionen. 

Werde ich morgen (Freitag) abend unter /tmp/perfect-hash.lha auf uniol 
ablegen:
  FTP       :  ftp.informatik.uni-oldenburg.de [134.106.1.9]
  Mailserver:  ftpmail@informatik.uni-oldenburg.de

Beim Mailserver als Subject "request" angeben, im Body dann:
   send /tmp/perfect-hash.lha
Oder noch besser erstmal 'ne Mail mit dem Subject "help" senden :-)


Tschau
Ingo
-- 
Ingo Wilken, CS Student, Univ.of Oldenburg, FRG | You mean I really did all of
wilken@uniol.uucp (..!uunet!unido!uniol!wilken) | dat stuff? Now dat explains
Ingo.Wilken@arbi.informatik.uni-oldenburg.de    | why my head hurts an' why I
wilken@uniol.zer   IRC:Nobody   OL:ingo@faramir | feel so bad!  -Snarf
Newsgroups: de.comp.sys.amiga.misc