Heim  >  Artikel  >  Java  >  Fassen Sie mehrere häufig verwendete Datenstrukturen in Java zusammen und teilen Sie sie

Fassen Sie mehrere häufig verwendete Datenstrukturen in Java zusammen und teilen Sie sie

巴扎黑
巴扎黑Original
2017-08-01 10:54:561855Durchsuche

Häufig verwendete Datenstrukturen in JAVA (java.util.)

Es gibt mehrere häufig verwendete Datenstrukturen in Java, die hauptsächlich in Sammlung und Karte unterteilt sind sind zwei Hauptschnittstellen (Schnittstellen stellen nur Methoden bereit, keine Implementierungen), und die letztendlich im Programm verwendeten Datenstrukturen sind von diesen Schnittstellen geerbte Datenstrukturklassen. Die Hauptbeziehungen (Vererbungsbeziehungen) sind: (----Weitere Informationen finden Sie in der Java-API-Dokumentation!)

Collection---->Collections                                          SortedMap--- ---> ;TreeMap

Collection---->List----->(Vector ArryList LinkedList)                                           ;HashMap

Collection---->Set------>(HashSet LinkedHashSet SortedSet)

-------------Sammlung---

1. Sammlungen

API--- -Diese Klasse besteht ausschließlich aus statischen Methoden, die Sammlungen bearbeiten oder zurückgeben. Sie enthält polymorphe Algorithmen, die Sammlungen bearbeiten, „Wrapper“, die eine neue Sammlung zurückgeben, die von einer bestimmten Sammlung unterstützt wird, und einige andere Kleinigkeiten.

Die Methoden dieser Klasse lösen alle eine NullPointerException aus, wenn die ihnen bereitgestellten Sammlungen oder Klassenobjekte null sind

2、List

API----Diese Klasse besteht ausschließlich aus statischen Methoden, die Sammlungen bearbeiten oder zurückgeben. Sie enthält polymorphe Algorithmen, die Sammlungen bearbeiten, „Wrapper“, die eine neue Sammlung zurückgeben, die von einer bestimmten Sammlung unterstützt wird, und einige andere Vorteile und endet.

Die Methoden dieser Klasse lösen alle eine NullPointerException aus, wenn die ihnen bereitgestellten Sammlungen oder Klassenobjekte null sind.

Liste ist geordnete Sammlung. Verwenden Sie diese Schnittstelle, um die Einfügeposition jedes Elements genau zu steuern. Benutzer können den Index (die Position des Elements in der Liste, ähnlich dem Array-Index) verwenden, um auf die Elemente in der Liste zuzugreifen, was Java-Arrays ähnelt.

3. Vektor

API---- Die Vector-Klasse implementiert ein erweiterbares Array von Objekten. Sie enthält wie ein Array Komponenten, auf die über einen ganzzahligen Index zugegriffen werden kann. Die Größe eines Vector kann jedoch nach Bedarf vergrößert oder verkleinert werden, um das Hinzufügen und Entfernen von Elementen zu ermöglichen DasVector wurde erstellt, daher ist es schwierig, die Einschränkungen von Arrays zu vermeiden, und gleichzeitig kann die Leistung Arrays nicht überschreiten. Deshalb sollten wir, wo möglich, mehr Arrays verwenden. Ein weiterer sehr wichtiger Punkt ist, dass Vector Thread-synchronisiert (synchronisiert) ist, weshalb Vector und ArrayList ein wichtiger Unterschied.


4. ArrayList

API----Resizable-Array-Implementierung des

List-Schnittstelle. Implementiert alle optionalen Listenoperationen und lässt alle Elemente zu, einschließlich null

. Zusätzlich zur Implementierung der

List

-Schnittstelle stellt diese Klasse Methoden zur Manipulation bereit die Größe des Arrays, das intern zum Speichern der Liste verwendet wird. (Diese Klasse entspricht in etwa

Vector, außer dass sie nicht synchronisiert ist.)

Wie Vector handelt es sich um eine verknüpfte Liste basierend auf einem Array, der Unterschied besteht jedoch darin, dass ArrayList nicht synchronisiert ist. Daher ist es in Bezug auf die Leistung besser als Vector, aber wenn es in einer Multithread-Umgebung ausgeführt wird, müssen Sie die Synchronisierung der Threads selbst verwalten.

5. LinkedList

API----Verknüpfte Listenimplementierung der List-Schnittstelle implementiert alle optionalen Listenoperationen und lässt alle Elemente zu (einschließlichnull). Zusätzlich zur Implementierung derList-Schnittstelle Die LinkedList-Klasse stellt einheitlich benannte Methoden zumAbrufen, Entfernen undEinfügen eines Elements am Anfang und Ende der Liste bereit. Diese Operationen ermöglichen verknüpfte Listen als Stapel, Warteschlange, oderdoppelendige Warteschlange.

LinkedList unterscheidet sich von den beiden vorherigen Listen dadurch, dass es nicht auf Arrays basiert und daher nicht durch die Array-Leistung eingeschränkt ist.
Jeder Knoten (Knoten) enthält zwei Aspekte des Inhalts:
1. Die Daten des Knotens selbst; Knoteninformationen (nextNode).
Wenn Sie also Aktionen zu LinkedList hinzufügen und löschen, ist es nicht erforderlich, viele Daten wie bei Array-basierten ArrayList zu verschieben. Dies kann durch einfaches Ändern der relevanten Informationen von nextNode erreicht werden. Dies ist der Vorteil von LinkedList.

Listenzusammenfassung:

Alle Listen können nur Tabellen enthalten, die aus einem einzelnen Objekt unterschiedlichen Typs bestehen, keine Schlüssel-Wert-Paare. Zum Beispiel: [ tom,1,c ]
Alle Listen können die gleichen Elemente haben, zum Beispiel kann Vector [ tom haben ,koo,too,koo ]
Alle Listen können Nullelemente haben, wie zum Beispiel [ tom,null,1 ]
Array-basierte Liste (Vector, ArrayList) eignet sich für Abfragen, während LinkedList für Hinzufügungs- und Löschvorgänge geeignet ist

6. Set (Schnittstelle) API-----Eine Sammlung, die keine doppelten Elemente enthält

und

so dass

und höchstens ein Nullelement, diese Schnittstelle modelliert die mathematische

Mengee1Abstraktion e2e1.equals(e2)Menge ist eine Sammlung

7. HashSet

API-----Diese Klasse implementiert die Set-Schnittstelle, unterstützt durch eine Hash-Tabelle (eigentlich eineHashMap-Instanz). Es gibt keine Garantien hinsichtlich der Iteration Die Reihenfolge der Menge ist insbesondere nicht gewährleistet, dass die Reihenfolge im Laufe der Zeit konstant bleibt. Obwohl Set und List beide die Collection-Schnittstelle implementieren, ist dies der Fall ganz anders. Die Liste basiert grundsätzlich auf Array. Aber Set wird auf Basis von HashMap implementiert. Dies ist der grundlegende Unterschied zwischen Set und List. Die Speichermethode von HashSet besteht darin, den Schlüssel in HashMap als entsprechendes Speicherelement von Set zu verwenden. schau mal Die Implementierung der Methode add(Object obj) von HashSet ist auf einen Blick ersichtlich.

8. LinkedHashSet
API----Verknüpfte Listenimplementierung der
Liste

Schnittstelle. Implementiert alle optionalen Listenoperationen und lässt alle Elemente zu (einschließlich

null). Zusätzlich zur Implementierung derList

-Schnittstelle bietet die Klasse

LinkedList einheitlich benannte Methoden um ein Element am Anfang und Ende der Liste zuabzurufen, zu entfernen undeinzufügen. Diese Operationen ermöglichen die Verwendung verknüpfter Listen als Stapel, Warteschlange usw. oderdoppelendige Warteschlange. Eine Unterklasse von HashSet, einer verknüpften Liste.


9. SortedSet

API---A

, das außerdem eine

Gesamtordnung für seine Elemente bereitstellt. Die Elemente werden in ihrer natürlichen Reihenfolge oder nach einem geordnet, der normalerweise zum Zeitpunkt der Erstellung des sortierten Satzes bereitgestellt wird die Menge in aufsteigender Elementreihenfolge. (Diese Schnittstelle ist das Mengenanalogon von

Set Ordered Set, Comparator wird durch SortedMap implementiert. SortedMap

Zusammenfassung festlegen:

(1)Die Grundlage der Set-Implementierung ist Map (HashMap) (2)

Die Elemente in Set können nicht wiederholt werden, wenn Sie add(Object obj)-Methode zum Hinzufügen eines vorhandenen Objekts überschreibt das vorherige Objekt

-------------Karte----------------

Karte ist ein Schlüsselobjekt, das einem Container zugeordnet ist mit einem Wertobjekt, und ein Wertobjekt kann eine Karte usw. sein, wodurch eine mehrstufige Karte entsteht. Bei Schlüsselobjekten wie Set dürfen die Schlüsselobjekte in einem Map-Container nicht wiederholt werden. Dies dient dazu, die Konsistenz der Suchergebnisse zu gewährleisten. Wenn es zwei gleiche Schlüsselobjekte gibt, möchten Sie den Wert erhalten Objekt, das diesem Schlüsselobjekt entspricht. Möglicherweise ist das, was Sie erhalten, nicht der von Ihnen gedachte Wert, und das Ergebnis ist Verwirrung. Daher ist die Einzigartigkeit des Schlüssels sehr wichtig und entspricht der Natur das Set. Natürlich kann sich während der Verwendung das einem bestimmten Schlüssel entsprechende Wertobjekt ändern. In diesem Fall entspricht das zuletzt geänderte Wertobjekt dem Schlüssel. Es gibt keine Eindeutigkeitsanforderung für Wertobjekte. Sie können einem Wertobjekt problemlos eine beliebige Anzahl von Schlüsseln zuordnen (dies kann jedoch zu Unannehmlichkeiten bei Ihrer Verwendung führen. Sie wissen nicht, was Sie erhalten. Ist das entsprechende Wertobjekt?). Schlüssel).

1. HashMap

API----Hash-tabellenbasierte Implementierung derMap-Schnittstelle. Diese Implementierung stellt alle optionalen Kartenoperationen bereit und erlaubtnull Werte und der Schlüssel null (Die Klasse HashMap entspricht in etwa der Klasse Hashtable, außer dass sie unsynchronisiert ist und Nullen zulässt.) Diese Klasse macht keine Garantien insbesondere hinsichtlich der Reihenfolge der Karte; Die Reihenfolge bleibt im Laufe der Zeit konstant.

2. TreeMap

API----Eine auf einem Rot-Schwarz-Baum basierendeNavigableMap-Implementierung .Die Karte ist sortiert nach abhängig vom verwendeten Konstruktor Comparator

TreeMap speichert Schlüssel in der richtigen Reihenfolge. Es verfügt über einige erweiterte Methoden wie firstKey(), lastKey() usw. Sie können auch einen Bereich von TreeMap angeben, um dessen Unterkarte zu erhalten.
Die Zuordnung zwischen Schlüsseln und Werten ist sehr einfach. Verwenden Sie die Methode put(Object key, Object value), um einen Schlüssel einem Wertobjekt zuzuordnen. Verwenden Sie get(Object key), um das diesem Schlüsselobjekt entsprechende Wertobjekt abzurufen.


------------Beschreibung----------

1. Unterschiede zwischen mehreren häufig verwendeten Kategorien
1. ArrayList: Einzelnes Element, hohe Effizienz, wird hauptsächlich für Abfragen verwendet
2. Vektor: Einzelnes Element, Thread-sicher, wird hauptsächlich für Abfragen verwendet
3. LinkedList: Einzelnes Element, das hauptsächlich zum Einfügen und Löschen verwendet wird
4. HashMap: Die Elemente sind paarweise und die Elemente können leer sein
5. HashTable: Elemente sind gepaart, threadsicher und Elemente können nicht null sein 2. Vector, ArrayList und LinkedList
In den meisten Fällen ArrayList ist in Bezug auf die Leistung am besten, aber wenn es um Sammlungen geht, bietet LinkedList eine bessere Leistung, wenn die darin enthaltenen Elemente häufig eingefügt und gelöscht werden müssen, aber die Leistung der drei ist nicht so gut wie die von Arrays. Darüber hinaus ist Vector threadsynchronisiert. Also:

Wenn Sie ein Array verwenden können (Elementtyp ist fest, Array-Länge ist fest), versuchen Sie bitte, ein Array anstelle von List zu verwenden ;

Wenn es keine häufigen Lösch- und Einfügevorgänge gibt und keine Notwendigkeit besteht, Multithreading-Probleme zu berücksichtigen, wird ArrayList bevorzugt

Bei Verwendung unter Multithread-Bedingungen können Sie Vector
Wenn Sie häufig löschen und einfügen müssen, ist LinkedList praktisch.
Wenn Sie nichts wissen, ist die Verwendung nicht verkehrt ArrayList.
3. Sammlungen und Arrays
in Es gibt zwei Klassen im Java-Collection-Klassen-Framework namens Collections (Achtung, nicht Collection!) und Arrays. Dies sind leistungsstarke Tools in JCF, die Anfänger jedoch häufig ignorieren. Laut JCF-Dokument stellen diese beiden Klassen Wrapper-Implementierungen (Wrapper-Implementierungen), Datenstrukturalgorithmen und Array-bezogene Anwendungen bereit.
Ich bin sicher, dass Sie die oben erwähnten klassischen Algorithmen wie „Halbsuche“ und „Sortieren“ nicht vergessen werden von statischen Methoden helfen uns, diese lästigen Aufgaben in Datenstrukturklassen einfach zu erledigen:
binarySearch: binäre Suche.
sortieren: Sortieren, hier ist eine Methode ähnlich der schnellen Sortierung, die Effizienz ist immer noch ist O(n * log n), ist aber eine stabile Sortiermethode. umgekehrt: Betreiben Sie eine lineare Tabelle in umgekehrter Reihenfolge. Dies ist eine klassische Frage zur Datenstruktur in der Vergangenheit!
drehen: „Rotieren“ Sie den linearen Tisch um ein bestimmtes Element als Achse.
Swap: Vertauschen Sie die Positionen zweier Elemente in einer linearen Liste.

Sammlungen haben auch eine wichtige Funktion ist der „Wrapper“, der einige Methoden zum Konvertieren einer Sammlung in eine spezielle Sammlung bereitstellt, wie folgt:
unmodifiableXXX: In eine schreibgeschützte Sammlung konvertieren, wobei XXX sechs grundlegende Sammlungsschnittstellen darstellt: Collection, List, Map, Set, SortedMap und SortedSet. Wenn Sie eine schreibgeschützte Sammlung einfügen oder löschen, wird eine UnsupportedOperationException ausgelöst.
synchronizedXXX: In synchronisierte Sammlung konvertieren.
Singleton: Erstellen Sie eine Sammlung mit nur einem Element. Hier generiert Singleton einen einzelnen Elementsatz ,
singletonList und singletonMap generieren jeweils eine Einzelelementliste und -karte.
Leerer Satz: dargestellt durch die statischen Eigenschaften EMPTY_SET, EMPTY_LIST und EMPTY_MAP der Sammlungen.

Das obige ist der detaillierte Inhalt vonFassen Sie mehrere häufig verwendete Datenstrukturen in Java zusammen und teilen Sie sie. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!

Stellungnahme:
Der Inhalt dieses Artikels wird freiwillig von Internetnutzern beigesteuert und das Urheberrecht liegt beim ursprünglichen Autor. Diese Website übernimmt keine entsprechende rechtliche Verantwortung. Wenn Sie Inhalte finden, bei denen der Verdacht eines Plagiats oder einer Rechtsverletzung besteht, wenden Sie sich bitte an admin@php.cn