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
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