Hashen: Integerüberläufe, Hornerschema in Delphi

**skizz**

Ich mache im Augenblick ein Projekt zum Thema:
Hashen von Strings, mithilfe der Divisionsrestmethode:
Strings wandel ich um durch deren ASCII Wert mal der Basis 128.
Problem: Die Zahlen werden recht groß.

Bei der Divisionsrestmethode muss ich diese nun durch m (in der Regel Tabellengröße) teilen.

Dabei gibt es nun ein Hornerschema, welches integer Überläufe verhindert.

Theorie:

h(HAUS) = ( ord(H)*128³ + ord(A)*128² + ord(U)*128 + ord(S)) mod m
H(HAUS)= [ 72*128³ + 65*128² + 85* 128 + 83 ] mod m
= [ ((72*128 + 65)*128 + 85)*128 + 83 ] mod m
= [ ((72 mod m *128 + 65) mod m *128 + 85) mod m *128 + 83 ] mod m

Praxis: Problem dabei ist wie ich wiederholt das mod m hinein bekomme.
(Siehe Theorie oben: Fettgedrucktes.) Das ganze soll immer noch mit einer variablen Länge des Strings möglich sein.

Wikipedia meint im Pseudocode:

h = s[1] mod m
for i in 2...l:
h = (h * 128 + s[i]) mod m

zusammenfalten · markieren

Delphi-Quellcode:

			procedure TForm1.Button1Click(Sender: TObject);

var s : string;

i,d,x,m,laenge,h,ergebnis,c : integer;

pos : integer = 1;

begin

   {Divisionsrestmethode bei Strings

   s speichert den string, i,j zählervariabeln

   power(basis, exponent) = b^exponent, benötigt uses math}

   m := strtoint(edit2.text); //auslesen des Teilers aus einem Editfeld

   s := edit1.Text; // auslesen des strings

   laenge := length(s);

   c:= 1;

 //umrechnung von string in zahlen zur basis b h := ord(s[j])*round(power(128,(laenge-c)));

for i:= 0 to laenge-1 do

   begin

   h := (ord(s[pos])*round(power(128,(laenge-c))) mod m) ;

{   x := (laenge+1-c); das ist die Anzahl der "mod m"'s die ich im Prinzip bei dem obrigen mod m benötige }

   //showmessage(s[j] + inttostr(ord(s[j])));  //prüfen der Ordinaten:

   ergebnis:= ergebnis+h; //summieren der Hashwerte der Einzelnen Ordinaten

   pos:= pos+1;

   c:= c+1;

   end;

 memo1.Text := inttostr(ergebnis); //anzeigen des Ergebnises

   //reset der Variabeln

   ergebnis:= 0;

   c:= 1;

   pos:= 1;

end;

Eine Modifikation meines Codes oder eine Übersetzung des Pseudocodes(sofern er funktioniert) würden mir doch weiter helfen.

MfG

Hashen: Integerüberläufe, Hornerschema in Delphi

Hashen: Integerüberläufe, Hornerschema in Delphi

Forumregeln