Verständnisfragen zu HashMaps und Sets

[Expendable]

Hi,

ich habe zwei kleine Fragen:

1) In einer HashMap werden Datensätze gespeichert. Dazu werden Schlüssel berechnet, über die die jeweiligen Datensätze ansprechbar sind. Meines Wissens sind, im Gegensatz zur TreeMap, bei der HashMap die Schlüssel ungeordnet abgespeichert. Wozu macht man sich dann die Mühe und generiert erst die Schlüssel, um dann anschließend beim Suchen eines Schlüssels im schlimmsten Fall einmal durch die komplette Liste der Schlüssel iterieren zu müssen?

2) Was genau ist ein Set? Wo liegt der Sinn von einem Set? Ich habe viel im Internet dazu gesucht, allerdings keine wirklichen Antworten auf meine Fragen gefunden. Es wurde nur immer wieder geschrieben, dass Sets meist eine ungeordnete Sammlung von Elementen sind. Warum nimmt man dazu nicht einfach Listen?


Bitte korrigiert mich, wenn ich irgendwo falsch liege, denn davon gehe ich stark aus


Edit: Ich habe vergessen, dass es bei Sets keine Duplikate gibt und man mit TreeMap eine Art sortierte Liste hätte. Dennoch gibt es ja auch HashMaps, dessen Funktion ich nicht ganz verstehe.

 

[turtle]

1) In einer HashMap werden Datensätze gespeichert. Dazu werden Schlüssel berechnet, über die die jeweiligen Datensätze ansprechbar sind. Meines Wissens sind, im Gegensatz zur TreeMap, bei der HashMap die Schlüssel ungeordnet abgespeichert. Wozu macht man sich dann die Mühe und generiert erst die Schlüssel, um dann anschließend beim Suchen eines Schlüssels im schlimmsten Fall einmal durch die komplette Liste der Schlüssel iterieren zu müssen?

2) Was genau ist ein Set? Wo liegt der Sinn von einem Set? Ich habe viel im Internet dazu gesucht, allerdings keine wirklichen Antworten auf meine Fragen gefunden. Es wurde nur immer wieder geschrieben, dass Sets meist eine ungeordnete Sammlung von Elementen sind. Warum nimmt man dazu nicht einfach Listen?

zu 1:
Beim Suchen wird bei einer HashMap NICHT die ganze Liste durchsucht. Es wird zu deinem Suchobjekt der Hashwert berechnet und dann in der HashMap genau dieser Wert genommen. Im besten Fall ist es das gesuchte Objekt, also nur eine Berechnung und direkter Zugriff. Nun kann es passieren, das zwei "gleiche" Objekte zum selben Hashwert berechnet werden. Dieses nennt man eine Kollision und es ist Aufgabe der Hashmap-Implementierung damit geeignet umzugehen. Wird eine ordentliche Hashfunktion genommen, verteilen sich aber Objekte sehr gleichmässig im zugrunde liegenden Speicher und es kommt selten zu Kollisionen. Daher läuft die Suche in einer HashMap häufig in linearer Zeit.

zu 2:
Eine Set ist, anders als eine Liste, eine Menge von Objekten. Daher können auch keine Duplikate enthalten sein.

 

[Expendable]

1) Hat sich erledigt.

2) Habe ich bereits geschrieben gehabt. Es stellt sich mir allerdings eine neue Frage. Bei einem TreeSet werden die Daten einfach nur sortiert. Bei einem HashSet werden jedoch auch wieder Schlüssel berechnet, genau wie bei der HashMap. Wo liegt der Unterschied?

 

[turtle]

2) Habe ich bereits geschrieben gehabt.
Ja, hatte ich übersehen

Es stellt sich mir allerdings eine neue Frage. Bei einem TreeSet werden die Daten einfach nur sortiert. Bei einem HashSet werden jedoch auch wieder Schlüssel berechnet, genau wie bei der HashMap. Wo liegt der Unterschied?

Hashing hat NICHTS mit Sortierung zu tun!
Eine Hashfunktion bildet "nur" eine grosse Eingabemenge auf eine beschränkte Zielmenge ab.

Ein HashSet implementiert das Set-Interface, verhält sich also nach aussen wie ein Set, nutzt intern aber eine HashMap zur Speicherung. Daher kann der Vorteil von Hashwerten benutzt werden, wenn man zum Beispiel wissen möchte, ob ein Objekt im Set gespeichert ist.

public boolean contains(Object o)

Ein TreeSet verwaltet die Elemente dagegen immer sortiert. Diese muss man ansonsten nachträglich umkopieren und dann sortieren.

 

[Expendable]

Heißt das, dass es eigentlich gar keinen Unterschied (abgesehen von den verschiedenen Interfaces) zwischen HashSets und HashMaps gibt?

 

[turtle]

Heißt das, dass es eigentlich gar keinen Unterschied (abgesehen von den verschiedenen Interfaces) zwischen HashSets und HashMaps gibt?

Bis auf die Interfaces?opcorn:
Na, das sind doch schon Einige, oder?
Um einige Untschiede, die in diesem Thread relevant waren, heraus zu filtern:

Set: Menge von Objekten (ohne Duplikate). Langsame Suche für ein Objekt
Map: Menge von Key zu Menge von Objekten. Extrem schneller Zugriff auf Objekt über Key.

 

[Expendable]

Wieso ist denn ein HashSet langsamer als eine HashMap, wenn das HashSet intern eine HashMap benutzt? Für mich ist das beides dann das gleiche

 

[turtle]

Weil du bei einer Map beliebige Objekte als Schlüssel nehmen kannst.

Beispiel Telefonbuch...

Du mappst also den Schlüssel (Name) "turtle" aus seine Telefonnummer "555-1234". Suchen geht schnell, indem du die Telefonnummer von "turtle" suchst.

Bei einem Hashset würde "nur" die Telefonnummer im Set, also "555-1234" gespeichert. Und du musst erstens entweder die Nummer bereits kennen, also rudimenäres Suchen, oder Testen, ob die Telefonnummer bereits gespeichert ist, oder explizites Suchen über den iterator(), ergo langsam.

 

[Expendable]

Wenn in dem HashSet nur die Telefonnummer gespeichert ist, was unterscheidet dann das HashSet von einer Liste? Wieso heißt es HashSet? Hieß es nicht mal, dass ein HashSet intern genauso arbeitet wie eine HashMap?

Ich verstehe deinen letzten Absatz leider nicht im geringsten.