Heim  >  Artikel  >  Java  >  Was sind die Java-Datenstrukturen?

Was sind die Java-Datenstrukturen?

王林
王林Original
2021-04-12 14:34:5121886Durchsuche

Java-Datenstrukturen umfassen: 1. Vector; 4. LinkedList;

Was sind die Java-Datenstrukturen?

Die Betriebsumgebung dieses Artikels: Windows 10-System, Java 1.8, Thinkpad T480-Computer.

In Java gibt es mehrere häufig verwendete Datenstrukturen, die hauptsächlich in zwei Hauptschnittstellen unterteilt sind: Sammlung und Karte (die Schnittstelle stellt nur Methoden und keine Implementierung bereit), und die letztendlich im Programm verwendete Datenstruktur ist die Datenstruktur von dieser Schnittstellenart geerbt.

Collection---->Collections   
Map----->SortedMap------>TreeMap          Map------>HashMap
Collection---->List----->(Vector \ ArryList \ LinkedList)
Collection---->Set------>(HashSet \ LinkedHashSet \ SortedSet)

List (Schnittstelle)

List ist eine geordnete Sammlung. Mithilfe dieser Schnittstelle kann die Einfügeposition jedes Elements genau gesteuert werden. 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.

Vector

Array-basierte Liste kapselt tatsächlich einige Funktionen, die Arrays für uns nicht nutzen können. Daher ist es schwierig, die Einschränkungen von Arrays zu vermeiden, und gleichzeitig kann ihre Leistung die von Arrays nicht überschreiten. Deshalb sollten wir, wo möglich, mehr Arrays verwenden. Ein weiterer sehr wichtiger Punkt ist, dass Vector threadsynchronisiert (synchronisiert) ist, was auch ein wichtiger Unterschied zwischen Vector und ArrayList ist.

ArrayList

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.

LinkedList

LinkedList unterscheidet sich von den beiden vorherigen Listen. Es basiert nicht auf Arrays und ist daher nicht durch die Array-Leistung eingeschränkt.

Jeder Knoten (Knoten) enthält zwei Inhaltsaspekte:

1 Die Daten des Knotens selbst (Daten);

2.

Wenn Sie also Aktionen zu LinkedList hinzufügen oder löschen, müssen Sie nicht viele Daten verschieben wie bei Array-basierten ArrayList. Dies kann durch einfaches Ändern der relevanten Informationen von nextNode erreicht werden. Dies ist der Vorteil von LinkedList.

Listenzusammenfassung

Alle Listen können nur eine Tabelle enthalten, die aus einem einzelnen Objekt unterschiedlichen Typs besteht, nicht aus Schlüssel-Wert-Paaren. Zum Beispiel: [tom,1,c]

Alle Listen können die gleichen Elemente haben, zum Beispiel kann Vector [tom,koo,too,koo] haben

Alle Listen können Nullelemente haben, zum Beispiel [tom, null ,1 ]

Array-basierte Liste (Vector, ArrayList) eignet sich für Abfragen, während LinkedList für Additions- und Löschvorgänge geeignet ist

Set (Schnittstelle)

Set ist eine Sammlung, die keine wiederholten Elemente enthält

HashSet

Obwohl Set und List identisch sind, implementieren beide die Collection-Schnittstelle, ihre Implementierungsmethoden sind jedoch sehr unterschiedlich. 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. Es wird auf einen Blick klar, wenn Sie sich die Implementierung der Methode add(Object obj) von HashSet ansehen.

LinkedHashSet

Eine Unterklasse von HashSet, einer verknüpften Liste.

SortedSet

Ordered Set wird über SortedMap implementiert.

Map (Schnittstelle)

Map ist ein Container, der Schlüsselobjekte und Wertobjekte verknüpft, und ein Wertobjekt kann eine Karte usw. sein und so eine mehrstufige Zuordnung bilden. 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 zwei Schlüsselobjekte identisch sind, 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 Wertobjekt ändern, das einem bestimmten Schlüssel entspricht. 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).

(Kostenloses Teilen von Video-Tutorials: Java-Video-Tutorial)

HashMap

Implementierung der Kartenschnittstelle basierend auf einer Hash-Tabelle. Diese Implementierung stellt alle optionalen Zuordnungsvorgänge bereit und ermöglicht Nullwerte und Nullschlüssel. (Die HashMap-Klasse ähnelt weitgehend einer Hashtable, außer dass sie nicht synchronisiert ist und Null zulässt.) Diese Klasse garantiert nicht die Reihenfolge der Karte und insbesondere nicht, dass die Reihenfolge unveränderlich ist. Darüber hinaus ist HashMap nicht threadsicher, was bedeutet, dass es in einer Multithread-Umgebung zu Problemen kommen kann, während Hashtable threadsicher ist.

TreeMap

TreeMap speichert Schlüssel der Reihe nach,

HashTable

(1) Hashtable ist eine Hash-Tabelle und der darin gespeicherte Inhalt ist eine Schlüssel-Wert-Zuordnung.

(2) Hashtable erbt von Dictionary und implementiert die Schnittstellen Map, Cloneable und java.io.Serializable.

(3) Die Funktionen von Hashtable sind alle synchron, was bedeutet, dass es threadsicher ist. Weder sein Schlüssel noch sein Wert dürfen null sein.

Unterschiede zwischen mehreren häufig verwendeten Klassen

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, wird hauptsächlich zum Einfügen und Löschen verwendet

4. HashMap: Elemente sind paarweise und Elemente können leer sein

5. HashTable: Elemente sind paarweise, threadsicher, Elemente dürfen nicht leer sein

Vector, ArrayList und LinkedList

In den meisten Fällen ist ArrayList hinsichtlich der Leistung am besten, wenn jedoch Elemente in der Sammlung häufig eingefügt und gelöscht werden müssen , LinkedList wird Probleme haben Relativ gute Leistung, aber die Leistung der drei ist nicht so gut wie die von Arrays Darüber hinaus ist Vector Thread-synchronisiert. Also:

Wenn Sie ein Array verwenden können (Elementtyp ist fest, Array-Länge ist fest), versuchen Sie bitte, ein Array anstelle einer Liste zu verwenden.

Wenn es keine häufigen Lösch- und Einfügevorgänge gibt und Sie dies nicht benötigen Um Multithreading-Probleme zu berücksichtigen, geben Sie ArrayList den Vorrang.

Wenn Sie es unter Multithread-Bedingungen verwenden, können Sie Vector in Betracht ziehen. Wenn Sie häufig löschen und einfügen müssen, ist LinkedList praktisch Ich weiß nichts, es ist nichts Falsches daran, ArrayList zu verwenden.

Stack

Stack ist eine spezielle lineare Liste, die nur an einem Ende eingefügt und gelöscht werden kann. Es speichert Daten nach dem First-In-Last-Out-Prinzip. Die Daten, die zuerst eingegeben werden, werden an den unteren Rand des Stapels verschoben, und die letzten Daten befinden sich oben im Stapel von der Spitze des Stapels (die letzten Daten werden zuerst ausgelesen).

Warteschlange

Eine spezielle lineare Tabelle, die nur Löschvorgänge am vorderen Ende der Tabelle (vorne) und Einfügevorgänge am hinteren Ende (hinten) der Tabelle zulässt. Das Ende, das den Einfügevorgang ausführt, wird als Ende der Warteschlange bezeichnet, und das Ende, das den Löschvorgang ausführt, wird als Kopf der Warteschlange bezeichnet. Wenn die Warteschlange keine Elemente enthält, spricht man von einer leeren Warteschlange.

Array

Bei der Programmierung werden zur Vereinfachung der Verarbeitung mehrere Variablen desselben Typs in einer geordneten Form organisiert. Eine Sammlung dieser ähnlichen Datenelemente, die der Reihe nach angeordnet sind, wird als Array bezeichnet. In der Sprache C sind Arrays konstruierte Datentypen. Ein Array kann in mehrere Array-Elemente zerlegt werden, und diese Array-Elemente können Basisdatentypen oder konstruierte Typen sein. Daher können Arrays entsprechend der Art der Array-Elemente in verschiedene Kategorien unterteilt werden, z. B. numerische Arrays, Zeichen-Arrays, Zeiger-Arrays und Struktur-Arrays.

Verknüpfte Liste

Eine nicht kontinuierliche und nicht sequentielle Speicherstruktur auf physischen Speichereinheiten. Die logische Reihenfolge der Datenelemente wird durch die Zeigerverknüpfungsreihenfolge in der verknüpften Liste realisiert.

Eine verknüpfte Liste besteht aus einer Reihe von Knoten (jedes Element in der verknüpften Liste wird als Knoten bezeichnet), und Knoten können zur Laufzeit dynamisch generiert werden. Jeder Knoten besteht aus zwei Teilen:

Einer ist das Datenfeld, in dem Datenelemente gespeichert werden, und der andere ist das Zeigerfeld, in dem die Adresse des nächsten Knotens gespeichert wird.

Baum

Ein Baum ist eine endliche Menge K, die n (n>0) Knoten enthält, und eine Beziehung N ist in K definiert. N erfüllt die folgenden Bedingungen:

(1) Es gibt und gibt nur einen Knoten k0, der keinen Vorgänger für die Beziehung N hat, wird Wurzelknoten des Baums genannt. Wird als Wurzel bezeichnet

(2) Mit Ausnahme von K0 hat und hat jeder Knoten in k nur einen Vorgänger für die Beziehung N.

(3) Jeder Knoten in K kann m Nachfolger (m>=0) für die Beziehung N haben.

Heap

In der Informatik ist ein Heap eine spezielle Baumdatenstruktur, jeder Knoten hat einen Wert. Normalerweise bezieht sich das, was wir als Datenstruktur eines Heaps bezeichnen, auf einen binären Heap. Das Merkmal eines Heaps besteht darin, dass der Wurzelknoten den kleinsten (oder größten) Wert hat und die beiden Teilbäume des Wurzelknotens ebenfalls ein Heap sind.

Hash-Tabelle

Wenn in der Struktur ein Datensatz mit dem Schlüsselwort K vorhanden ist, muss dieser sich am Speicherort von f(K) befinden. Somit können die gesuchten Datensätze ohne Vergleich direkt ermittelt werden. Diese Korrespondenz f wird als Hash-Funktion bezeichnet, und die auf dieser Idee basierende Tabelle ist eine Hash-Tabelle.

Verwandte Empfehlungen:

Fragen und Antworten zu Java-Interviews

Das obige ist der detaillierte Inhalt vonWas sind die Java-Datenstrukturen?. 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