Collections (Java): Unterschied zwischen den Versionen

Aus Byte-Welt Wiki
Zur Navigation springenZur Suche springen
(List)
K (Änderung 8421 von L-ectron-X (Diskussion) rückgängig gemacht.)
 
(23 dazwischenliegende Versionen von 2 Benutzern werden nicht angezeigt)
Zeile 4: Zeile 4:
 
  (Eine Collection stellt eine Gruppe von Objekten dar, bekannt als ihr Element. Einige Collections erlauben doppelte Elemente, andere nicht. Manche sind geordnet, manche ungeordnet)
 
  (Eine Collection stellt eine Gruppe von Objekten dar, bekannt als ihr Element. Einige Collections erlauben doppelte Elemente, andere nicht. Manche sind geordnet, manche ungeordnet)
  
Eine Collection ist somit vorstellbar als eine Tasche in die man mehrere Objekte hinein tun kann und wieder rausholen kann. Das Interface Collection ist das oberste Elemente der Hierarchie und bietet keine direkten Implementationen an.
+
Eine {{JAPI|Collection}} ist somit vorstellbar als eine Tasche in die man mehrere [[Objekt|Objekte]] hinein tun kann und wieder rausholen kann. Das [[Interface]] Collection ist das oberste Elemente der Hierarchie und bietet keine direkten Implementationen an.
  
 
Um eine solche Tasche nutzen zu können muss man sich erst überlegen, welche Art von Tasche man überhaupt haben will. Wie oben erwähnt gibt es verschiedene Arten davon (mit Dupilkaten, ohne Duplikaten, geordnet oder nicht geordnet). Alle haben aber gemeinsam, dass sie eine Tasche zum aufbewahren von Objekten sind.
 
Um eine solche Tasche nutzen zu können muss man sich erst überlegen, welche Art von Tasche man überhaupt haben will. Wie oben erwähnt gibt es verschiedene Arten davon (mit Dupilkaten, ohne Duplikaten, geordnet oder nicht geordnet). Alle haben aber gemeinsam, dass sie eine Tasche zum aufbewahren von Objekten sind.
  
Dieser Beitrag soll eine kleine Übersicht über diese enorme Hierarchie darstellen und die Vor- bzw. Nachteile einiger Collection Klassen zeigen. Der Beitrag gewährt keinen Anspruch auf Vollständigkeit und ist angeleht an dem [http://docs.oracle.com/javase/tutorial/collections/index.html Tutorial zu Collections] von Oracle (früher Sun).
+
Dieser Beitrag soll eine kleine Übersicht über diese enorme Hierarchie darstellen und die Vor- bzw. Nachteile einiger Collection [[Klasse|Klassen]] zeigen. Der Beitrag gewährt keinen Anspruch auf Vollständigkeit und ist angeleht an dem [http://docs.oracle.com/javase/tutorial/collections/index.html Tutorial zu Collections] von Oracle (früher Sun).
  
 
Betrachten wir zuerst einmal die Hierarchie der Interfaces die uns Oracle bietet:
 
Betrachten wir zuerst einmal die Hierarchie der Interfaces die uns Oracle bietet:
Zeile 15: Zeile 15:
  
 
= List =
 
= List =
  Eine geordnete Collection (bekannt auch als Sequenz). Der Benutzer hat die genau Kontrolle darüber, an welcher Stelle in der Liste jedes Element eingefügt werden soll.  
+
  Eine geordnete Collection (bekannt auch als Sequenz). Der Benutzer hat die genau Kontrolle darüber, an welcher Stelle in der [[Liste]] jedes [[Element]] eingefügt werden soll.  
 
  Der Benutzer kann über den Index (die Position in der Liste) auf die Elemente zugreifen und nach Elementen in der Liste suchen.
 
  Der Benutzer kann über den Index (die Position in der Liste) auf die Elemente zugreifen und nach Elementen in der Liste suchen.
  
Die drei bekanntesten Implementationen des List Interfaces sind [http://www.google.de/search?btnI&q=site:docs.oracle.com/javase/7/docs/api/%20inurl:Vector Vector], [http://www.google.de/search?btnI&q=site:docs.oracle.com/javase/7/docs/api/%20inurl:ArrayList ArrayList] und [http://www.google.de/search?btnI&q=site:docs.oracle.com/javase/7/docs/api/%20inurl:LinkedList LinkedList]. Alle diese Elemente werden im Folgenden betrachtet. Sie bieten eine geordnete Struktur (geordnet im Sinne von Ordnung nach der Einfügereihenfolge) und erlauben doppelte Elemente.
+
Die drei bekanntesten Implementationen des {{JAPI|List}} Interfaces sind {{JAPI|Vector}}, {{JAPI|ArrayList}} und {{JAPI|LinkedList}}. Alle diese Elemente werden im Folgenden betrachtet. Sie bieten eine geordnete Struktur (geordnet im Sinne von Ordnung nach der Einfügereihenfolge) und erlauben doppelte Elemente.
  
 
==Vector==
 
==Vector==
Der Vector ist im Grunde nichts anderes als ein Array mit ein paar Methoden außenrum. Intern werden die Objekte in einem Array gespeichert. Aufgrund des Arrays ist der Vector schnell beim indexbasierten Zugriff auf seine Elemente.
+
Der {{JAPI|Vector}} ist im Grunde nichts anderes als ein [[Array]] mit ein paar [[Methode|Methoden]] außenrum. Intern werden die Objekte in einem [[Array]] gespeichert. Aufgrund des Arrays ist der Vector schnell beim indexbasierten Zugriff auf seine Elemente.
D.h. das Iterieren über die Elemente kann schnell und einfach per for-Schleife realisiert werden.
+
D.h. das Iterieren über die Elemente kann schnell und einfach per [[for-Schleife]] realisiert werden.
<code=java>
+
<syntaxhighlight lang="java">
 
for(int i = 0, j = vector.size(); i < j; i++) {
 
for(int i = 0, j = vector.size(); i < j; i++) {
 
   System.out.println(vector.get(i));
 
   System.out.println(vector.get(i));
 
}
 
}
</code=java>
+
</syntaxhighlight>
  
Des Weiteren sind alle Methoden des Vectors synchronisiert, d.h. geschützt vor Multihread-Zugriffen. Der Nachteil macht sich aber bei "normalen" Programmen bemerkbar, die nur einen Thread besitzen, da das Synchronisieren in diesem Falle mehr nachteilig ist, da unnötig. Weiterhin hat der Vector Probleme, falls oft Elemente hinzugefügt bzw. gelöscht werden.<br>
+
Des Weiteren sind alle [[Methode]]n des Vectors synchronisiert, d.h. geschützt vor Multihread-Zugriffen. Der Nachteil macht sich aber bei "normalen" Programmen bemerkbar, die nur einen [[Thread]] besitzen, da das Synchronisieren in diesem Falle mehr nachteilig ist, da unnötig. Weiterhin hat der Vector Probleme, falls oft Elemente hinzugefügt bzw. gelöscht werden.<br>
 
Da der Vector ein Array ist, tritt irgendwann die Situation auf, dass der Array voll ist. Wird nun ein weiteres Element hinzufügt, muss intern ein neuer, größerer Array angelegt werden und alle Elemente des alten Arrays hinüberkopiert werden.<br>
 
Da der Vector ein Array ist, tritt irgendwann die Situation auf, dass der Array voll ist. Wird nun ein weiteres Element hinzufügt, muss intern ein neuer, größerer Array angelegt werden und alle Elemente des alten Arrays hinüberkopiert werden.<br>
Beim Löschen eines Index muss der Array-Rest größer des Index jeweils um eine Stelle nach links kopiert werden, um die entstandene Lücke zu füllen.<br>
+
Beim Löschen eines [[Index]] muss der Array-Rest größer des Index jeweils um eine Stelle nach links kopiert werden, um die entstandene Lücke zu füllen.<br>
 
Diese beiden Operationen benötigen natürlich "etwas Zeit".
 
Diese beiden Operationen benötigen natürlich "etwas Zeit".
  
 
==ArrayList==
 
==ArrayList==
Die ArrayList ist im Grunde nichts anderes als ein nichtsynchronisierter Vector. D.h. alle Eigenschaften außer den synchronisierten Methoden, die oben aufgeführt sind, treffen auch auf die ArrayList zu.<br>
+
Die {{JAPI|ArrayList}} ist im Grunde nichts anderes als ein nichtsynchronisierter Vector. D.h. alle Eigenschaften außer den synchronisierten Methoden, die oben aufgeführt sind, treffen auch auf die ArrayList zu.<br>
  
'''Allgemeine Regel'''
+
'''Allgemeine Regel'''
 
+
Wenn man eine indexbasierte Collection haben will, muss man sich überlegen, ob man mit einem oder mehreren Threads arbeitet: <br>
Wenn man eine indexbasierte Collection haben will, muss man sich überlegen, ob man mit einem oder mehreren Threads arbeitet: <br>
+
Ein Thread ===> ArrayList (99% der Fälle)<br>
Ein Thread ===> ArrayList (99% der Fälle)<br>
+
Mehrere Threads ===> Vector bzw. eine synchronisierte List ( [http://docs.oracle.com/javase/8/docs/api/java/util/Collections.html#synchronizedList-java.util.List- Collections#syncronizedList(java.util.List)] )
Mehrere Threads ===> Vector bzw. eine synchronisierte List ([http://docs.oracle.com/javase/7/docs/api/java/util/Collections.html#synchronizedList(java.util.List) Collections#syncronizedList(java.util.List)])
 
  
 
==LinkedList==
 
==LinkedList==
Die LinkedList unterscheidet sich von den anderen beiden oben genannten. Sie ist intern kein Array sondern eine doppelt verkette Liste. D.h. die Objekte in der Collection haben jeweils einen Verweis auf ihren Vorgänger, sowie ihren Nachfolger.<br>
+
Die {{JAPI|LinkedList}} unterscheidet sich von den anderen beiden oben genannten. Sie ist intern kein [[Array]] sondern eine doppelt verkette Liste. D.h. die Objekte in der Collection haben jeweils einen Verweis auf ihren Vorgänger, sowie ihren Nachfolger.<br>
Der große Vorteil der Liste ist es, dass Einfüge- bzw. Löschoperationen extrem günstig sind, da hier nur ein paar Zeiger verschoben werden müssen, nie aber Elemente kopiert oder verschoben werden.
+
Der große Vorteil der Liste ist es, dass Einfüge- bzw. Löschoperationen extrem günstig sind, da hier nur ein paar [[Zeiger]] verschoben werden müssen, nie aber Elemente kopiert oder verschoben werden.
  
Verheerend wäre es aber, bei einer LinkedList über einen Index auf die Elemente zuzugreifen. Da LinkedList intern kein Array benutzt und man somit ein Element nicht per Index holen kann, würde bei jedem Indexzugriff vom Startelement über alle Element sich gehangelt, bis der gegebene Index erreicht wurde. Das führt zu einer enormen Laufzeit für einen Zugriff.
+
Verheerend wäre es aber, bei einer {{JAPI|LinkedList}} über einen Index auf die Elemente zuzugreifen. Da LinkedList intern kein Array benutzt und man somit ein Element nicht per Index holen kann, würde bei jedem Indexzugriff vom Startelement über alle Element sich gehangelt, bis der gegebene Index erreicht wurde. Das führt zu einer enormen Laufzeit für einen Zugriff.
Somit ist ein direktes "Herausholen" eines Elements nicht möglich, nur das Iterieren über die Liste ist zu empfehlen.
+
Somit ist ein direktes "Herausholen" eines Elements nicht möglich, nur das [[Iteration|Iterieren]] über die Liste ist zu empfehlen.
<code=java>
+
<syntaxhighlight lang="java">
 
Iterator iter = linkedList.iterator();
 
Iterator iter = linkedList.iterator();
 
while(iter.hasNext()) {
 
while(iter.hasNext()) {
 
   System.out.println(iter.next());
 
   System.out.println(iter.next());
 
}
 
}
</code=java>
+
</syntaxhighlight>
  
'''Allgemeine Regel'''
+
'''Allgemeine Regel'''
LinkedList bieten den Vorteil, dass sie bei vielen Einfüge- bzw Löschoperationen effizienter ist, benötigt aber mehr Speicher (wg. zusätzlicher Referenzen) und keinen direkten Zugriff auf ein Element.
+
LinkedList bieten den Vorteil, dass sie bei vielen Einfüge- bzw Löschoperationen effizienter ist, benötigt aber mehr Speicher (wg. zusätzlicher [[Referenz|Referenzen]]) und keinen direkten Zugriff auf ein Element.
  
 
= Set =
 
= Set =
 +
Ein {{JAPI|Set}} speichert Objekte, ohne dabei Duplikate zuzulassen.
 +
 +
Das bekannteste Set ist das {{JAPI|HashSet}}, in dem die [[Objekt|Objekte]] je nach ihrem [[HashCode]] eingefügt werden. D.h. Java stellt sich intern die Objekte anders dar, als wir sie erzeugen, um sie effizient in das Set einfügen zu können. Das hat zur Folge, dass die Einfügereihenfolge nicht der Reihenfolge entspricht, wenn wir es wieder auslesen.
 +
 +
Auch hier ist kein indexbasierter Zugriff möglich, da auch hier wieder intern kein [[Array]] zum Speichern verwendet wird. Der Zugriff erfolgt wie bei der LinkedList über den {{JAPI|Iterator}}.
 +
 +
 +
'''Allgemeine Regel'''
 +
Wenn ihr eine Tasche haben wollt, in der ihr sicher gehen wollt, dass keine doppelten Elemente vorhanden sind, die Reihenfolge der Elemente, die in der Tasche liegen egal für das Programm ist, so ist ein Set zu verwenden.
 +
 +
Ein Spezialfall des Sets ist das sog. {{JAPI|SortedSet}}, mit seinem Vertreter {{JAPI|TreeSet}}. Hier werden die Objekte nach ihrer natürlichen Ordnung gespeichert. Die zu speichernden Elemente müssen das [[Interface]] {{JAPI|Comparable}} implementieren, so dass eine solche Ordnung gegeben ist.
 +
 +
 +
'''Allgemeine Regel'''
 +
Will man die Vorzüge eines Sets nutzen und zusätzlich die Element geordnet haben, so ist ein {{JAPI|TreeSet}} zu verwenden.
 +
 +
Es gibt noch einige Collection mehr, doch sind die eben vorgestellten Klassen die meist benutzten. Man kann mehr über die Collection Klassen in der API finden und in dem oben verlinkten Tutorial.
  
 
= Map =
 
= Map =
 +
Klassen, die das [[Interface]] {{JAPI|Map}} implementieren gehören nicht zu den Collections. Dennoch möchten wir sie hier im Rahmen dieses Artikels vorstellen.<br>
 +
 +
Maps speichern ebenso, wie die [[Klasse|Klassen]] aus dem oben vorgestellten Collection [[Framework]] Objekte. Eine Map speichert aber pro Zeile nicht nur ein Objekt, sondern ein Schlüssel-Wert-Paar.<br>
 +
Dieses Schlüssel-Wert-Paar besteht aus zwei Objekten: Einem Schlüssel und einem Wert, dem eigentlichen Nutzobjekt, welches in der Map mit dem Schlüssel eindeutig identifiziert werden kann.
 +
So sind auch Duplikate möglich, wenn verschiedene Schlüssel eingesetzt werden.
 +
{{In Arbeit}}
 +
==HashMap==
 +
Siehe auch: [[HashMap (Java_API)]]
 +
 +
==TreeMap==
 +
 +
{{Fragen stellen}}
 +
 +
=Weiterführendes Material=
 +
*[https://docs.oracle.com/javase/8/docs/technotes/guides/collections/index.html Oracle - The Collections Framework]
 +
*[[Doppelte Datensätze aus ArrayList entfernen|Duplikate aus ArrayList entfernen]]
  
[[Kategorie:Java]]
+
[[Kategorie:Java Grundlagen]]
  
 
--[[Benutzer:bygones | bygones]] 29.06.2005 | [[Benutzer:L-ectron-X | L-ectron-X]] (Update 30.08.2013)
 
--[[Benutzer:bygones | bygones]] 29.06.2005 | [[Benutzer:L-ectron-X | L-ectron-X]] (Update 30.08.2013)

Aktuelle Version vom 30. Juli 2018, 09:48 Uhr

Vector, ArrayList und die anderen Collection

Zitat:
A collection represents a group of objects, known as its elements. Some collections allow duplicate elements and others do not. Some are ordered and others unordered.
(Eine Collection stellt eine Gruppe von Objekten dar, bekannt als ihr Element. Einige Collections erlauben doppelte Elemente, andere nicht. Manche sind geordnet, manche ungeordnet)

Eine Collection ist somit vorstellbar als eine Tasche in die man mehrere Objekte hinein tun kann und wieder rausholen kann. Das Interface Collection ist das oberste Elemente der Hierarchie und bietet keine direkten Implementationen an.

Um eine solche Tasche nutzen zu können muss man sich erst überlegen, welche Art von Tasche man überhaupt haben will. Wie oben erwähnt gibt es verschiedene Arten davon (mit Dupilkaten, ohne Duplikaten, geordnet oder nicht geordnet). Alle haben aber gemeinsam, dass sie eine Tasche zum aufbewahren von Objekten sind.

Dieser Beitrag soll eine kleine Übersicht über diese enorme Hierarchie darstellen und die Vor- bzw. Nachteile einiger Collection Klassen zeigen. Der Beitrag gewährt keinen Anspruch auf Vollständigkeit und ist angeleht an dem Tutorial zu Collections von Oracle (früher Sun).

Betrachten wir zuerst einmal die Hierarchie der Interfaces die uns Oracle bietet:

Colls-coreInterfaces.gif

List

Eine geordnete Collection (bekannt auch als Sequenz). Der Benutzer hat die genau Kontrolle darüber, an welcher Stelle in der Liste jedes Element eingefügt werden soll. 
Der Benutzer kann über den Index (die Position in der Liste) auf die Elemente zugreifen und nach Elementen in der Liste suchen.

Die drei bekanntesten Implementationen des List Interfaces sind Vector, ArrayList und LinkedList. Alle diese Elemente werden im Folgenden betrachtet. Sie bieten eine geordnete Struktur (geordnet im Sinne von Ordnung nach der Einfügereihenfolge) und erlauben doppelte Elemente.

Vector

Der Vector ist im Grunde nichts anderes als ein Array mit ein paar Methoden außenrum. Intern werden die Objekte in einem Array gespeichert. Aufgrund des Arrays ist der Vector schnell beim indexbasierten Zugriff auf seine Elemente. D.h. das Iterieren über die Elemente kann schnell und einfach per for-Schleife realisiert werden.

for(int i = 0, j = vector.size(); i < j; i++) {
   System.out.println(vector.get(i));
}

Des Weiteren sind alle Methoden des Vectors synchronisiert, d.h. geschützt vor Multihread-Zugriffen. Der Nachteil macht sich aber bei "normalen" Programmen bemerkbar, die nur einen Thread besitzen, da das Synchronisieren in diesem Falle mehr nachteilig ist, da unnötig. Weiterhin hat der Vector Probleme, falls oft Elemente hinzugefügt bzw. gelöscht werden.
Da der Vector ein Array ist, tritt irgendwann die Situation auf, dass der Array voll ist. Wird nun ein weiteres Element hinzufügt, muss intern ein neuer, größerer Array angelegt werden und alle Elemente des alten Arrays hinüberkopiert werden.
Beim Löschen eines Index muss der Array-Rest größer des Index jeweils um eine Stelle nach links kopiert werden, um die entstandene Lücke zu füllen.
Diese beiden Operationen benötigen natürlich "etwas Zeit".

ArrayList

Die ArrayList ist im Grunde nichts anderes als ein nichtsynchronisierter Vector. D.h. alle Eigenschaften außer den synchronisierten Methoden, die oben aufgeführt sind, treffen auch auf die ArrayList zu.

Allgemeine Regel
Wenn man eine indexbasierte Collection haben will, muss man sich überlegen, ob man mit einem oder mehreren Threads arbeitet: 
Ein Thread ===> ArrayList (99% der Fälle)
Mehrere Threads ===> Vector bzw. eine synchronisierte List ( Collections#syncronizedList(java.util.List) )

LinkedList

Die LinkedList unterscheidet sich von den anderen beiden oben genannten. Sie ist intern kein Array sondern eine doppelt verkette Liste. D.h. die Objekte in der Collection haben jeweils einen Verweis auf ihren Vorgänger, sowie ihren Nachfolger.
Der große Vorteil der Liste ist es, dass Einfüge- bzw. Löschoperationen extrem günstig sind, da hier nur ein paar Zeiger verschoben werden müssen, nie aber Elemente kopiert oder verschoben werden.

Verheerend wäre es aber, bei einer LinkedList über einen Index auf die Elemente zuzugreifen. Da LinkedList intern kein Array benutzt und man somit ein Element nicht per Index holen kann, würde bei jedem Indexzugriff vom Startelement über alle Element sich gehangelt, bis der gegebene Index erreicht wurde. Das führt zu einer enormen Laufzeit für einen Zugriff. Somit ist ein direktes "Herausholen" eines Elements nicht möglich, nur das Iterieren über die Liste ist zu empfehlen.

Iterator iter = linkedList.iterator();
while(iter.hasNext()) {
  System.out.println(iter.next());
}
Allgemeine Regel
LinkedList bieten den Vorteil, dass sie bei vielen Einfüge- bzw Löschoperationen effizienter ist, benötigt aber mehr Speicher (wg. zusätzlicher Referenzen) und keinen direkten Zugriff auf ein Element.

Set

Ein Set speichert Objekte, ohne dabei Duplikate zuzulassen.

Das bekannteste Set ist das HashSet, in dem die Objekte je nach ihrem HashCode eingefügt werden. D.h. Java stellt sich intern die Objekte anders dar, als wir sie erzeugen, um sie effizient in das Set einfügen zu können. Das hat zur Folge, dass die Einfügereihenfolge nicht der Reihenfolge entspricht, wenn wir es wieder auslesen.

Auch hier ist kein indexbasierter Zugriff möglich, da auch hier wieder intern kein Array zum Speichern verwendet wird. Der Zugriff erfolgt wie bei der LinkedList über den Iterator.


Allgemeine Regel
Wenn ihr eine Tasche haben wollt, in der ihr sicher gehen wollt, dass keine doppelten Elemente vorhanden sind, die Reihenfolge der Elemente, die in der Tasche liegen egal für das Programm ist, so ist ein Set zu verwenden.

Ein Spezialfall des Sets ist das sog. SortedSet, mit seinem Vertreter TreeSet. Hier werden die Objekte nach ihrer natürlichen Ordnung gespeichert. Die zu speichernden Elemente müssen das Interface Comparable implementieren, so dass eine solche Ordnung gegeben ist.


Allgemeine Regel
Will man die Vorzüge eines Sets nutzen und zusätzlich die Element geordnet haben, so ist ein TreeSet zu verwenden.

Es gibt noch einige Collection mehr, doch sind die eben vorgestellten Klassen die meist benutzten. Man kann mehr über die Collection Klassen in der API finden und in dem oben verlinkten Tutorial.

Map

Klassen, die das Interface Map implementieren gehören nicht zu den Collections. Dennoch möchten wir sie hier im Rahmen dieses Artikels vorstellen.

Maps speichern ebenso, wie die Klassen aus dem oben vorgestellten Collection Framework Objekte. Eine Map speichert aber pro Zeile nicht nur ein Objekt, sondern ein Schlüssel-Wert-Paar.
Dieses Schlüssel-Wert-Paar besteht aus zwei Objekten: Einem Schlüssel und einem Wert, dem eigentlichen Nutzobjekt, welches in der Map mit dem Schlüssel eindeutig identifiziert werden kann. So sind auch Duplikate möglich, wenn verschiedene Schlüssel eingesetzt werden.

Baustelle.png Dieser Beitrag wird derzeit noch bearbeitet. Der Text ist deshalb unvollständig und kann Fehler oder ungeprüfte Aussagen enthalten.

HashMap

Siehe auch: HashMap (Java_API)

TreeMap

Fragen

Das Thema wurde nicht ausreichend behandelt? Du hast Fragen dazu und brauchst weitere Informationen? Lass Dir von uns helfen!

Wir helfen dir gerne!


Dir hat dieser Artikel gefallen? Oder Du hast Fehler entdeckt und möchtest zur Berichtigung beitragen? Prima! Schreibe einen Kommentar!

Du musst angemeldet sein, um einen Kommentar abzugeben.


Weiterführendes Material

-- bygones 29.06.2005 | L-ectron-X (Update 30.08.2013)