Praktikum5: mid square

pect
Erstie
Erstie
Beiträge: 20
Registriert: 9. Apr 2008 21:47

Praktikum5: mid square

Beitrag von 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?

Benutzeravatar
Krümelmonster
Geek
Geek
Beiträge: 767
Registriert: 17. Okt 2007 13:58
Wohnort: Jossgrund

Re: Praktikum5: mid square

Beitrag von 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.
Stell deinen Fuß auf einen hohen Sockel
Mach dir ein Haar aus tausend Locken
Du bleibst doch immer, was du bist!

strauß
Windoof-User
Windoof-User
Beiträge: 27
Registriert: 5. Mai 2007 10:41

Re: Praktikum5: mid square

Beitrag von 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.

Benutzeravatar
Krümelmonster
Geek
Geek
Beiträge: 767
Registriert: 17. Okt 2007 13:58
Wohnort: Jossgrund

Re: Praktikum5: mid square

Beitrag von Krümelmonster »

Genau deshalb muss noch der modulo-Operator angewendet werden.

Damit sichergestellt ist, dass das Ergebnis eine Adresse des Arrays ist.
Stell deinen Fuß auf einen hohen Sockel
Mach dir ein Haar aus tausend Locken
Du bleibst doch immer, was du bist!

Benutzeravatar
s!mon
Computerversteher
Computerversteher
Beiträge: 373
Registriert: 20. Okt 2007 18:24
Wohnort: Höchst i. Odw

Re: Praktikum5: mid square

Beitrag von 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..

Benutzeravatar
Krümelmonster
Geek
Geek
Beiträge: 767
Registriert: 17. Okt 2007 13:58
Wohnort: Jossgrund

Re: Praktikum5: mid square

Beitrag von Krümelmonster »

Ein Blick in die Important Comments.txt hilft:
3) Fur die mid_square Kollisionsbehandlugsmethode hann man ein BigInteger benutzen.
Stell deinen Fuß auf einen hohen Sockel
Mach dir ein Haar aus tausend Locken
Du bleibst doch immer, was du bist!

Mspringer
Nerd
Nerd
Beiträge: 555
Registriert: 19. Okt 2006 14:41
Wohnort: Darmstadt / Alzenau
Kontaktdaten:

Re: Praktikum5: mid square

Beitrag von 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?

Benutzeravatar
s!mon
Computerversteher
Computerversteher
Beiträge: 373
Registriert: 20. Okt 2007 18:24
Wohnort: Höchst i. Odw

Re: Praktikum5: mid square

Beitrag von s!mon »

Thx

über mir:

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

So funktionierts bei mir

Edoat
Sonntagsinformatiker
Sonntagsinformatiker
Beiträge: 242
Registriert: 26. Feb 2007 15:10

Re: Praktikum5: mid square

Beitrag von 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
Nerd
Nerd
Beiträge: 555
Registriert: 19. Okt 2006 14:41
Wohnort: Darmstadt / Alzenau
Kontaktdaten:

Re: Praktikum5: mid square

Beitrag von 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 ;)

Antworten

Zurück zu „Archiv“