Discussion:
Was ist schneller? HashMap vs. HashTable vs. Baumstruktur
(zu alt für eine Antwort)
Sirke Pippig
2003-12-08 17:19:12 UTC
Permalink
Hallo

ich bin auf der Suche nach einer sehr schnellen Datenstruktur.
Der Datenstruktur muss man einen Schlüssel in Form eines Strings oder
einer Liste von Strings geben können.
Für den Wert muss ein Objekt möglich sein.
Die Sortierung spielt keine Rolle.

Jetzt mein Problem. Der Schlüssel kann sehr gross sein. Ich schätze
bis zu 1000 Zeichen lang. Verwaltet werden ca. 15.000 Einträge

Ich überlege ob ich eine HashMap oder ein HashTable nehmen soll oder
mir selber eine Datenstruktur schreiben sollte.

Aufbau des Schlüssels:
Der Schlüssel hat eine Komplexe Struktur, welche man nutzen könnte um
mehrere Hashmaps in einander zu schachteln
Der Schlüssel setzt sich auch aus einzelnen Schlüsseln und Werten
zumsammen.
Bsp:
key1=asdf
key2=ghjk
key3=löä#
key3=345
key4=qwer
Alles zusammen ergibt dann meinen grossen Schlüssel anhand ich dann
meine Werte in die Datenstruktur speichern und aus ihr auslesen will.
Ich kenne aber weder die Schlüssel noch die Werte.
Die Schlüssel können unter Umständen doppelt vorkommen. In dem Fall
spielt die Reihnfolge eine Rolle. Bei Einträgen bei denen der
Schlüssel nur einmal vor kommt ist die Reihfolge uninteresannt.


Kann mir jemand ein paar Tips geben?
Es muss nicht die Lösung meines Problems sein, aber vielleicht kennt
jemand eine sehr schnell Datenstruktur oder hat eine Idee.

Vielen Dank

Sirke
Remo Hartwig
2003-12-08 18:16:42 UTC
Permalink
Vielleicht hilft folgendes.

http://www.geocities.com/herong_yang/jdk/collection.html

Die Performance der einzelnen Collections sind ganz gut sichtbar.

Gruesse
remo
Wanja Gayk
2003-12-08 18:22:34 UTC
Permalink
Sirke Pippig said...
Post by Sirke Pippig
ich bin auf der Suche nach einer sehr schnellen Datenstruktur.
Der Datenstruktur muss man einen Schlüssel in Form eines Strings oder
einer Liste von Strings geben können.
Für den Wert muss ein Objekt möglich sein.
Die Sortierung spielt keine Rolle.
[..]
Post by Sirke Pippig
Kann mir jemand ein paar Tips geben?
Es muss nicht die Lösung meines Problems sein, aber vielleicht kennt
jemand eine sehr schnell Datenstruktur oder hat eine Idee.
Mach dir Gedanken, welche Operationen du häufig brauchst.
Wenn du oft quer über den ganzen Datenraum einfügen, suchen und
entfernen musst, ist ne HashMap Top Notch.
Wenn du aber öfter alles ausliest, ist ne Hashtable nicht ganz zu super,
weil du da idR auch die leeren Einträge ablaufen musst.

Bäume machen IMHO mehr für geordnete Datensätze Sinn. Denn ohne eine
irgendwie geartete Ordnung, bringt dir Suchen im Baum nix. Besonders bei
extrem großen Datensätzen kannst du mit nem Baum gut arbeiten, weil du
ganze Arme auslagern kannst. Dafür geht entfernen, sortieren und
einfügen mit nem Baum immer in vertretbarer Zeit. Ordnung spielt aber
bei dir keine Rolle. Von daherwürd ich fast zur HashMap neigen, wenn du
nicht all zu viel Speicher opfern musst.

Gruss,
-Wanja-
--
At a funeral, the Real Programmer is the one saying "Poor George. And he
almost had the sort routine working before the coronary."
[http://www.pbm.com/~lindahl/real.programmers.html]
Stefan Matthias Aust
2003-12-08 19:12:14 UTC
Permalink
Post by Sirke Pippig
ich bin auf der Suche nach einer sehr schnellen Datenstruktur.
Der Datenstruktur muss man einen Schlüssel in Form eines Strings oder
einer Liste von Strings geben können.
Für den Wert muss ein Objekt möglich sein.
Die Sortierung spielt keine Rolle.
Jetzt mein Problem. Der Schlüssel kann sehr gross sein. Ich schätze
bis zu 1000 Zeichen lang. Verwaltet werden ca. 15.000 Einträge
Ich überlege ob ich eine HashMap oder ein HashTable nehmen soll oder
mir selber eine Datenstruktur schreiben sollte.
Irrelevant. Um einen Datensatz zu finden, musst du Schlüssel
vergleichen. Wenn das Schnell sein soll, musst du möglichst wenig
Schlüssel möglichst schnell vergleichen.

Beide Datenstrukturen haben einen Aufwand von k*O(1) mit einem "k" das
relevant sein kann. Ob nun synchronisiert oder nicht, ein Unterschied
der meist überschätzt wird.

Idealerweise kannst du jedem Schlüsselobjekt einen Wert zuordnen, indem
ein Schlüsselobjekt einfach das Datenobjekt enthält. Sobald du den
Schlüssel hast, hast du auch den Wert. Schneller geht es nicht! (So
was gibt es, Symbole eines klassischen Lisp-Interpreters bilden auf
diese Weise auf die entsprechend benannten globalen Funktionen ab)

Nur, kannst du einzigartige Schlüsselobjekte garantieren? Das ist u.U.
schwierig. Eine Liste von Strings ist natürlich äquivalent zu einen
längeren String mit passenden Trennzeichen. Beim Erzeugen der Schlüssel
musst du zusehen, dass immer wieder das selbe (nicht nur ein gleiches)
Objekt zurückgegeben wird.

Derartige einzigartigen Schlüsselobjekte eignen sich dann auch sehr gut
als Schlüssel in einer IdentityHashMap. Nächstschnellere Variante.
Kann allerdings zum Problem werden, wenn die Anzahl der Objekte größer
ist als die Streuungbreite der System-Hashfunktion oder diese keine gut
gestreuten Werte liefert. Ersteres kann bei klassischen
Smalltalk-System passieren, die nur einen 12-bit-Hashcode hatten.
Letzteres, wenn als System-Hashcode eine fortlaufende Zahl, etwa eine
Speicheradresse benutzt wird (bei üblichen Java-VMs ist wohl beides
nicht der Fall)


bye
--
Stefan Matthias Aust // "Ist es normal, nur weil alle es tun?" -F4
Jochen Theodorou
2003-12-08 21:28:07 UTC
Permalink
Post by Sirke Pippig
Hallo
ich bin auf der Suche nach einer sehr schnellen Datenstruktur.
Der Datenstruktur muss man einen Schlüssel in Form eines Strings oder
einer Liste von Strings geben können.
Für den Wert muss ein Objekt möglich sein.
Die Sortierung spielt keine Rolle.
Jetzt mein Problem. Der Schlüssel kann sehr gross sein. Ich schätze
bis zu 1000 Zeichen lang. Verwaltet werden ca. 15.000 Einträge
[...]

darf man mehr über das Problem erfahren, vielleicht fällt uns ja was
besseres ein. Denn die Art und Weise, wie etwas gespeichert wird
schränkt die Möglichkeiten bei der Wahl der Strukturen doch sehr ein.
Also woher der Key kommt zum Bespiel, was der Wert zu diesem Key ist usw.

Gruss theo
Carl Rosenberger
2003-12-08 22:11:25 UTC
Permalink
Post by Sirke Pippig
ich bin auf der Suche nach einer sehr schnellen Datenstruktur.
Wie schon vor mir erwähnt:

Diese Information ist für einen guten Tipp etwas ungenau.
Wofür soll die Struktur schnell sein?

Geht es nur um das Suchen oder werden auch Daten hinzugefügt
oder entfernt? Muss es vielleicht möglich sein, alle Werte
als Liste auszugeben?
Post by Sirke Pippig
Der Schlüssel hat eine Komplexe Struktur, welche man nutzen könnte um
mehrere Hashmaps in einander zu schachteln
Das ist ziemlich sicher keine besonders schnelle Lösung.
Stattdessen macht es mehr Sinn, an einer eigenen Methode
zu feilen, um den Hashcode zu berechnen.

Wenn es nur darum geht, auf einen Schlüssel hin einen
Wert zu finden, ist eine HashMap nicht zu schlagen.

Idealerweise berechnet sich aus dem Hashwert direkt eine
Position im Speicher, (in Java also ein Element eines Arrays)
an dem bei einem perfekten Hash-Algorithmus nur ein Wert
stehen sollte.

Wenn Du die Daten schon im Vorhinein zur Verfügung hast,
sollte es einfach sein, mit der Implementierung des
Hash-Codes zu spielen:
- Wieviele der Schlüssel verwendest Du für die Berechnung?
- Wieviele Zeichen jedes Schlüssels verwendest Du für
die Berechnung?
- Vielleicht ist die Länge der Schlüssel eine super
Information, die sich mit einbauen lässt.
- Was machst Du aus den Schlüsseln, um letztendlich einen
Int Wert zu generieren, der möglichst eindeutig ist?

Wenn Du partout die Daten vorher nicht bekommst, kannst Du
vielleicht eine selbstlernende Implementation schreiben:
Wenn die Daten dann da sind, werden verschiedene Ansätze
zur Berechnung des Hashwertes durchgetestet. Desto weniger
gleiche Hashwerte die Berechnung erzeugt, desto besser ist
sie. Die bestmögliche Berechnung wird dann schlussendlich
vom System automatisch verwendet.

Viele Grüße,
Carl
Carl Rosenberger
2003-12-09 12:04:25 UTC
Permalink
Post by Carl Rosenberger
Wenn Du partout die Daten vorher nicht bekommst, kannst Du
Wenn die Daten dann da sind, werden verschiedene Ansätze
zur Berechnung des Hashwertes durchgetestet. Desto weniger
gleiche Hashwerte die Berechnung erzeugt, desto besser ist
sie. Die bestmögliche Berechnung wird dann schlussendlich
vom System automatisch verwendet.
Wie es der Zufall will, habe ich gestern abend genau zu diesem
Thema noch etwas in einem Buch gelesen, in dem ich gerade nach
Ideen suche [1].

Grundsätzlich suchst Du nach einer "perfect hash function" (PHF).
Sofern der Speicherplatz der notwendigen Hash-Elemente auf das
Optimum minimiert werden soll, spricht man auch von einer "minimal
perfect hash function (MPHF)".

Mit diesen Akronymen würde ich Google bemühen
http://www.google.com/search?q=PHF+Hash
http://www.google.com/search?q=MPHF+Hash
oder mal bei CiteSeer nachsehen
Post by Carl Rosenberger
http://citeseer.nj.nec.com/cs?qb=dbnum%3D1%2Cqtype%3Ddocument:&q=phf%20and%20hash
Viele Grüße,
Carl

[1] "Managing Gigabytes" von Witten, Moffat, Bell
Sirke Pippig
2003-12-12 10:29:53 UTC
Permalink
Hallo

Danke an alle die mir geantwortet haben.
Ich habe mich für das erste für eine HashMap entschieden. Es ist aber
kein Problem diese noch zu ändern, wenn es eine bessere Lösung gibt.
Post by Jochen Theodorou
Also woher der Key kommt zum Bespiel, was der Wert zu diesem Key ist
usw.
Es ist ein Mischung aus URL-Parametern und Werten die in der Session
stehen.
Die URL-Parameter liegen mir immer als String vor und die Werte aus
der Session sind verschiedene Datentypen Boolean, Integer aber
hauptsächlich Strings.


Danke an alle

Sirke

Lesen Sie weiter auf narkive:
Loading...