Zusätzliches WOrt in Hashtabelle einfügen?

[Furtbichler]

[QUOTE=shmia;1167302]

Zitat von Furtbichler:

Die Standardimplementierung einer Hash-Tabelle sieht so aus, .."Linear Probing"...

Ich sprach aber von einer brauchbaren Hashmap, also z.B. "chaining" und dynamisch.

Zitat von Furtbichler:

Hashtabellen (nicht gerade diese) sind in puncto Performance bei großen Datenmengen nicht zu schlagen. ... sofern eine dynamische Variante genutzt wird.

Zitat:

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

Für mich ist der Test nicht aussagekräftig, da er zu wenig Fälle betrachtet. Versuch diesen:

Delphi-Quellcode:

for i := 1 to 1000000 do
  for j := 0 to allReservedWordsCount-1 do
    IsReserved(reservedWords[j]);

Er sucht nach allen reservierten Wörtern. Wir können noch ein paar Wörter hinzupacken, die nicht gefunden werden sollen, wenn Du magst. Oder Du schlägst einen anderen Test vor.
Dein Test zeigt aber sehr deutlich, das lineare Suche bei kleinen Listen nicht zu topppen ist. Eine Liste mit 88 Elemente ist hier aber nicht mehr "klein".

Der Test mit folgender Klasse führt bei mir zu erheblichen Geschwindigkeitszuwächsen und hält sich bezüglich Speicherauslastung in Grenzen:

Delphi-Quellcode:

Unit pascalKeywordList;
Interface
Type
  TKeywordBucket = Record
    data: Array[0..10] Of String;
    dataCount: Integer;
  End;
  // A generic chaining hash map using the first character as hash function.
  TKeywordListHash = Array[Char] Of TKeywordBucket;

  TPascalKeywordList = Class
  private
    keywords: TKeywordListHash;
    Procedure FillList;
  public
    Constructor Create;
    Function IsReserved(Const aWord: String): Boolean;
  End;

Implementation
Const
  keywordCount = 88;
  keywordList: Array[0..keyWordCount - 1] 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', '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');

{ TPascalKeywordList }

Constructor TPascalKeywordList.Create;
Begin
  FillList;
End;

Procedure TPascalKeywordList.FillList;
Var
  i: Integer;

  Procedure _FillIntoList(Const keyWord: String);
  Begin
    Assert(Length(keyWord) > 1, 'the keyword to be filled in may not be empty');
    With keywords[keyword[1]] Do Begin
      data[dataCount] := keyWord;
      inc(dataCount);
    End
  End;

Begin
  For I := 0 To keywordCount - 1 Do _FillIntoList(keyWordList[i]);
End;

Function TPascalKeywordList.IsReserved(Const aWord: String): Boolean;
Var
  i: Integer;

Begin
   Assert(Length(aWord) > 1, 'the word to be searched may not be empty');
   With keywords[aWord[1]] Do
    For I := 0 To dataCount - 1 Do
      If data[i] = aWord Then Begin
        result := true;
        exit;
      End;
  result := false;
End;

End.