PDA

Archiv verlassen und diese Seite im Standarddesign anzeigen : Javascript hash Funktion



wirehack7
01.03.2015, 19:27:42
Folgende Problemstellung:


function hash (s)
{
var h = 7;
var letters = "acdegilmnoprstuw";
for(i = 0; i < s.length; i++) {
h = (h * 37 + letters.indexOf(s[i]));
}
return h
}

document.write(hash('leepadg'));

document.write('<br>');


function rev_hash(s) {
var letters = "acdegilmnoprstuw";
x = 0;
while(s > 7.5) {
s = s / 37;
x++;
}

return x;
}

Die Funktion hash(); ist vorgegeben, sie wandelt eine Zeichenkette in eine Zahl um, dabei dürfen nur jene Zeichen benutzt werden welche in der Variable letters stehen.
Beim ersten durchlauf nimmt sie


7*37+(Stelle des ersten Zeichens des Strings in letters)

Danach nimmt sie:

(letztes Ergebnis)*37+(Stelle des ersten Zeichens des Strings in letters)

Bitte beachten, das Zählen fängt bei 0 an, nicht 1. Also wenn es beim Zählen ab 1 die 6te Stelle wäre ist es die 5te.

Und das so oft wie es Zeichen im gegebenen String gibt.

Nun möchte ich das ganze umdrehen, ich gebe also einen Zahlenwert und bekomme dadurch den String. Ich habe hier aber nun irgendwie eine Denkblockade.

rev_hash gibt bisher zurück wie viele Zeichen das Ergebnis haben muss. Was kann ich aber nun mit der Information machen?

Billkiller
01.03.2015, 22:30:06
Ich würde rev_hash anders implementieren. In der Form, in der sie jetzt ist, kann sie dir nur die Anzahl der Zeichen zurückgeben.

Mein Ansatz: Ziehe vom Hash solange die Zahl 1 ab, bis der Wert restlos durch 37 teilbar geworden ist. Jedes mal, wenn du 1 abziehst erhöhst du einen Zähler um 1 (von 0 beginnend). Sobald die bearbeitete Variable restlos durch 37 teilbar ist, beinhaltet deine Zählvariable den Index des Buchstabens. Nun muss die Zahl durch 37 geteilt werden. Das Ergebnis setzt du nun entweder rekursiv wieder in deine rev hash Funktion ein oder du lässt eine äußere Schleife laufen, bis der eingegebene Hash <= 7 ist.

Aus meiner Sicht sollte das so hinhauen :)

wirehack7
01.03.2015, 23:23:23
Ich würde rev_hash anders implementieren. In der Form, in der sie jetzt ist, kann sie dir nur die Anzahl der Zeichen zurückgeben.

Mein Ansatz: Ziehe vom Hash solange die Zahl 1 ab, bis der Wert restlos durch 37 teilbar geworden ist. Jedes mal, wenn du 1 abziehst erhöhst du einen Zähler um 1 (von 0 beginnend). Sobald die bearbeitete Variable restlos durch 37 teilbar ist, beinhaltet deine Zählvariable den Index des Buchstabens. Nun muss die Zahl durch 37 geteilt werden. Das Ergebnis setzt du nun entweder rekursiv wieder in deine rev hash Funktion ein oder du lässt eine äußere Schleife laufen, bis der eingegebene Hash <= 7 ist.

Aus meiner Sicht sollte das so hinhauen :)

Das weiß ich sogar auch dass die Funktion das nur kann :) Wie gesagt, bisher zeigt sie nur die Anzahl der Zeichen.

Jop, Modulus macht Sinn, mal morgen damit rumspielen. Danke!

Billkiller
01.03.2015, 23:53:05
Habe gerade noch mal etwas rumgegrübelt und da ist mir aufgefallen, dass die jetzige rev hash Funktion wohl auch nicht ganz zuverlässig die Anzahl der Zeichen ausgibt. Beim Wort "www" sollte nach dem hashen und "rückwärts hashen" die Länge 4 ausgegeben werden, was ja nicht stimmt :)

eMo
02.03.2015, 01:44:13
Der Modulo Operator ist hier, denke ich, tatsächlich die Lösung.
Leider bin ich mit JavaScript nicht so bewandert, daher eher Pseudocodig:


function rev_hash(s){
var letters = "acdegilmnoprstuw";
var sol = "";
while(s!=7) {
if(s%37==0)
sol += "_";
else
sol += letters.get(s % 37); // wie in list.get() oder array[]
s = (s - s%37)/37;
}

return sol;
}

Ich sehe das Problem jedoch eher in der Tatsache, dass das Ergebnis durch die Unvollständigkeit von letters zu Problemen führen wird. Habe das in der Rückfunktion jetzt über "_" gelöst. Ist halt problematisch, da man die letzten Ziffern nur raten kann, macht jedoch auch nichts, weil es gleichzeitig bedeutet, dass die Buchstaben, die nicht in letters enthalten sind, irrelevant sind. Und selbst wenn man mehr als ein Hash hätte, könnte man die verbleibenden Stellen mit Sicherheit deutlich schneller brute forcen als den kompletten Ausdruck :D

Billkiller
02.03.2015, 10:35:54
War wohl etwas spät für mich gestern Abend. Das von mir angesprochene Verfahren entspricht natürlich der Operation mit dem Modulo-Operator :D

Wenn ich das hier richtig interpretiert habe:



Bitte beachten, das Zählen fängt bei 0 an, nicht 1. Also wenn es beim Zählen ab 1 die 6te Stelle wäre ist es die 5te.



Dann braucht man den Sonderfall s%37==0 gar nicht betrachten, da die aufaddierte 0 einfach dem ersten Buchstaben der Variable letters entspricht (hier also 'a').
Nicht bekannte Zeichen sollte man eigentlich nur bekommen, falls s%37 größer als die Länge von letters -1 ist.

eMo
02.03.2015, 11:40:30
War wohl etwas spät für mich gestern Abend. Das von mir angesprochene Verfahren entspricht natürlich der Operation mit dem Modulo-Operator :D

Wenn ich das hier richtig interpretiert habe:



Dann braucht man den Sonderfall s%37==0 gar nicht betrachten, da die aufaddierte 0 einfach dem ersten Buchstaben der Variable letters entspricht (hier also 'a').
Nicht bekannte Zeichen sollte man eigentlich nur bekommen, falls s%37 größer als die Länge von letters -1 ist.

Stimmt, da hast du recht, war doch etwas spät gestern :ugly:

Nilo
02.03.2015, 20:42:41
Modulo is the way to go!
Ein Problem könnte aber hier ziemlich leicht auftreten, wenn ich das richtig sehe: Kollision.
Wenn ein Wort die gleiche Länge und die gleichen Buchstaben hat, ergibt sich bei deiner Hashing-Funktion der gleiche Hashwert.
Kann auch sein, dass ich es nicht ganz geblickt haben, ich probiers mal aus...

eMo
02.03.2015, 22:03:32
Modulo is the way to go!
Ein Problem könnte aber hier ziemlich leicht auftreten, wenn ich das richtig sehe: Kollision.
Wenn ein Wort die gleiche Länge und die gleichen Buchstaben hat, ergibt sich bei deiner Hashing-Funktion der gleiche Hashwert.
Kann auch sein, dass ich es nicht ganz geblickt haben, ich probiers mal aus...

Bist du dir sicher, dass:
(a*37+b)*37 das selbe ist wie (b*37+a)*37
Halte ich für unwahrscheinlich.
Problem ist eher, wenn ein Wort bis auf Wörter außerhalb der letter gleich ist.

Sonst müsste mein Algorithmus halbwegs sinnvoll sein, wenn man die if-Bedingung weglässt.
Interessant ist eher, was indexOf zurück gibt, sollte ein Symbol nicht gefunden werden.

BaShoR
02.03.2015, 22:17:28
Da ja was dazuaddiert wird vor dem weiteren Multiplizieren, sollte da solange der addierte Wert < 37 ist nie dasselbe rauskommen. Deswegen nimmt man dafür ja große Primzahlen.
Korrigiert mich wenn ich mich irre, aber tendenziell sollte jeder String einen einzigartigen Zahlenwert ausspucken.

eMo
02.03.2015, 23:05:05
Nein, du irrst 'aazcde' und 'aabcde' hätten den selben Hashwert, da weder b noch z in letters enthalten sind.

Nilo
03.03.2015, 13:58:38
Nein, du irrst 'aazcde' und 'aabcde' hätten den selben Hashwert, da weder b noch z in letters enthalten sind.

Jo, hab mich anfangs geirrt. Du hast recht, bei solchen Strings treten die selben Hashwerte aber auf :>