Extendible Hashing - Integer --> Binär

[fkerber]

Hi!

Da das Projekt an sich in Java geschrieben ist, erspare ich euch spezielle Codes und versuche das Problem etwas abstrakter zu beschreiben.
Also, es geht um die Implementierung von Extendible Hashing.
Ich glaube, es geht schneller wenn man kurz den Wiki-Artikel liest, als wenn ich mir einen Knoten in die Finger schreibe, um es zu erklären - allerdings ist auch für das eigentliche Problem nicht ganz so wichtig, wofür man es im Endeffekt braucht.
Wichtig ist im Prinzip folgendes: Man hat x Werte, die man da einfügen möchte (in meinem Fall sind es Integer-Werte) und damit man rausbekommt, in welches Bucket man sie einfügen muss, wird ihre Darstellung als Binärzahl gebraucht. (Allerdings immer nur die letzten Stellen). Und genau da liegt das Problem:
Es ist verdammt zeitaufwendig, diese Umwandlung von Dezimal nach Binär durchzuführen. Es gibt da in Java eine fertige Methode für, ich denke, die wird wohl schon das schneller sein, als wenn ich da jetzt was von Hand frickel.
Die Sache ist ja jetzt, dass man meist Sachen berechnet, die man nicht braucht. Als Beispiel mal folgendes:

Hash: 213.338.459 --> Binär: 1100 1011 0111 0100 1001 0101 1011

Davon brauche ich vllt. die letzten 4 oder 5 Stellen - also 11011 z.B.


Langer Rede kurzer Sinn:
Kennt jemand eine Möglichkeit, wie ich an diese Zahlen kommen könnte, ohne so viel Aufwand zu haben?
Insbesondere ist es wichtig, dass es die letzten Stellen der Binärdarstellung sein müssen, damit man schrittweise Stellen davor machen kann, wenn das Hashing es erfordert.

Ich denke, die Alternative, dass man die ersten Stellen nimmt und diese reversiert ist keine wirkliche, da das Reversieren ja auch kostet...


Grüße, Frederic

[himitsu]

in Delphi ... k.A. wie das in Java aussieht

i and 1 = letzte Stelle
(i shr 1) and 1 = vorletzte Stelle
i and 3 = letzten zwei Stellen

ich denke mal nicht, daß es nötig ist das auch noch in Strings umzuwandeln
(abgesehn davom, daß eine Suche im Baum mit Strings nicht grad optimal ablaufen dürfte)

[fkerber]

Hi!

Das klingt interessant.
Geht es da auch irgendwie weiter?

Also wenn ich auf einen Schlag die letzten 5 Stellen brauche?


Edit:
Welche Suche im Baum meinst du?
Es gibt da keinen Baum und der Binärstring wird auch nochmal in einen int umgewandelt :mrgreen:


Edit2:
Gefunden: i and 31 liefert die letzten 5 Stellen - System erkannt.

Grüße, Frederic

[himitsu]

Zitat:

Zitat von fkerber

Welche Suche im Baum meinst du?

Es gibt da keinen Baum und der Binärstring wird auch nochmal in einen int umgewandelt :mrgreen:

na den Baum?

Zitat:

and uses a trie for bucket lookup

Zitat:

Zitat von fkerber

Das klingt interessant.
Geht es da auch irgendwie weiter?

Zitat:

Zitat von fkerber

Edit2:
Gefunden: i and 31 liefert die letzten 5 Stellen - System erkannt.

genau :thumb:
31 = binär ...00000000011111 und gibt per AND nur diese Stellen/Bits zurück

[fkerber]

Hi!

Ah, ok.
Es gibt bei unserer Implementierung keinen Baum.
Wir haben ein Array, in dem die Buckets drin sind. Daher wurde auch der Binärstring wieder in nen int verwandelt, der dann als index für den Arrayzugriff diente.

Habe das jetzt umgebaut und einen deutlichen Speedup verzeichnen können.


Vielen Dank!


Grüße, Frederic