Zusätzliches WOrt in Hashtabelle einfügen?

[schöni]

Hallo,

in diesem Quelltext gibt es eine Hashtabelle mit den in Pascal reservierten Wörtern. Allerdings fehlt das Wort "ASM". An welcher Stelle muss ich das einfügen, damit der hier verwendete Algo das eigefügte Wort auch findet und ohne die bisherige Wortfolge für den verwendeten Algo unbrauchbar zu machen.

Hier ist die Quelle:

Delphi-Quellcode:

unit Reserved {word or directive identificator };    
{ Under GNU License            }
{ JOAO PAULO SCHWARZ SCHULER }
{ http://www.schulers.com      }
{ Turbo Pascal Source          }
{ Free Pascal Source for DOS   }
{ Free Pascal Source for Linux }
{ Delphi Source                }


interface

Const HashingNumber = 23;
      MaxOnHashLine = 10;

type STR20 = string[20];

Const RWords : array[0..HashingNumber-1,0..MaxOnHashLine-1] of str20 =
(
{00}  ('CONST','OR','TYPE','','','','','','',''),
{01}  ('SHL','FOR','DESTRUCTOR','INHERITED','PROPERTY','','','','',''),
{02}  ('TO','OBJECT','TRY','CDECL','','','','','',''),
{03}  ('VAR','ASSEMBLER','','','','','','','',''),
{04}  ('AND','FORWARD','THEN','IMPLEMENTATION','LIBRARY','RAISE','','','',''),
{05}  ('IF','UNTIL','PUBLISHED','STORED','','','','','',''),
{06}  ('SET','CLASS','INITIALIZATION','THREADVAR','','','','','',''),
{07}  ('LABEL','PROGRAM','SHR','FINALIZATION','NODEFAULT','','','','',''),
{08}  ('CASE','END','DISPID','INDEX','RESIDENT','','','','',''),
{09}  ('ABSOLUTE','WHILE','DO','AUTOMATED','','','','','',''),
{10}  ('RECORD','PACKED','INLINE','PUBLIC','PRIVATE','AS','FAR','OVERRIDE','',''),
{11}  ('OF','STRING','NOT','DEFAULT','DYNAMIC','MESSAGE','','','',''),
{12}  ('FILE','REPEAT','BEGIN','','','','','','',''),
{13}  ('IN','EXTERNAL','INTERFACE','EXPORTS','NAME','STDCALL','','','',''),
{14}  ('GOTO','PROCEDURE','','','','','','','',''),
{15}  ('DOWNTO','ARRAY','PROTECTED','','','','','','',''),
{16}  ('FUNCTION','','','','','','','','',''),
{17}  ('MOD','WITH','','','','','','','',''),
{18}  ('IS','NEAR','','','','','','','',''),
{19}  ('XOR','CONSTRUCTOR','','','','','','','',''),
{20}  ('DIV','NIL','EXCEPT','','','','','','',''),
{21}  ('ELSE','UNIT','USES','FINALLY','ABSTRACT','','','','',''),
{22}  ('EXPORT','PASCAL','VIRTUAL','','','','','','',''));

function Key(S:string;Divisor:byte):word;
{calculates de hashing code}
{ calcula chave de acesso }

function GetHash(S:String):word;

function IsReserved(S:string):boolean;
{ checks if S is a Reserved word or a directive}


implementation

function Key(S:string;Divisor:byte):word;
{ calcula chave de acesso }
var I:integer;
    SOMA:longint;
begin
SOMA:=0;
for I:=1 to length(S) do
    inc(SOMA,ord(S[I]));
Key:=SOMA mod Divisor;
end;

function GetHash(S:String):word;
begin
GetHash:=Key(S,HashingNumber);
end;

function IsReserved(S:string):boolean;
{ checks if S is a Reserved word or a directive}
var HN,L:word;
    C:word;
    Found:boolean;
begin
L:=Length(S);
for C:=1 to L
    do S[C]:=UpCase(S[C]);

HN:=GetHash(S);
C:=0;
Found:=false;
while (C<MaxOnHashLine) and (RWORDS[HN,C]<>'') and not(Found) do
      begin
      Found:=Found or (S=RWORDS[HN,C]);
      inc(C);
      end;
IsReserved:=Found;
end;


end. {of unit}

Aus dem Quellcode werde ich da nicht schlau. Wo gibt es Literatur zu diesem Thema, aber bitte praxisnah.

Oder ist die Einfügestelle völlig egal. Key berechnet dann einen Hashwert, abhängig von der Einfügestelle und dem Wort.

Allerdings kann ich mir nicht wirklich vostellen, das der Einfügeort echt egal ist. Eher glaube ich das die beherigen Pascal Wörter algo-bedingt an ebendiesen Stellen stehen müssen.

Wer kann hier Licht ins Dunkel bringen?

Ich möchte gerne das fehlende Wort 'ASM' ergänzen und wenn ich später noch andere fehlende Wörter finden sollte, diese auch ergänzen.

Die Konstante RWords enthält die Hash-Tabelle.

.

[Namenloser]

Den Index der Zeile, in der ein Wort stehen muss, gibt GetHash(Wort) an.

GetHash('ASM') ergibt 18. Also muss 'ASM' in die Zeile {18} eingefügt werden, und zwar so, dass das erste '' ersetzt wird:
{18}  ('IS','NEAR','ASM','','','','','','',''),

[schöni]

Danke wie verrückt. So füge ich also ein neues Wort ein, indem ich den Hash Wert mit GetHash() ermittle und dann einen Index (hier 18) in die Tabelle erhalte. Dann füge ich das neue Wort da ein, wo das erste '' ist. Verstanden. Von da ais sind es nicht allzu viele Wörter in der Tabellenzeile, dürfte also dann schnell gefunden sein.

[shmia]

Wahrscheinlich wäre eine lineare Suche bei der geringen Anzahl an Schlüsseln nicht langsamer als diese Hashtabelle.
Ausserdem wird enthält das Array RWords jede Menge Luft (23*10*(20+1) = 4830 Bytes); die lineare Suche bräuchte nicht mal ein Viertel davon.

[schöni]

Zitat von shmia:

Wahrscheinlich wäre eine lineare Suche bei der geringen Anzahl an Schlüsseln nicht langsamer als diese Hashtabelle.
Ausserdem wird enthält das Array RWords jede Menge Luft (23*10*(20+1) = 4830 Bytes); die lineare Suche bräuchte nicht mal ein Viertel davon.

Interessanter Gedanke. Ok, ich werde beides probieren. Schaun mer mal.

[Christian Seehase]

Zitat von shmia:

Wahrscheinlich wäre eine lineare Suche bei der geringen Anzahl an Schlüsseln nicht langsamer als diese Hashtabelle.
Ausserdem wird enthält das Array RWords jede Menge Luft (23*10*(20+1) = 4830 Bytes); die lineare Suche bräuchte nicht mal ein Viertel davon.

Von der binären Suche in einer sortierten StringListe mal ganz zu schweigen
Ich hab's mal ausprobiert: Fast dreimal so schnell, wie die Lösung mit Hashtable.

[shmia]

Ich denke es hängt auch davon ab, ob die Menge an Schlüsseln sich nie verändert oder ob zur Laufzeit Schlüssel hinzugefügt oder entfernt werden sollen.

a.) feste Menge an Schlüsseln
-> binäre Suche, Interpolationssuche oder quadratische Binärsuche liefert das beste Ergebnis

b.) zur Laufzeit wird eine begrenzte Menge an Schlüsseln hinzugefügt
-> Hashverfahren können genützt werden
Bei zu hohem Füllungsgrad der Hashtabelle wird die Suche aber langsam.

c.) zur Laufzeit dürfen auch Schlüssel gelöscht werden
-> Hashverfahren versagen, weil das Löschen von Schlüsseln nicht erlaubt ist