Verständnisfrage zur Java HashMap

Bei Postings zu Vorlesungsthema X lassen Sie Ihr Betreff bitte mit "X: " beginnen, gefolgt von einer möglichst präzisen Überschrift, danke!

Moderator: Algorithmen und Datenstrukturen

Forumsregeln
Bei Postings zu Vorlesungsthema X lassen Sie Ihr Betreff bitte mit "X: " beginnen, gefolgt von einer möglichst präzisen Überschrift, danke!
JRS
Erstie
Erstie
Beiträge: 15
Registriert: 5. Nov 2015 17:49

Verständnisfrage zur Java HashMap

Beitrag von JRS » 18. Jul 2016 14:02

Hallo allerseits,

ich wollte mir mal die Java-Implementierung der find-Methode der HashMap anschauen. Ich hatte es aus der Vorlesung so verstanden, dass wir dazu mit der Hashfunktion den Key K zum zu findenden Value V bilden und dann an dieser Stelle im Array nachschauen, ob der an dieser Stelle gespeicherte Value mit V übereinstimmt. Falls nein, wird neu gehasht (mit Linear Probing, Qudratic Probing oder Double Hashing) und wieder nachgeschaut. Somit würden wir im Average Case auf O(1) kommen.

In Java sieht es für mich allerdings so aus, als hätte die implementierte Funktion Komplexität O(n): http://grepcode.com/file/repository.gre ... .Object%29

Das kann doch irgendwie nicht sein, oder? Würde ja dann keinen Sinn machen, eine HashMap zu verwenden. Vielleicht verstehe ich den Code auch nicht.
Kann mir dazu jemand weiterhelfen?

Prof. Karsten Weihe
Moderator
Moderator
Beiträge: 1824
Registriert: 21. Feb 2005 16:33

Re: Verständnisfrage zur Java HashMap

Beitrag von Prof. Karsten Weihe » 18. Jul 2016 16:14

JRS hat geschrieben: Somit würden wir im Average Case auf O(1) kommen.
In Java sieht es für mich allerdings so aus, als hätte die implementierte Funktion Komplexität O(n)
Was ist \(n\) bei Ihnen?

Im Worst Case wird man für Einfügen und Finden in einer Hashtable nichts Besseres herausbekommen als "\(\Theta\)(Arraygröße)", denn schlimmstenfalls wird man doch wieder alle Komponenten des Arrays aufsuchen müssen.

Im Average Case hingegen kann man unter gewissen Annahmen, die durch reale Hashfunktionen nur näherungsweise erfüllt werden, eine Komplexität erreichen, die nur noch vom Füllgrad der Hashtable abhängt, bei festem Füllgrad also in \(\Theta(1)\) ist.

Wo genau sehen Sie einen Widerspruch?

KW

JRS
Erstie
Erstie
Beiträge: 15
Registriert: 5. Nov 2015 17:49

Re: Verständnisfrage zur Java HashMap

Beitrag von JRS » 18. Jul 2016 19:34

Tut mir Leid, \(n\) sollte die Arraygröße sein.

Ich habe nochmal drüber nachgedacht, und jetzt ist es mir klarer.
Für das Finden müssen wir also tatsächlich einmal das gesamte Array durchlaufen, bis wir das Element finden - daran lässt sich auch nichts ändern. Und genau das wird in der Java Methode .containsValue(...) auch gemacht. Danke!

JRS
Erstie
Erstie
Beiträge: 15
Registriert: 5. Nov 2015 17:49

Re: Verständnisfrage zur Java HashMap

Beitrag von JRS » 25. Jul 2016 10:45

Ich muss noch einmal nachhaken, weil es mir doch noch nicht ganz klar geworden ist. Ich hatte glaube ich die Keys und Values etwas durcheinander gebracht. Ich schreibe mal auf, wie ich es momentan verstehe, und wäre dankbar für Bestätigung oder Korrektur.

- Methode \(containsKey (T\ key)\) bildet den Hashwert des keys über die Hashfunktion. Der Hashwert ist der Arrayindex, an dem nachgeschaut wird. Wird der Key an dieser Stelle gefunden, wird \(true\) zurückgeliefert. Ist das Arrayelement an dieser Stelle leer (\(null / void\)), wird \(false\) zurückgeliefert. Ist der Arrayeintrag nicht leer, der gespeicherte key stimmt aber nicht mit dem übergebenen key überein, wird neu gehasht (z.B. mit Double Hashing) und am neu berechneten Arrayindex die Prozedur wiederholt. Dies wird solange durchgeführt, bis entweder irgendwann der richtige key gefunden wird (\(true\)) oder man bei Iteration \(i == n\) (\(n\) Arraygröße) angekommen ist, dann wird \(false\) zurückgeliefert.

- Methode \(get(T\ key)\) arbeitet genauso wie \(containsKey(key)\), und liefert bei Finden des keys den value zu diesem key zurück, oder falls der key nicht enthalten ist wird \(null\) zurückgegeben.

- Methode \(containsValue(V\ value)\) kann nicht direkt einen Hashwert aus dem key bilden, da der key nicht bekannt ist. Daher muss das Array durchlaufen werden, bis entweder in einem Eintrag das richtige value-Objekt gefunden wird (\(return\ true\)) oder man am Ende des Arrays angekommen ist (\(return\ false\)).

Prof. Karsten Weihe
Moderator
Moderator
Beiträge: 1824
Registriert: 21. Feb 2005 16:33

Re: Verständnisfrage zur Java HashMap

Beitrag von Prof. Karsten Weihe » 25. Jul 2016 11:08

JRS hat geschrieben: - Methode \(containsKey (T\ key)\) bildet den Hashwert des keys über die Hashfunktion. Der Hashwert ist der Arrayindex, an dem nachgeschaut wird.
Ich weiß ehrlich gesagt nicht, wie ich Ihre Formulierungen verstehen soll.

Folgendes: Methoden wie containsKey lesen einen Hashcode aus dem Key aus mittels der Methode hashCode, die in der Key-Klasse entweder von Object ererbt oder in der Key-Klasse selbst (oder einer ihrer Superklassen) überschrieben wurde, siehe https://docs.oracle.com/javase/7/docs/a ... hashCode(). Dieser Hashcode wird dann in der HashMap als Parameter für die Hashfunktionen verwendet, die die einzelnen zu durchsuchenden Arrayindizes liefern.

Ich hatte in der Vorlesung an zwei Beispielen (int und String) diskutiert, wie es aussehen könnte, wenn die Keys selbst Parameter der Hashfunction sind. Bei der Java-HashMap gibt es zwei "Hashings" (Verstreuungen): erst durch Methode hashCode, dann noch einmal durch die Hashfunktionen in HashMap. Wobei Methode hashCode natürlich auch ganz primitiv implementiert werden kann und dann nicht wirklich streut.
JRS hat geschrieben: - Methode \(get(T\ key)\) arbeitet genauso wie \(containsKey(key)\), und liefert bei Finden des keys den value zu diesem key zurück, oder falls der key nicht enthalten ist wird \(null\) zurückgegeben.
Ja.
JRS hat geschrieben: - Methode \(containsValue(V\ value)\) kann nicht direkt einen Hashwert aus dem key bilden, da der key nicht bekannt ist. Daher muss das Array durchlaufen werden, bis entweder in einem Eintrag das richtige value-Objekt gefunden wird (\(return\ true\)) oder man am Ende des Arrays angekommen ist (\(return\ false\)).
Das wäre die einfache, naheliegende Implementation. Man könnte natürlich in der Hashmap noch eine weitere Hashtabelle für die Values verwalten. Ich weiß aber nicht, ob so etwas in den gängigen Implementationen von HashMap gemacht wird.

KW

JRS
Erstie
Erstie
Beiträge: 15
Registriert: 5. Nov 2015 17:49

Re: Verständnisfrage zur Java HashMap

Beitrag von JRS » 25. Jul 2016 11:50

Vielen Dank, ich glaube ich habe es jetzt verstanden.

Antworten

Zurück zu „AuD: Vorlesung“