Zusätzliches WOrt in Hashtabelle einfügen?

[shmia]

Zitat von Furtbichler:

Zitat von shmia:

Bei zu hohem Füllungsgrad der Hashtabelle wird die Suche aber langsam.

Da bin ich aber ganz anderer Meinung (oder beziehst Du dich auf diese konkrete Implementierung?):
Hashtabellen (nicht gerade diese) sind in Puncto Performance bei großen Datenmengen nicht zu schlagen. Die Performance für das Einfügen, Suchen und Löschen ist stehts O(1), sofern eine dynamische Variante genutzt wird.

Die Standardimplementierung einer Hash-Tabelle sieht so aus, dass es eine bestimmte Anzahl an Buckets (Einträge in einem Array) gibt.
Die Hashfunktion bildet den Schlüssel auf den Index im Array ab.
Sollte ein Bucket aber schon belegt sein, dann nimmt man den nächsten freien Eintrag. ("Linear Probing")
Bei zu hohem Füllungsgrad; also das Array ist schon zu 80% voll; wird immer seltener ein freies Bucket gefunden.
Es bilden sich ganze Ketten von belegten Buckets, die das Suchen und Eintragen von Schlüsseln verlangsamen.
Bei 100% Belegung müssen für die Suche nach einem nichtvorhandenen Schlüssel ALLE Buckets durchsucht werden.
Natürlich kann man Hashtabellen auch anderst strukturieren, z.B. als Array of TList und damit einige dieser Nachteile vermeiden.


Ansonsten ist nach meinen Messung die lineare Suche bei diesem Beispiel schneller!

Delphi-Quellcode:

for i := 1 to 1000000 do
begin
   IsReserved('test');  // Miss
   IsReserved('string');  // Hit
end;

Die Hashtabelle aus Beitrag #1 benötigt ~ 1,32 Sekunden,
die lineare Suche braucht ~ 1,02 Sekunden.

Wer selbst messen möchte:

Delphi-Quellcode:

function IsReservedLinSearch(S:string):Boolean;
const list : array[0..87] of string =
(
'CONST','OR','TYPE',
'SHL','FOR','DESTRUCTOR','INHERITED','PROPERTY',
'TO','OBJECT','TRY','CDECL',
'VAR','ASSEMBLER',
'AND','FORWARD','THEN','IMPLEMENTATION','LIBRARY','RAISE',
'IF','UNTIL','PUBLISHED','STORED',
'SET','CLASS','INITIALIZATION','THREADVAR',
'LABEL','PROGRAM','SHR','FINALIZATION','NODEFAULT',
'CASE','END','DISPID','INDEX','RESIDENT',
'ABSOLUTE','WHILE','DO','AUTOMATED',
'RECORD','PACKED','INLINE','PUBLIC','PRIVATE','AS','FAR','OVERRIDE', //50
'OF','STRING','NOT','DEFAULT','DYNAMIC','MESSAGE',
'FILE','REPEAT','BEGIN',
'IN','EXTERNAL','INTERFACE','EXPORTS','NAME','STDCALL',
'GOTO','PROCEDURE',
'DOWNTO','ARRAY','PROTECTED',
'FUNCTION',
'MOD','WITH',
'IS','NEAR',
'XOR','CONSTRUCTOR',
'DIV','NIL','EXCEPT',
'ELSE','UNIT','USES','FINALLY','ABSTRACT',
'EXPORT','PASCAL','VIRTUAL'
);
var
  i : Integer;
begin
   S := Uppercase(S);
   for i := low(List) to High(List) do
   begin
      if S = list[i] then
      begin
         Result := True;
         Exit;
      end;
   end;
   Result := False;
end;