Ich habe solche Fragen in der Vergangenheit oft gestoßen. Leider, ich schäme mich, das Fundament ist zu arm, es gibt keinen Weg, ich fühle mich Unrecht getan
Jetzt müssen wir über die Unterschiede und Verbindungen zwischen diesen drei sprechen: Diese drei implementieren die Listenschnittstelle, alle sind in der Listenschnittstelle definiert und haben auch Methoden der Sammlungsschnittstelle.
ArrayList: Verwendet die Array -Methode, um Daten, Abfragen und Änderungsgeschwindigkeit zu speichern, aber die Zugabe und Löschgeschwindigkeit sind langsam.
LinkedList: Verwendet die Methode der verknüpften Liste, um Daten zu speichern. Die Abfrage- und Änderungsgeschwindigkeit ist langsam, aber die Zugabe und Löschgeschwindigkeit sind schnell.
Vektor: Es wurde auch Arrays für die Speicherung verwendet. Iteratoren, Aufzählungen, GET (INT -Index) und Indexof (int Index), aber ArrayList hat keine Aufzählungen
ArrayList und Vektor verwenden Arrays, um Daten zu speichern. Operationen, so dass die Indexdaten schnell eingefügt werden. oder Rückwärtstraversal, aber nur dieses Element ist bei der Einfügung von Daten erforderlich.
Lineare Tabellen, verknüpfte Listen und Hash -Tabellen werden häufig verwendete Datenstrukturen. Diese Klassen befinden sich alle im Java.util -Paket. In diesem Artikel wird versucht, den Lesern die Rolle jeder Klasse zu erklären und wie man sie durch eine einfache Beschreibung korrekt verwendet.
Sammlung ├List │ ├linkedList │ ├ArrayList │ └Vector │ └Stack └SetMap ├Hashtable ├HashMap └WeakhashMap
Sammlungsschnittstelle
Die Sammlung ist die grundlegendste Sammelschnittstelle. Einige Sammlungen erlauben die gleichen Elemente, während andere nicht. Einige können sortieren, andere können nicht. Das Java SDK bietet keine Klassen, die direkt aus der Sammlung geerbt werden.
Alle Klassen, die die Sammelschnittstelle implementieren, müssen zwei Standardkonstruktoren bereitstellen: Der parameterlose Konstruktor wird verwendet, um eine leere Sammlung zu erstellen, und es gibt einen Sammelparameterkonstruktor, um eine neue Sammlung zu erstellen, diese neue Sammlung und Pass. Gleiches Element. Der letztere Konstruktor ermöglicht es dem Benutzer, eine Sammlung zu kopieren.
Wie kann man jedes Element in einer Sammlung durchführen? Unabhängig von der tatsächlichen Art der Sammlung unterstützt sie eine Iterator () -Methode, die einen Iterator zurückgibt, und verwendet diesen Iterator, um auf jedes Element in der Sammlung nacheinander zuzugreifen. Typische Verwendung sind wie folgt:
Iterator it = collection.iterator ();
Die beiden von der Sammlungsschnittstelle abgeleiteten Schnittstellen sind Liste und festgelegt.
Listenschnittstelle
List ist eine geordnete Sammlung. Mit dieser Schnittstelle können Sie die Position der einzelnen Elementeinfügungen genau steuern. Benutzer können Indizes (die Position von Elementen in der Liste, ähnlich wie bei Array -Einweisen) verwenden, um in der Liste auf Elemente zuzugreifen, die den Arrays von Java ähnlich sind.
Im Gegensatz zum unten erwähnten Satz erlaubt die Liste dieselben Elemente.
Zusätzlich zu der Iterator () -Methode, die die erforderliche Sammelschnittstelle hat, enthält die Liste auch eine Listiterator () -Methode, die eine Listiterator -Schnittstelle im Vergleich zur Standard -Iterator -Schnittstelle zurückgibt. Löschen, Elemente einstellen und auch nach vorne oder rückwärts fahren.
Gemeinsame Klassen, die Listenschnittstellen implementieren, umfassen LinkedList, ArrayList, Vector und Stack.
LinkedList -Klasse
Die LinkedList implementiert die Listenschnittstelle und ermöglicht Nullelemente. Darüber hinaus bietet LinkedList zusätzliche GET, Entfernen, Einfügen und Einfügen von Methoden am Kopf oder Schwanz der LinkedList. Diese Operationen ermöglichen es LinkedList, als Stapel, Warteschlange oder Zwei-Wege-Warteschlange zu verwenden.
Beachten Sie, dass die LinkedList keine synchrone Methode hat. Wenn mehrere Threads gleichzeitig auf eine Liste zugreifen, müssen Sie die Zugriffssynchronisation selbst implementieren. Eine Lösung besteht darin, beim Erstellen einer synchronen Liste zu konstruieren:
Listlist = collections.synchronizedList (Neue LinkedList (...));
ArrayList -Klasse
ArrayList implementiert Arrays mit variabler Größe. Es ermöglicht allen Elementen, einschließlich Null. ArrayList wird nicht synchronisiert.
Die Laufzeit der Größe der Größe, Isempty, Get, Set -Methoden ist konstant. Der Overhead der Add -Methode ist jedoch eine amortisierte Konstante, und es dauert O (n) Zeit, um N -Elemente hinzuzufügen. Die anderen Methoden haben eine lineare Laufzeit.
Jede ArrayList -Instanz hat eine Kapazität, die die Größe des Arrays hat, das zum Speichern von Elementen verwendet wird. Diese Kapazität kann automatisch zunehmen, wenn neue Elemente ständig hinzugefügt werden, der Wachstumsalgorithmus ist jedoch nicht definiert. Wenn eine große Anzahl von Elementen eingefügt werden muss, kann die Sicherungscoapacity -Methode vor dem Einfügen aufgerufen werden, um die Kapazität der Arraylist zu erhöhen, um die Insertionseffizienz zu verbessern.
Wie LinkedList ist auch ArrayList unsynchronisiert.
Vektorklasse
Der Vektor ist ArrayList sehr ähnlich, aber Vektor ist synchron. Von Vektor erstellte Iterator ist, obwohl Iterator von ArrayList erstellt wurde, dieselbe Schnittstelle wie von ArrayList erstellte Iterator, da der Vektor synchronisiert ist, wenn ein Iterator erstellt wird und verwendet wird, ein anderer Thread den Status des Vektors ändert (z. B. Hinzufügen von Hinzufügen zu Hinzufügen von Hinzufügen oder etwas entfernen) zu diesem Zeitpunkt wird die ConcurrentModificificationException ausgeworfen, wenn die Iteratormethode aufgerufen wird, sodass die Ausnahme gefangen werden muss.
Stapelklasse
Stack erbt von Vector und implementiert einen letzten Stack. Stack bietet 5 zusätzliche Methoden, mit denen Vektor als Stapel verwendet werden kann. Die grundlegenden Push- und POP -Methoden und die Peek -Methode erheben die Elemente oben im Stapel, die leere Methode testet, ob der Stapel leer ist, und die Suchmethode erkennt die Position eines Elements im Stapel. Stack ist nur erstellt und ist ein leerer Stapel.
Setzen Sie die Schnittstelle
SET ist eine Sammlung, die keine doppelten Elemente enthält, dh zwei beliebige Elemente E1 und E2 haben E1.Equals (E2) = Falsch, und das SET hat höchstens ein Nullelement.
Offensichtlich hat der Konstruktor von SET eine Einschränkung, und der übergebene Sammlungsparameter kann keine doppelten Elemente enthalten.
Bitte beachten Sie: Veränderliche Objekte müssen mit Sorgfalt betrieben werden. Wenn ein veränderliches Element in einem Satz seinen eigenen Zustand ändert und Objekt verursacht.Equals (Objekt) = treu, um einige Probleme zu verursachen.
Kartenschnittstelle
Bitte beachten Sie, dass die Karte die Sammlungsschnittstelle nicht erbt und die Karte eine Zuordnung von Schlüssel zu Wert bietet. Eine Karte kann nicht denselben Schlüssel enthalten, und jeder Schlüssel kann nur einen Wert zuordnen. Die Kartenschnittstelle bietet drei Arten von Ansichten der Sammlung.
Hashtable -Klasse
Hashtable erbt die Kartenschnittstelle und implementiert eine Hash-Tabelle mit einem Schlüsselwert-Zuordnung. Jedes Nicht-Null-Objekt kann als Schlüssel oder Wert verwendet werden.
Verwenden Sie Put (Schlüssel, Wert), um Daten hinzuzufügen. Verwenden Sie GET (Schlüssel), um Daten abzurufen.
Hashtable passt die Leistung durch die anfänglichen Kapazitäts- und Lastfaktorparameter an. Normalerweise kann der Standardlastfaktor 0,75 Zeit- und Raumausgleich besser erreichen. Das Erhöhen des Lastfaktors kann Platz sparen, aber die entsprechende Suchzeit erhöht sich, was sich auf die Operationen wie Get and Put auswirkt.
Ein einfaches Beispiel für die Verwendung eines Hashtabels ist wie folgt: Stellen Sie 1, 2 und 3 in einen Hashtable ein, und ihre Schlüssel sind "eins", "zwei", "drei":
Hashtable nummern = neuer Hashtable ();
nummern.put ("eins", neue Ganzzahl (1));
nummern.put ("zwei", neue Integer (2));
nummern.put ("drei", neue Ganzzahl (3));
Verwenden Sie den entsprechenden Schlüssel, um eine Nummer wie 2 herauszunehmen:
Ganzzahl n = (Integer) number.get ("zwei");
System.out.println ("Two =" + n);
Da ein Objekt als Schlüssel die Position des entsprechenden Werts durch Berechnung seiner Hash -Funktion bestimmt, muss jedes Objekt als Schlüssel den HashCode und gleiche Methoden implementieren. Hashcode und Equals -Methoden erben aus dem Stammklassenobjekt. ) = dann muss ihr Hashcode gleich sein, aber wenn die beiden Objekte unterschiedlich sind, sind ihre Hashcodes möglicherweise nicht unterschiedlich. von operativen Hash -Tabellen.
Wenn dasselbe Objekt unterschiedliche Hashcodes hat, hat die Operation in der Hash -Tabelle unerwartete Ergebnisse (die erwartete GET -Methode gibt NULL zurück). Gleichzeitig schreiben Sie nicht nur einen von ihnen.
Hashtable wird synchronisiert.
Hashmap -Klasse
HashMap ist ähnlich wie Hashtable. Der Unterschied besteht darin, dass Hashmap asynchron ist und Null zulässt, d. H. Nullwert und Nullschlüssel. Aber wenn HashMap als Sammlung angesehen wird (die VALUTE () -Methode kann eine Sammlung zurückgeben), ist die iterative Unteroperationszeit proportional zur Kapazität von HashMap. Wenn die Leistung von Iterationsoperationen sehr wichtig ist, setzen Sie die Initialisierungskapazität von HashMap nicht auf zu hoch oder der Lastfaktor ist zu niedrig.
WeaChashMap -Klasse
WeaPhashMap ist eine verbesserte Hashmap, die "schwache Referenz" auf den Schlüssel implementiert.
Zusammenfassen
Wenn Sie die Warteschlange und andere Operationen in Betracht ziehen, sollten Sie die Liste verwenden.
Wenn sich das Programm in einer einsthread-Umgebung oder in einem Thread befindet, wenn man asynchrone Klassen berücksichtigt, ist es effizienter.
Achten Sie besonders auf den Betrieb von Hash -Tabellen.
Versuchen Sie, die Schnittstelle anstelle des tatsächlichen Typs zurückzugeben, z. B. die Rückgabe einer Liste anstelle einer ArrayList. Dies ist für abstrakte Programmierung.
Synchronisation
Vektor ist synchron. Einige Methoden in dieser Klasse stellen sicher, dass die Objekte in Vektor mit Thread-Sicherheit sind. ArrayList ist asynchron, daher sind die Objekte in ArrayList nicht mit Thread-Safe. Da die Anforderungen an die Synchronisation die Ausführungseffizienz beeinflussen, ist die Verwendung von ArrayList eine gute Wahl, wenn Sie keine Thread-Safe-Sammlungen benötigen, die aufgrund der Synchronisation unnötige Leistungsaufwand vermeiden können.
Datenwachstum
Aus dem internen Implementierungsmechanismus verwenden ArrayList und Vector beide Arrays (Array), um Objekte in der Sammlung zu steuern. Wenn Sie diesen beiden Typen Elemente hinzufügen, überschreitet die Anzahl der Elemente die aktuelle Länge des internen Arrays, die die Länge des internen Arrays standardmäßig erweitern müssen Original 50% davon. Wenn Sie diese Sammlung das letzte Mal erhalten, nimmt Sie immer mehr Platz als Sie tatsächlich benötigen. Wenn Sie also viele Daten in einer Sammlung sparen möchten, können Sie Vektor verwenden, da Sie unnötige Ressourcenaufwand vermeiden können, indem Sie die Initialisierungsgröße der Sammlung festlegen.
Nutzungsmodus
In ArrayList und Vector dauert es die gleiche Zeit, um Daten aus einem bestimmten Ort (über den Index) zu finden oder ein Element am Ende des Satzes hinzuzufügen und zu entfernen. Wenn jedoch Elemente an anderer Stelle im Satz hinzugefügt oder entfernt werden, wächst die ausgegebene Zeit linear: O (NI), wobei N die Anzahl der Elemente im Satz darstellt, und ich stellt die Indexposition dar, in der Elemente Elemente erhöhen oder entfernen. Warum passiert das? Es wird vermutet, dass bei der Ausführung der oben genannten Operationen alle Elemente nach dem I-ten und i-Th-Element im Satz Verschiebungsvorgänge durchführen müssen. Was bedeutet das alles?
Dies bedeutet, dass Sie nur nach Elementen in einer bestimmten Position suchen oder einfach Elemente am Ende der Sammlung hinzufügen und entfernen, und dann ist die Verwendung von Vektor oder ArrayList in Ordnung. Wenn es sich um eine andere Operation handelt, sollten Sie eine andere Sammlungsbetriebsklasse besser auswählen. Zum Beispiel ist die Zeit, die die LinkList -Sammlungsklasse benötigt, um Elemente an einer Position in der Sammlung hinzuzufügen oder zu entfernen, gleich (1)? ist der Ort des Index. LinkList erstellt auch Objekte für jedes eingefügte Element, und alles, was Sie verstehen müssen, bringt auch zusätzlichen Aufwand.
Schließlich schlägt Peter Haggar im Buch Practical Java vor, ein einfaches Array (Array) anstelle von Vector oder ArrayList zu verwenden. Dies gilt insbesondere für Programme mit hoher Ausführungseffizienz. Da die Verwendung von Arrays (Arrays) die Synchronisation vermeidet, werden zusätzliche Methodenaufrufe und unnötige Neuzuweisung von Raumvorgängen.