nicht angemeldet
Hash Problem
Hallo,
ich habe Zeichnketten in eine Hashtable eingelesen - funktioniert auch.
Nun lasse ich mir den Inhalt mit
Enumeration enum = h.elements();
liefern und gehe die Elemente mit einer while-Schleife durch. Das funktioniert auch.
Aber: warum bekomme ich die Zeichenketten in einer anderen Reihenfolge, als ich sie eingelesen habe? Ich habe keine Sortierroutine angewendet - warum also sortiert Java die Elemente um? Wie verhindere ich das?
Vielen Dank, Kay
-
hallo,
in einem has werden die daten nicht in der reihenfolge abgespeichert, in der du die daten eingegeben hast, sondern so, wie es verwaltungstechnisch am günstigsten ist. wirklich umgehen kannst das nicht. aber du könntest eine Klasse definieren, die ein schlüssel-, sowie ein wert-objekt speichert, und instanzen dieser klassen in einem Vector unterbringen.
mit freundlichen grüßen
dimitri rettig -
Hallo Kay,
Aber: warum bekomme ich die Zeichenketten in einer anderen
Reihenfolge, als ich sie eingelesen habe? Ich habe keine
Sortierroutine angewendet - warum also sortiert Java die Elemente
um?Java sortiert die Reihenfolge der Elemente gar nicht. Die ergibt sich
aus der Hash-Summe. Eine Hash-Table arbeitet ungefähr so: aus dem
Key-String wird eine Zahl (im Normalfall unsigned 32 Bit gross)
erstellt. Diese Summe wird gekürzt (z. B. auf 16 Bit) und gibt damit
eine Index-Zahl für einen Array, der halt 2^x Elemente groß ist, wobei
x die Größe der Zahl bezeichnet (in diesem Fall also 16, weil die Zahl
auf 16 Bit gekürzt wurde). Da wir allerdings einen begrenzten
Abbildungsraum haben, sind Dupletten (zwei Keys, die dieselbe
Hash-Summe ergeben) unvermeidlich. Treten zu viele Dupletten auf, so
wird die Hash-Tabelle vergrößert (z. B. auf 32 Bit). Im Zuge der
Vergrößerung muss jedes Element neu einsortiert werden; das kostet
natürlich Zeit, jedoch ist der Nutzen daraus größer als der Aufwand.Ich hoffe, du verstehst jetzt, warum eine Hash-Tabelle nicht sortiert
ist, und dass du...Wie verhindere ich das?
... das nicht verhindern kannst.
Grüße,
CK--
Der Verstand steht ueber allem. Was durch die Vorstellungskraft nicht geschaffen werden kann, existiert nicht.-
Tag nochmal,
[...] Da wir allerdings einen begrenzten Abbildungsraum haben,
sind Dupletten (zwei Keys, die dieselbe Hash-Summe ergeben)
unvermeidlich.Nochmal genauer: wir haben einen begrenzten Abbildungsraum bei einer
unbegrenzten Eingabemenge.Grüße,
CK--
Der Verstand steht ueber allem. Was durch die Vorstellungskraft nicht geschaffen werden kann, existiert nicht. -
hallo christian,
kannst du einen link angeben, wo man solcherlei sachen nachlesen kann?
mit freundlichen grüßen
dimitri rettig-
Hallo Dimitri,
kannst du einen link angeben, wo man solcherlei sachen nachlesen kann?
Eine generelle Adresse gibt es für sowas wohl nicht, denke ich. Aber
Google hilft aus: mit den Stichworten 'Algorithmen Datenstrukturen
Hash-Tabelle' habe ich recht gute Ergebnisse erhalten. Hochschul-Seiten
würde ich tendentiell bevorzugen, am liebsten wären mir Scripte oder
Mitschriften von Vorlesungen :) Aber das ist natürlich reine
Geschmacksache.Grüße,
CK--
Nur die Weisesten und die Dümmsten können sich nicht ändern.
-
-