Hashtabeller i Delphi

Hvis man arbejder med store mængder data i hukommelsen er det ofte nødvendigt at pålægge dem en form for orden og struktur. Arrays, lister, træer, stakke er alle eksempler herpå. Når man vælger hvilken metode man vil benytte er der flere ting der skal overvejes, f.eks. hvor hurtigt man kan hente/indsætte elementer, samt hvilken type data der skal opbevares.
De ovenstående datastrukturer har alle fordele og ulemper, som jeg ikke vil komme nærmere ind på her. I stedet vil jeg give et eksempel på hvordan man i Delphi kan konstruere en Hashtabel, som kan indeholde et vilkårligt element, så længe elementet har en unik nøgle tilknyttet, og tilgå/indsætte disse på en effektiv måde.
Mit mål her er kun at beskrive idéen bag en hashtabel, ikke at gå i detaljer med hvordan den implementeres. Til sidst i teksten er der dog et eksempel på en hashtabel, baseret på nedenstående idé.

En hash-funktion er en funktion der som input tager en tekststreng, og som output genererer en nøgle. Funktionen er "many-to-one", hvilket vil sige at flere strenge godt kan give den samme nøgle. Desto færre gange den samme nøgle bliver genereret ud fra forskellige strenge, desto bedre.

Tabellen består af et array af lister. Listerne indholder elementerne i tabellen. Tabellens funktionalitet illustreres nok nemmest med et eksempel. Lad os sige vi ønsker at indsætte superhelte. Allerførst skal vi bestemme os for hvilken streng vi skal sende til hashfunktionen. Strengen skal kunne identificerer den pågældende superhelt unikt, så vi vælger hans heltenavn (supermand, batman osv.). Hash-funktionen genererer nu en integer. Denne integer benytter vi til at indeksere ind i arrayet af lister. Såfremt vores superhelt ikke allerede eksisterer i listen, bliver han tilføjet.
Vi har nu en struktur som ligner denne:

[0]-list|supermand|
[1]-list|
[2]-list|batman|robin|
[3]-list|hulk|
[4]-null
[5]-null


Arrayet størrelse er en parameter til hashtabellens konstruktør.
Når så et element skal hentes ud igen er fremgangsmåden den samme, blot skal vi søge igennem den pågældende liste, indtil den rigtige superhelt er fundet.
Det er her det er nødvendigt at hashfunktionen fordeler nøglerne så ligeligt som overhovedet muligt, ellers bliver listerne for store, hvilket resulterer i at der er meget at søge igennem før det rigtige element er fundet. I værste tilfælde alle elmenterne (sker aldrig med mange elementer og god hash).
Når hash-funktionen fungerer fornuftigt, vil man tilgengæld opnå en effektivitet næsten på højde med at indeksere i et array.
Jeg har også tilføjet en sorteringsfunktion.
Da hash-tabellen ikke har noget som helst kendskab til de elementer den indeholder er det nødvendigt at sende en sammenligningsfunktion med som argument.

unit utils;

interface

uses
  Classes,
  CUser;

{Would propably be more effective to implement my own list, but this will do}
type PTList = ^TList;

type
  PElement = ^Element;
  Element = class(TObject)
    private
      key : string;
      e : Pointer;
    public
      Constructor Create(key : string; e : Pointer);
      function getKey() : string;
      function getElement() : Pointer;
  end;

{Declaration of type HashTable. It has an array of list's}
type
  HashTable = class(TObject)
    private
      table: array of Tlist;
      x : array of integer; //Used by hash function
      tableSize : integer;
      function getHash(key : string): integer;
      procedure merge(pl : PTList);
    public
      Constructor Create(tableSize: integer);
      procedure Insert(key : string; item : Pointer);
      function Get(key : string) : Pointer;
      function Sort(Compare : TListSortCompare) : PTList;
  end;

implementation

{##############################type element###########################################}

{Public functions}
Constructor Element.Create(key : string; e : Pointer);
  begin
    Self.key := key;
    Self.e := e;
  end;

function Element.getKey() : string;
  begin
    result := key;
  end;

function Element.getElement() : Pointer;
  begin
    result := e;
  end;

{##############################type hashTable###########################################}

{Public functions}
Constructor HashTable.Create(tableSize: integer);
  var
    k, s, i, j : integer;
  begin
    SetLength(table, tableSize);
    Self.tableSize := tableSize - 1;

    {Initializing the hash function}
    SetLength(x, 256);
    for i := 0 to 255 do
      begin
        x[i] := i;
      end;
    k := 7;
    for j := 0 to 3 do
      begin
        for i := 0 to 255 do
          begin
            s := x[i];
            k := (k + s) mod 256;
            x[i] := x[k];
            x[k] := s;
          end;
      end;
  end;

procedure HashTable.Insert(key : string; item : Pointer);
  var
    tableIndex : integer;
    pe : PElement;
  begin
    tableIndex := getHash(key);
    if table[tableIndex] = nil Then table[tableIndex] := TList.Create();
    New(pe);
    pe^:= Element.Create(key, item);
    table[tableIndex].add(pe);
  end;

function HashTable.Get(key : string) : Pointer;
  var
    tableIndex, i : integer;
    pe : PElement;
  begin
    result := nil;
    tableIndex := getHash(key);
    if table[tableIndex] <> nil Then
      for i := 0 to (table[tableIndex].Count - 1) do
        begin
          pe := PElement(table[tableIndex].Items[i]);
          if ((pe <> nil) and (pe^.getKey() = key)) Then
                begin
                  result := PElement(pe^.getElement());
                  break;
            end;
        end;
  end;

function HashTable.Sort(Compare : TListSortCompare) : PTList;
  var
    pl : PTList;
  begin
    new(pl);
    pl^ := TList.Create();
    merge(pl);
    pl^.Sort(Compare);
    result := pl;
  end;

{Private functions}
function HashTable.getHash(key : string): integer;
  var
    hash, i : integer;
  begin
    hash := Length(key) mod 256;
    for i := 0 to (Length(key) -1) do
      begin
        hash := integer(key[i]) mod 256;
        hash := x[hash];
      end;
    result := hash mod (tableSize + 1);
  end;

procedure HashTable.merge(pl : PTList);
  var
    i, j : integer;
  begin
    for i := 0 to tableSize do
      begin
        if table[i] <> nil Then
          begin
            for j := 0 to (table[i].Count - 1) do
              begin
                if table[i].Items[j] <> nil Then pl^.add(PUser(PElement(table[i].Items[j])^.getElement()));
              end;
          end;
      end;
  end;

end.

Jakob Justsen