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

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

[Klaus01]

Hallo,

vielleicht bin ich im falschen Film,

aber warum rechnest Du mit power.
Und h kann meines Erachtens nicht größer als m werden.


Mein Versuch:

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;

   h := ord(s[1]) mod m; // h = s[1] mod m

   for i:= 2 to laenge-1 do
     begin
       //h := (ord(s[pos])*round(power(128,(laenge-c))) mod m) ;
        h := (h * 128 + ord(s[i])) mod m;  // h = (h * 128 + s[i]) mod m 
    end;

   memo1.Text := intToHex(h,16);

end;

(nicht getestet)

Grüße
Klaus

[alzaimar]

Zitat von skizz:

Hashen von Strings, mithilfe der Divisionsrestmethode

Muss das sein? Wieso nicht andere/bessere Hash-Funktionen? Oder ein ELF-Hash?

[skizz]

@Klaus

h(HAUS) = ( ord(H)*128³ + ord(A)*128² + ord(U)*128 + ord(S)) mod m

Irgendwie hing ich da fest, daher das power(128,x)....

// am Rande, bei dem da oben, ist h sehr wahrscheinlich größer als m, da mod m nur einmal dividiert, was zu kuriosen Ergebnissen führt...


Danke fürs umsetzten des Pseudocodes. Da wäre ich irgendwann sicherlich auch drauf gekommen...

Musste noch kleine Änderungen vornehmen:
Showmessage hilft bei der Fehleranalyse.
Probleme waren bei deiner Version, dass er das letzte Zeichen nicht mehr genommen hat, dafür das erste aber 2 mal, funktioniert nun. (Glaube ich zumindest)

Dennoch danke, denn ich war irgendwo auf dem Falschen weg

Delphi-Quellcode:

  h := ord(s[1]) mod m; // h = s[1] mod m
  //showmessage(s[1] + inttostr(ord(s[1]))); // prüfen
   for i:= 2 to laenge do                  //(h1 mod m *128 +h[i]) mod m .....
     begin
        //showmessage(s[i] + inttostr(ord(s[i])));  //prüfen
        h := (h * 128 + ord(s[i])) mod m;
    end;
   memo1.Text := inttostr(h);

@alzaimer

Die Divisionsrestmethode ist recht einfach zu verstehen und daher für einen kleinen Vortrag gerade passend. Anfangs dachte ich zwar an einen md5 hash, der für die Verschlüsselung deutlich effektiver ist, aber für einen kleinen Vortrag ist das eindeutig zu viel. (Insbesondere da hashes nur ein Teil des Themas sind...)
P.S. Die Divisionsrestmethode, sowie eine Abwandlung davon sind auch in deinem ersten Link enthalten.