Mechanismus und Merkmale der in Java häufig verwendeten Collection-Implementierungsklasse

Ich habe einen Artikel ["Bedeutung der aus der Java-Sammlung gelernten Schnittstelle"] geschrieben (http://qiita.com/frost_star/items/14a12d64ccbe85a8ac3f). Da sich dieser Artikel auf die Collection-Oberfläche konzentrierte, konzentrieren wir uns dieses Mal auf die häufig verwendeten Implementierungsklassen und sprechen über die interne Implementierung, Funktionen und Verwendung jeder Implementierungsklasse.

Die Implementierungsklasse wurde diesmal erklärt

Dies ist eine Collection-Klasse, die Sie wahrscheinlich häufig verwenden werden.

• ArrayList
• LinkedList
• HashSet
• HashMap

HashMap ist keine Sammlung, sondern eine Implementierungsklasse von Map. Da es jedoch häufig verwendet wird und in hohem Maße mit HashSet zusammenhängt, werde ich es zusammen mit HashSet erläutern.

Klassen Diagramm

Die Rolle der Schnittstelle (Klicken Sie hier für Details (http://qiita.com/frost_star/items/14a12d64ccbe85a8ac3f))

ArrayList ~ Liste nach Array ~

ArrayList ist, wie der Name schon sagt, eine Implementierung von List by Array. Es verfügt intern über ein Array und speichert, referenziert und fügt Daten in das Array ein. Um die Eigenschaften von ArrayList zu kennen, ist es daher erforderlich, die Eigenschaften des Arrays zu kennen.

Was ist überhaupt ein Array?

Ein Array reserviert einen zusammenhängenden Bereich im Speicher. Das Beste daran ist, dass Indizes mit hoher Geschwindigkeit auf sie verweisen können. Da die Bereiche fortlaufend sind, können Sie die Adresse, auf die Sie sich beziehen möchten, anhand der folgenden Formel finden, sofern Sie die Startadresse, den Index und die Datengröße pro Element kennen.

Adresse, auf die verwiesen werden soll=Startadresse+Index x Datengröße pro Eins

Interne Verarbeitung von ArrayList

Da das Array einen solchen kontinuierlichen Bereich sichern muss, kann es nicht von der ursprünglich festgelegten Anzahl von Elementen geändert werden. Mit ArrayList können Sie jedoch Elemente dynamisch hinzufügen. ArrayList ordnet ein Array automatisch neu zu, wenn Sie Elemente hinzufügen und keine Arrays mehr haben. Das erneute Sichern ist einfach, aber in Wirklichkeit ist es ein sehr schwerer Prozess, da ein neues Array mit der 1,5-fachen Anzahl von Elementen als Originalgröße verarbeitet und die Daten aus dem ursprünglichen Array kopiert werden. Werden. Es wird gesagt, dass es besser ist, die Anfangskapazität (Argument des Konstruktors) in ArrayList zu bestimmen, da dies die Häufigkeit der Ausführung dieses Neuzuweisungsprozesses verringert, indem die Größe des Arrays bestimmt wird, das zuerst zugewiesen werden soll.

Außerdem sind Arrays sehr anfällig für das Einfügen. Dies liegt daran, dass der Bereich, in dem Daten gespeichert sind, festgelegt ist, sodass das Verschieben des Standorts nicht durchgeführt werden kann. In ArrayList wird der Prozess des Einfügens von Daten an eine beliebige Stelle durch die Methode "add" implementiert, aber diese interne Methode ordnet auch das Array neu zu, und die Daten nach der Einfügeposition werden durch Verschieben des Index und Kopieren eingefügt. Wir arbeiten daran, Platz zu schaffen.

LinkedList ~ Liste nach linearer Liste ~

Haben Sie jemals von einer Datenstruktur gehört, die als lineare Liste bezeichnet wird? LinkedList ist eine Implementierung von List, die auf der Struktur einer linearen Liste basiert.

Was ist eine lineare Liste?

Eine lineare Liste ist eine Datenstruktur, die Daten und Verknüpfungen (Verweise auf das nächste Element) als ein Objekt (Knoten) behandelt und Datenketten durch Verketten der Knoten verarbeiten kann.

Der Vorteil dieser Datenstruktur besteht darin, dass Sie auf die Elemente zugreifen können, indem Sie den Links in jedem Knoten folgen, solange Sie die Wurzel kennen (Verweis auf den ersten Knoten). Daher muss nicht jeder Knoten in einem zusammenhängenden Bereich wie einem Array vorhanden sein. Außerdem müssen Sie beim Einfügen von Daten nur die Referenzen der Knoten vorher und nachher ändern, sodass Sie keinen umfangreichen Kopiervorgang wie ArrayList benötigen.

Interne Verarbeitung von LinkedList

Der Nachteil von linearen Listen ist der langsame Direktzugriff. Um beispielsweise auf das 2. Element zuzugreifen, folgen Sie dem Link von der Wurzel aus halbwiederholend, z. B. [Wurzel] -> [0. Element] -> [1. Element] -> [2. Element]. Ich muss gehen. Um den Direktzugriff so weit wie möglich zu beschleunigen, haben wir in LinkedList Möglichkeiten entwickelt, Links bidirektional zu gestalten und einen Verweis auf das letzte Element beizubehalten. Je mehr Elemente vorhanden sind, desto langsamer ist der Direktzugriff unvermeidlich.

Da jeder Knoten zusätzlich zu den Daten eine Referenz als Feld hat, verwendet er mehr Speicher als eine ArrayList mit der gleichen Anzahl von Elementen.

HashSet ~ Mit dem Hashwert ~ festlegen

HashSet ist im Gegensatz zu den beiden vorherigen Listen eine Implementierungsklasse von Set. Das heißt, es erlaubt keine doppelten Elemente und keinen wahlfreien Zugriff. Außerdem behält HashSet die Reihenfolge nicht bei.

Duplikate nicht zulassen bedeutet, dass Sie beim Hinzufügen eines Elements feststellen müssen, ob das Element bereits im Set vorhanden ist. HashSet verwendet Arrays, lineare Listen und Hash-Werte, um eine schnelle Existenzüberprüfung zu erreichen.

Was ist ein Hashwert?

Der Hash-Wert ist ein Wert, der aus den Originaldaten durch Berechnung auf der Grundlage einer bestimmten Formel berechnet wird. Der gleiche Hash-Wert kann aus den gleichen Daten berechnet werden, ist jedoch so ausgelegt, dass sich die Werte erheblich unterscheiden, wenn sich die Daten geringfügig unterscheiden. Auch wenn es irreversibel ist und der Hash-Wert aus den Daten berechnet werden kann, können die Daten nicht aus dem Hash-Wert wiederhergestellt werden. Der Hash-Wert selbst wird in der Welt der Informationsverarbeitung häufig verwendet, z. B. bei der Authentifizierung, Gültigkeitsprüfung und Verschlüsselung.

Hash-Wert in Java

Der Hash-Wert in Java ist ein Wert zum Identifizieren einer Instanz und eine Ganzzahl vom Typ int, die mit der Methode "hashCode" berechnet wird. Die hashCode-Methode wird mit dem Objekttyp definiert. Basierend auf dem Merkmal, dass "derselbe Hashwert aus den gleichen Daten des Hashwerts berechnet werden kann", muss derselbe Hashwert zwischen Fällen zurückgegeben werden, in denen die Methode "equals" true zurückgibt, und umgekehrt, wenn die Daten unterschiedlich sind, sind sie so weit wie möglich gleich. Es sollte kein Wert sein.

Interne Verarbeitung von HashSet

HashSet realisiert eine schnelle Existenzbestätigung, indem dieser Hashwert gut genutzt wird. HashSet reserviert ein Array der Größe s, wenn es instanziiert wird. Beim Speichern einer Instanz "e" findet HashSet zuerst den Hashwert mit "e.hashCode ()" und berechnet dann, wo er gespeichert werden soll. Suchen Sie den Rest (Teilungsrest) von e.hashCode () unds und speichern Sie e an dieser Stelle.

array[ e.hashCode() % s ] = e;

Da der Speicherort aus "e.hashCode ()% s" berechnet wird, ist es nicht erforderlich, das Array einzeln zu durchsuchen, wenn die Existenz überprüft wird, und der Hash-Wert der angegebenen Instanz wird berechnet und die Instanz ist vorhanden. Sie können die Existenz bestätigen, indem Sie prüfen, ob dies der Fall ist.

Im Falle einer Kollision

Das ist nur eine ideale Theorie. Tatsächlich ist die Größe des Arrays "s" im Vergleich zum Hash-Wert klein, sodass das Phänomen auftritt, dass sich bereits Daten an dem Ort befinden, an dem Sie versucht haben, sie zu speichern. Dies wird als Kollision bezeichnet. Im Konfliktfall speichert HashSet Daten in einer Datenstruktur mit Links zum nächsten Element wie eine lineare Liste, wenn Daten gespeichert werden. Im Falle einer Kollision werden die Daten dann als nächstes Element nach dem vorhandenen Element verbunden. Auf diese Weise können Sie die Existenz überprüfen, indem Sie nur nach Gruppen suchen, die denselben Wert wie "e.hashCode ()% s" haben, auch wenn es sich nicht um eine einzelne Referenz handelt.

Größe ändern

Je mehr Daten Sie haben, desto wahrscheinlicher ist es, dass Sie kollidieren. Wenn Sie beispielsweise 11 Daten speichern, wenn s = 10 ist, kommt es definitiv zu einer Kollision (dem Taubennestprinzip). Wenn daher die Anzahl der Daten zunimmt, wird das Array mit einer großen Kapazität neu zugewiesen und die Daten werden erneut eingefügt. Das erneute Einfügen von Daten ist hier keine einfache Kopie, aber die Datenstruktur wird nicht unterbrochen, da das erneute Einfügen von Daten durchgeführt wird, damit die Korrespondenz zwischen dem Array-Index und "e.hashCode ()% s" nicht unterbrochen wird.

hashCode überschreiben

HashSet bestimmt den Speicherort basierend auf dem Wert von "hashCode". Daher hängt die Leistung des Ausdrucks "hashCode" direkt mit der Kollisionswahrscheinlichkeit des HashSet zusammen. Im Extremfall tritt bei jeder Speicherung von Daten ein Konflikt auf, wenn der Inhalt von "hashCode" so verarbeitet wird, dass immer eine Konstante wie "return 0;" zurückgegeben wird, und die Suchleistung ist geringer als bei LinkedList. Daher ist es wichtig, die entsprechende hashCode-Methode für die Klasse des zu speichernden Elements zu überschreiben. Es besteht jedoch eine hohe Wahrscheinlichkeit eines Konflikts mit Oreore hashCode. Am besten verwenden Sie die Methode "Objects.hashCode".

Objects.hashCode(Feld 1,Feld 2,Feld 3);

Da das Argument ein variables Argument ist, können Sie Daten mehrerer Objekttypen übergeben. Da der endgültige Hashwert jedoch unter Verwendung des durch hashCode jedes Felds erhaltenen Hashwerts berechnet wird, muss die hashCode-Methode auch in jeder Feldklasse überschrieben werden.

HashSet und HashMap

Bisher haben wir über die interne Implementierung von HashSet gesprochen, aber es ist tatsächlich eine Lüge. Wie ich in Ein anderer Artikel geschrieben habe, wird die interne Implementierung von HashSet tatsächlich von HashMap realisiert. Daher war die interne Implementierungsgeschichte, über die wir bisher gesprochen haben, tatsächlich die interne Implementierung von HashMap. Da die Implementierung der internen Verarbeitung jedoch nur von HashMap abhängt, ist das Verhalten für beide gleich.

Die Geschichte von HashMap

Wie bei HashMap ist HashMap eine Implementierungsklasse von Map, die Werte in zwei Datenpaaren enthält, Key und Value. Der Schlüssel entspricht dem zuvor erläuterten Datenteil des HashSet. Da die Daten durch den Hashwert der Schlüsselinstanz gespeichert werden, ist es möglich, die Daten vom Schlüssel mit hoher Geschwindigkeit zu suchen. Der Wert ist einfach der mit dem Schlüssel verknüpfte Wert und wird mit dem Schlüssel gespeichert. In HashSet wird durch Festlegen eines statischen Werts als Wert die Verwendung von HashMap implementiert, ohne dass zusätzlicher Speicher benötigt wird.

Vergleich jeder Implementierungsklasse

Lassen Sie uns zusammenfassend die Leistung jeder Implementierungsklasse in der Reihenfolge der Notation vergleichen. Wenn Sie die Auftragsnotation nicht verstehen, ist * O * (n) langsamer als * O * (1). Schauen Sie also bitte vorbei.

Leistungsvergleich

*: Die Größe kann geändert werden

Zum Vergleich sehen Sie die Merkmale jeder Implementierungsklasse. Beispiel: LinkedList, wenn viele Einfügungen vorhanden sind, ArrayList, wenn viele zufällige Zugriffe vorhanden sind usw. Welche Klasse geeignet ist, hängt vom Verarbeitungsinhalt ab. Wählen Sie also eine geeignete Implementierungsklasse aus.