Zugriff auf eine HashMap

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!!!