Zugriff auf eine HashMap

freakC++

Hallo zusammen,

ich verstehe nicht, warum der Zugriff auf eine HashMap so effizient, also O(1) und nicht O(n) ist. Auch wenn der Key keine Zahl, sondern eben der Hashwert eines Strings ist, muss doch erstmal danach gesucht werden und das deutet wieder auf O(n) hin!?

Vielen Dank
LG, freakC++

Dasd

Nein, weil der Hashwert selbst als Arrayindex verwendet werden kann (bzw. direkt darin umgerechnet wird).

Siehe z.B. http://www.docjar.com/html/api/java/util/Hashtable.java.html, ab Zeile 355.

freakC++

Ok, das verstehe ich. Dann müsste O(1) aber auch beispielsweise für die ArrayList gelten, da dort ja auch über einen Arrayindex auf die Felder zugegriffen werden, oder?

Vielen Dank
LG, freakC++

Dasd

Das schon. Allerdings haben eine Liste und eine Map verschiedene Aufgaben, so dass ein direkter Vergleich nicht sinnvoll ist.

... musst du ihm so komisch wiedersprechen? Natürlich ist ein direkter Zugriff über den Index auf eine ArrayList o(1).

Im Gegensatz dazu hat eine LinkedList, welche Zugriffszeit bei dem aufruf:

list.get(i)

??

Eine ArrayList ist übrigens auch eine Hashmap, Stichwort direktes Hashing .

freakC++

Dafür ist dann das Einfügen/Löschen sehr rechenaufwändig, oder? Immerhin müssen alle Elemente um eins nach vorne/hinten verschoben werden.

Noch ne andere Frage. Set nimmt ein Objekt maximal einmal auf. Warum kompiliet dieser Code?

Integer io = new Integer(29);
Set a = new HashSet();
a.add(io); //einmal einfügen
a.add(io); //noch einmal einfügen

Vielen Dank
LG, freakC++

TyRoXx

freakC++ schrieb:

Noch ne andere Frage. Set nimmt ein Objekt maximal einmal auf. Warum kompiliet dieser Code?
Integer io = new Integer(29);
Set a = new HashSet();
a.add(io); //einmal einfügen
a.add(io); //noch einmal einfügen

Äh, weil HashSet eben so funktioniert?

Dafür ist dann das Einfügen/Löschen sehr rechenaufwändig, oder?

Amortisiert in O(1). Hängt aber vom Einzelfall ab, wie immer.

TyRoXx

weaw schrieb:

Dafür ist dann das Einfügen/Löschen sehr rechenaufwändig, oder?

Amortisiert in O(1). Hängt aber vom Einzelfall ab, wie immer.

Falsch und Widerspruch. Komplexität hängt eben nicht "vom Einzelfall ab".

Einfügen und Löschen an zufälligen Positionen haben bei ArrayList s der Länge N den Aufwand O(N), weil im Schnitt N/2 Elemente verschoben werden müssen.

Komplexität hängt eben nicht "vom Einzelfall ab".

Ja, das mit dem Einzelfall war aber auch mehr auf den Rechenaufwand in der Praxis bezogen. Manchmal ist eine verzeigerte Liste eben sinnvoller als eine mit Arrays implementierte und umgekehrt.

Einfügen und Löschen an zufälligen Positionen haben bei ArrayLists der Länge N den Aufwand O(N), weil im Schnitt N/2 Elemente verschoben werden müssen.

Ich spreche von amortisierter Laufzeit, du von der durchschnittlichen. Da ist ein feiner, aber umso wichtigerer Unterschied.

Fedaykin

Hab ich die O-Notation schon so verdrängt? Aber ich dachte O(N) wäre die Laufzeit im Worst Case. Und der sollte bei einer HashMap schon N sein (wenn die Map stark befüllt ist muss ja auch beim Zugriff nach den Wert in den nachfolgenden Zellen gesucht werden). Im besten Fall war sie o(1) (Ich dachte gerade das war die unterscheidung zwischen o und O und irgendwie gab es noch das durchschnittliche Laufzeitverhalten.) Kann mich da bitte einer Korrigieren?

Psycho

Integer io = new Integer(29);
Set a = new HashSet();
a.add(io); //einmal einfügen
a.add(io); //noch einmal einfügen

warum sollte er nicht kompilieren?
allerdings wird er dir dein io nicht nochmal in das set einfügen. der 2te aufruf liefert false.

@Fedaykin: Ob O, Θ, Ω, o, oder ω sagt a priori nichts darüber aus, ob man von worst-, best- oder average case (oder eben von amortisierten Kosten) spricht.
Das sind nur unterschiedliche Mengen von Funktionen. Siehe http://de.wikipedia.org/wiki/O-Notation#Definition

... nicht so unrecht...

Fedaykin schrieb:

Und der sollte bei einer HashMap schon N sein (wenn die Map stark befüllt ist muss ja auch beim Zugriff nach den Wert in den nachfolgenden Zellen gesucht werden).

Wenn die Hash-Funktion übertrieben schlecht ist hasht sie alles in ein Bucked und deine HashMap wird zur Verketteten Liste. Aber ich bezweifele ma stark, dass sowas bei der HashMap, -Set, etc. aus dem JDK passiert... Man kann schon mit einem store und get Verhalten o(1) bekommt...

freakC++

Psycho schrieb:

Integer io = new Integer(29);
Set a = new HashSet();
a.add(io); //einmal einfügen
a.add(io); //noch einmal einfügen
warum sollte er nicht kompilieren?
allerdings wird er dir dein io nicht nochmal in das set einfügen. der 2te aufruf liefert false.

Achso, ich dachte, dass SET dann eine Exception wirft.

Danke
LG, freakC++

TyRoXx

freakC++ schrieb:

Achso, ich dachte, dass SET dann eine Exception wirft.

Was genau hält dich davon ab, die Dokumentation von Java zu lesen?

... doch auf Englisch, maaaannnnnn!!!