Verständnisproblem zur Hashtable

[alex987]

Hi Leute.

Ich muss viele tausend Objekte unsortiert in einer Liste oder ähnlichem speichern. Für den schnellen Lesezugriff bietet sich hier die Hashtable an. Nur ein Problem. In den Javadocs steht: "Note that the hash table is open: in the case of a "hash collision", a single bucket stores multiple entries, which must be searched sequentially."
Die put-Methode gibt bei einer Kollision zwar das Objekt zurück, was vorher mit diesem Key verknüpft war. Ist das dann aber noch drin oder damit raus aus der Hashtable? Sind dann 2 Objekte mit diesem Key verknüpft? Wie durchsuche ich die dann "sequentiell"? Die get-Methode gibt doch dann nur 1 Objekt zurück. Wie käme ich an das zweite?
Ich denke, mit put legt er das neue Objekt in die Table und verknüpft sie mit dem Key. Das alte Objekt fliegt aus der Tabelle und ich muss mich selber drum kümmern, wie ich die Kollision nun behandle. Richtig?

 

[Marco13]

Ich glaub' du vermischst da zwei Sachen.

Man kann nicht 2 Objekte mit dem gleichen Key abspeichern. Wenn man sowas macht wie
table.put("Hallo", "Welt");
table.put("Hallo", "Universum");
dann wird in der zweiten Zeile das "Welt" rausgeworfen, und die table enthält nurnoch das Key-Value-Paar ("Hallo", "Universum").

Das hat aber nichts mit einer "Hash Collision" zu tun. Eine Hash-Collision liegt vor, wenn zwei Schlüssel den gleichen Hashwert haben, aber unterschiedliche Objekte beschrieben. Das ist erlaubt. Die Bedinungen sind

- Wenn zwei Objekte gleich sind, müssen sie den gleichen Hashwert haben
Aus a.equals(b) muss also a.hashCode()==b.hashCode() folgen

- Wenn zwei Objekte den gleichen hashCode haben, müssen sie nicht notwendingerweise gleich sein
Es kann sein, dass a.hashCode()==b.hashCode() gilt, aber trotzdem a.equals(b)==false ist.

Die Hashtable verwendet zum endgültigen Identifizieren die equals-Funktion. Der hashCode ist nur ein "Hinweis", wo die Daten liegen, damit man sie schneller findet.

Es kann z.B. sein, dass die Strings "Bla" und "Blubb" den gleichen hashCode haben. Wenn man dann sagt
table.put("Bla", "Welt");
table.put("Blubb", "Universum");
Dann gibt es eine "hash-Collision", aber trotzdem mann man nach wie vor mit
table.get("Bla");
table.get("Blubb");
die jeweiligen Values "Welt" und "Universum" aus der Tabelle holen.

Wenn es "viele" Hashkollisionen gibt, wird eine Hashtable eben immer langsamer (weil dann mehr gesucht und mit equals verglichen werden muss). Eine "gute" Hashfunktion zu finden (bzw. zu Implementieren) ist eine Kunst für sich...

Wenn du mehrere Objekte mit dem gleichen Key abspeichern willst, gibt es einen gängigen Workaraund: Man speichert eine Liste als Value...

 

[alex987]

Also so lange ich unterschiedliche Keys verwende, kann ich immer eindeutig auf das damit verknüpfte Objekt zugreifen!?
Die ganzen Eigenheiten der Hashtabellen: z.B. Kollision, Kollisionsbehandlung, Hashfunktion usw. passieren also innerhalb der Hashtable. Für mich unsichtbar!?
Soll heißen: Ich packe meine Objekte mit zugehörigem eineindeutigen Key(bei mir ein Integer-objekt) in die Hashtable und das ganze Thema Hash interessiert mich nicht weiter. Das macht die Tabelle selbst?

 

[Marco13]

Wenn du als Keys Integer-Objekte verwendest, dann kannst du zu jedem Integer genau ein Objekt speichern.

table.put(1, "Hallo");
table.put(2, "Welt");
table.put(3, "oder");
table.put(2, "Universum"); // Erst hier wird (2,"Welt") rausgeworfen und durch (2,"Universum") ersetzt.

Dabei können zwar hash-Kollisionen auftreten, aber die "sieht man von außen nicht", und sie "gehen den Benutzer auch nichts an".

BTW: Falls du keine Mutithreaded-Anwendung schreibst, solltest du nicht sowas machen wie
private Hashtable map = new Hashtable();
sondern
private Map map = new HashMap();

(bzw. das ganze mit Generics
private Map<Integer, WasAuchImmer> map = new HashMap<Integer, WasAuchImmer>();
falls du Java >= 1.5 verwendest)

 

[Milbo]

Ich frage immer ab, ob bereits ein wert gespeichert wurde

z.B. Object alter Wert = table.put(neuerWert, "meinKey");

kann man dann gut abfangen mit

if(alterWerts!=null){

}

Marco13, warum schlägst du eine HashMap vor? Ist es schneller? und warum nicht bei Multithreaded.
Ich habe eine Multihreaded-Anwendung und benutze das Table.

Was ich mich gefragt habe, wie das mit der Kapazität ist. Sone Hashmap ist wenn ich das richtig verstanden habe etwas größer, als es sein müßte. Ich frage mich, ob es Sinn macht bei Hashtable, welche sich nicht mehr verändern die Kapazität auf das mögliche Minimum zu begrenzen.

 

[Tobias]

Hashtable ist synchronized und deshalb marginal langsamer als die nicht-synchronisierte HashMap-Implementierung. Ansonsten sind die beiden Klassen gleichwertig. Man sollte dem Computer nicht mehr Arbeit aufhalsen als nötig und deshalb immer das richtige Werkzeug zum Anwendungszweck wählen.

mpG
Tobias

 

[Marco13]

Den Unterschiech zwischen HashTable und HashMap hat Tobias schon erklärt. Trotzdem finde ich es "schöner", nicht eine Hashtable zu verwenden, sondern eine synchronisierte HashMap
private Map map = Collections.synchronizedMap(new HashMap());
Die Hashtable wurde nachträglich in das Collections-Framework gepresst - es spricht kaum noch etwas dafür, genau diese Implementierung zu verwenden.

Ich frage mich, ob es Sinn macht bei Hashtable, welche sich nicht mehr verändern die Kapazität auf das mögliche Minimum zu begrenzen.
Ganz klar: Jein :wink: Man könnte eine
new HashMap(numElements+1, 1.0f)
erstellen, die dann die "minimale" Größe für die gegebene Zahl von Elementen hätte, aber je kleiner die HashMap (im Vergleich zur Anzahl der Enthaltenen Elemente) ist, umso höher ist die Wahrscheinlichkeit für Hash-Kollisionen. Wenn es um eine "große" Hashtable geht, könnte man den loadFactor etwas runtersetzen und einen passenden Anfangsspeicherplatz reservieren, aber im allgemeinen ist das nicht notwendig...

 

[real987]

Danke Euch. Es ist wieder also mal einfacher im Java, als ich dachte.
Habs inzwischen schon als Hashtable implementiert.

@Marco13: Wenns wirklich etwas schneller ist, mach ich noch HashMaps draus. Multithreaded wirds nich. Aber mind. 30.000 Objekte je Table. Da macht sich das sicher bemerkbar.

@Milbo: So hab ichs auch gemacht :wink:

 

[Tobias]

Den Geschwindigkeitsunterschied wird man wohl eher nicht bemerken. Ist mehr eine Frage der "Programmiererehre".

mpG
Tobias

 

[Guest]

Diese 30.000 Objekte, was für Integer-Zahlen haben die ganz konkret als Key? Sicher nicht 0 bis 29.999, oder?

 

[maki]

^^^^ LOL!