Hash-Funktion und assoz. Array

[student]

Hallo,

ich bin Student und arbeite mich in das Thema Hashing und Hashfunktionen ein. Jetzt wollte ich das mal ein bisschen ausprobieren und habe folgendes versucht:

Es sollen die Zahlen von 0 bis 10 mit der Funktion h(k) = k mod 11 gehasht werden.

function h(k, N) {
 return k%N;
}

var hashTable = new Array();
document.write("k ---- h(k)");
for (var i = 0;i<11;i++) {
 document.write((i*i) + " ---- "+h((i*i),11));
 hashWert = h((i*i),11);
 if (typeof hashTable[hashWert] != "undefined") hashTable[hashWert]=hashTable[hashWert]+1;
 else hashTable[hashWert]=0;
}

document.write("<br>");

for (i in hashTable) {
 document.write("hashTable["+i+"]="+hashTable[String(i)]);
}

Irgendwie funktioniert das aber nicht so wie es soll. Kann mir jemand den Fehler zeigen und eventuell korrigieren?

[Griever]

document.write("k ---- h(k)");

Ich weiß nicht, ob das gewollt war oder nicht:

document.write("k ---- " + h(k));

Außerdem fehlt der 2. Übergabewert "N".

[student]

document.write("k ---- h(k)");

Ist die Tabellen überschrift.

Das Problem ist, dass die Tabelle nicht funktioniert. Ich kann nicht auf  die Element so zugreifen wie ich es möchte. Es geht nur mit

var hashTable = new Array(0,0,0,0,0,0,0,0,0,0,0);

als Inialwert. Aber dann habe ich ja kein ass. Array mehr.

[Griever]

Ein Assoziatives Array ließe sich auch nur leicht mit einer assosziativer Schleife machen.

Vielleicht versuchtst du es mal.

[student]

Ein Assoziatives Array ließe sich auch nur leicht mit einer assosziativer Schleife machen.

Vielleicht versuchtst du es mal.

Kann ich leider nicht, weil ich nicht verstehe, was du jetzt genau meinst.

Was ich haben wollte, war dies hier:

k ---- h(k)
0 ---- 0
1 ---- 1
4 ---- 4
9 ---- 9
16 ---- 5
25 ---- 3
36 ---- 3
49 ---- 5
64 ---- 9
81 ---- 4
100 ---- 1

hashTable[0]=1
hashTable[1]=2
hashTable[3]=2
hashTable[4]=2
hashTable[5]=2
hashTable[9]=2

Klappt halt nicht. Und in der zweiten Schleife habe ich doch for(i in hashTable) genommen.

[Struppi]

Es sollen die Zahlen von 0 bis 10 mit der Funktion h(k) = k mod 11 gehasht werden.

In JS gibt es keine assoziativen Arrays oder Hashs, du nutzt einfach die Eigenschaft in JS aus, dass du jedem x-beliebigen Objekt um ein x-beliebiges Attribut erweitern kannst. Das ist zwar zumindest im Ansatz ein ähnliches verhalten, du hast aber ausser dass du mit einer for in Schleife darauf zugreifen (wie bei allen Objekten) kannst keinerlei Kontrollmöglichkeiten (wie in anderen Sprachen, die entsprechende Objekte kennen)

function h(k, N) {
return k%N;
}

var hashTable = new Array();

D.h. hier kannst du getrost var hashTable = new Object(); schreiben

Irgendwie funktioniert das aber nicht so wie es soll. Kann mir jemand den Fehler zeigen und eventuell korrigieren?

"Irgendwie funktioniert es nicht" ist keine Fehlerbeschreibung mit der jemand etwas anfangen kann. Was ist es? Und was ist der Fehler?

Struppi.

[Siechfred]

Hell-O!

Es sollen die Zahlen von 0 bis 10 mit der Funktion h(k) = k mod 11 gehasht werden.

Die Ergebnisse sollen die Schlüssel werden, und du willst zählen, wie oft ein Ergebnis vorkommt?

Irgendwie funktioniert das aber nicht so wie es soll. Kann mir jemand den Fehler zeigen und eventuell korrigieren?

Der Fehler liegt nicht im Javascript, sondern in deiner Logik. Wenn das Script im else-Zweig landet, dann gibt es den Schlüssel noch nicht, gleichwohl handelt es sich um das *erste* Vorkommen von hashWert. Konsequenterweise musst du dann auch die Eigenschaft mit 1 initialisieren, nicht mit 0.

Siechfred

[student]

Der Fehler liegt nicht im Javascript, sondern in deiner Logik. Wenn das Script im else-Zweig landet, dann gibt es den Schlüssel noch nicht, gleichwohl handelt es sich um das *erste* Vorkommen von hashWert. Konsequenterweise musst du dann auch die Eigenschaft mit 1 initialisieren, nicht mit 0.

Vielen Dank. Ich glaube, ich hätte vorher erstmal ein bisschen schlafen sollen. 4,5 Stunden sind wohl zum Lernen und klar denken einfach zu wenig.