Praktikum5: mid square

[pect]

mid square - The decimal representation of the key is interpreted as
a natural number and multiplied by itself. From the middle of the
result of this multiplication some digits (number of digits is equal to
the length of an address in the Hash-Table) are used as the address in
the Hash-Table. You should start from the 10-th digit from the right.
For example if the multiplication delivers 7766279611452241921 and
the length of an address is 3 then you should use 611 as the address
to store the corresponding entry if the capacity of the Hash-Table
exceeds 611

Was macht man denn bei MidSquare, wenn garkein Index passt? Nehmen wir als Beispiel den
Eintrag "Z8IG4LDXS" mit seiner Ascii-Repräsentation der ersten 5 Stellen dargestellt als 9056737152.
Multipliziert mit sich selbst ergibt das 82024487840417071104 (wo kommt die Zahl 7766.. aus der Beschreibung her?!),
von welcher Zahl ich widerrum die ersten zehn Stellen nehmen soll: 8202448784.

Jetzt soll man von rechts nach links gehend den Index suchen. Wenn man beispielsweise 10.000 Einträge hat,
kann man weder die Zahl 48784 noch 82024 zum hashen nutzen.

Wie soll man dann weiter vorgehen? 0 zurückgeben? Abbrechen?

[Krümelmonster]

Die Zahl in dem Beispiel hat nichts mit der ASCII-Darstellung zu tun.
Es ist einfach eine beliebige Zahl.

Important Comments.txt

1) Bei allen Methoden zum Hashen muss ein mod m erfolgen, d.h. auch fuer
folding und mid_square.

[strauß]

Das versteh ich nicht ganz.
Also wenn ich jetzt bei folding 25 raus habe, soll ich noch ein modulo auf die HashTabellengröße machen?
Dann wäre meine Frage geklärt, was passiert wenn ich 25 raus habe die Hash-Tabellengröße aber nur 22 ist.

[Krümelmonster]

Genau deshalb muss noch der modulo-Operator angewendet werden.

Damit sichergestellt ist, dass das Ergebnis eine Adresse des Arrays ist.

[s!mon]

Wie quadriere ich denn long-Zahlen? Bei mir kommt bei

long dezimal = dezimal(key);
dezimal = dezimal * dezimal;

Wenn ich 9056737152 quadriere komme ich damit auf 8237511545578864640. Die richtige Lösung ist aber wie oben ja steht 82024487840417071104. Dadurch fallen bei mir halt 2 Testfälle durch..

[Krümelmonster]

Ein Blick in die Important Comments.txt hilft:

3) Fur die mid_square Kollisionsbehandlugsmethode hann man ein BigInteger benutzen.

[Mspringer]

3) For the mid_square collision resolution method, you can use BigInteger.

Steht in den Important nodes. Gibt dafür ne Klasse in Math, aber egal wa sich in den Konstruktor schreibe beim instanzieren, der nimmt es nicht an... Oder meinen die Veranstallter hier was anderes?

[s!mon]

Thx

über mir:

BigInteger dezimal = BigInteger.valueOf(dezimal(key));
dezimal = dezimal.pow(2);

So funktionierts bei mir

[Edoat]

Bei Unklarheiten zur Verwendung von irgendwelchen Klassen oder Methoden bietet es sich an, in die Doku zu schauen:

http://java.sun.com/reference/api/

[Mspringer]

Danke für den Tipp Edoat, war mir bekannt, aber z.b. der Konstruktor mit long (nur als Beispiel) gab bei mir den Fehler : Constructor not visible.

Und danke @ Simon, funst dann