Wir wissen, dass eine Hash -Tabelle eine sehr effiziente Datenstruktur ist, und ein hervorragendes Design der Hash -Funktion kann die Ergänzung, Löschung, Änderung und Suchvorgänge auf dem O (1) -Pegel erreichen. Java bietet uns eine vorgefertigte Hash-Struktur, dh die Hashmap-Klasse. Im vorherigen Artikel habe ich die HashMap-Klasse vorgestellt und wusste, dass alle ihre Methoden nicht synchronisiert wurden, so dass sie in einer Umgebung mit mehreren Threaden nicht sicher ist. Zu diesem Zweck bietet Java uns eine andere Hashtable-Klasse, die sehr einfach und grob bei der Behandlung von Multi-Thread-Synchronisation ist, dh alle seine Methoden mit dem synchronisierten Schlüsselwort basierend auf HashMap zu sperren. Obwohl diese Methode einfach ist, führt sie zu einem Problem, dh nur ein Thread kann die Hash -Tabelle gleichzeitig bedienen. Auch wenn diese Themen nur Lesen von Vorgängen sind, müssen sie in der Warteschlange gestellt werden, was die Leistung in hoch wettbewerbsfähigen Umgebungen mit mehreren Threaden stark beeinflusst. Die in diesem Artikel eingeführte Concurenthashmap besteht darin, dieses Problem zu lösen. Es verwendet segmentierte Schlösser, um die Schlösser fein zu körnern, damit mehrere Fäden die Hash-Tabelle gleichzeitig bedienen können, was die Leistung erheblich verbessert. Die folgende Abbildung ist ein schematisches Diagramm seiner inneren Struktur.
1. Welche Mitgliedsvariablen hat Concurrenthashmap?
// Standardinitialisierungskapazität statische endgültige int default_initial_capacity = 16; // Standard -Lastfaktor statische endgültige float default_load_factor = 0,75f; // Standard -Parallelitätsebene statische endgültige int default_concurrency_level Min_segment_table_capacity = 2; // Maximale Anzahl von Segmentschlössern statische endgültige int max_segmente = 1 << 16; // Anzahl der Wiederholungen, bevor statische endgültige int retries_before_lock = 2; // Maskenwert der Segmentschloss endgültige Int -Segmentmask; // Segment -Lock -Array -Schluss -Segment <k, v> [] [] [] [] [] [] [] [] [] [] [] Segment;
Vor dem Lesen dieses Artikels glaube ich, dass die Leser die spezifische Bedeutung und Funktion dieser Mitgliedervariablen nicht verstehen können, aber die Leser werden empfohlen, geduldig zu lesen. Die Rolle dieser Mitgliedsvariablen wird nacheinander in den spezifischen Szenarien später eingeführt. Hier müssen die Leser nur einen vertrauten Blick auf diese Mitgliedervariablen hinterlassen. Es gibt jedoch noch einige Variablen, die wir jetzt wissen müssen. Beispielsweise repräsentiert das Segmentarray den Satz von Segmentschlöstern, die Parallelitätsebene repräsentiert die Anzahl der Segmentschlösser (was auch bedeutet, wie viele Threads gleichzeitig funktionieren können), die Initialisierungskapazität repräsentiert die Kapazität des gesamten Containers und der Ladefaktor repräsentiert die Ebene der vollständigen Containerelemente.
2. Was ist die interne Struktur des Segmentschlosses?
// Segment Sperre statische endgültige Klasse Segment <k, v> erweitert Reentrantlock implementiert serialisierbare {// Maximale Spin -Nummer statische endgültige int max_scan_retries = runTime.getRuntime (). AFFORTEPROCESSORS ()> 1? 64: 1; // HUT TABLE Transient Flüchtige Hashentry <k, v> [] Tabelle; // Gesamtzahl der Elemente Transient Int Count; // Anzahl der Modifikationen transient int modcount; // Element -Schwellenwert -Transienten -Int -Schwelle; // Lastfaktor Final Float LoadFactor; // den folgenden Inhalt weglassen ...}Segment ist eine statische innere Klasse von Concurrenthashmap. Es enthält intern ein Hashentry-Array (Hash-Tabelle) und stellt sicher, dass alle Methoden zum Hinzufügen, Löschen, Ändern und Durchsuchen des Arrays thread-sicher sind. Die spezifische Implementierung wird später erörtert. Alle Vorgänge zum Hinzufügen, Löschen, Ändern und Überprüfen der Concurrenthashmap können dem Segment anvertraut werden. Daher kann die Concurrenthashmap sicherstellen, dass sie in einer Umgebung mit mehreren Threaden sicher ist. Da verschiedene Segmente unterschiedliche Schlösser sind, können Multithreads gleichzeitig verschiedene Segmente bedienen, was bedeutet, dass Multithreads gleichzeitig gleichzeitig arbeiten können, was die Mangel an Hashtable vermeiden und die Leistung erheblich verbessern kann.
3. Was hat Concurrenthashmap initialisiert?
// Core Constructor @SuppressWarnings ("Deaktiviert") public ConcurrentHasHMap (init initialCapacity, float loadfactor, int ConcurrencyLevel) {if (! (LoadFactor> 0) || initialCapacity <0 || ConcurrencyLevel <= 0) {werfen neue illegalargumentException (); } // Stellen Sie sicher, dass die Parallelitätsstufe nicht größer als die Grenze ist, wenn (ConcurrencyLevel> max_segmente) {ConcurrencyLevel = max_segmments; } int sShift = 0; int ssize = 1; // Stellen Sie sicher, dass SSIZE eine Leistung von 2 ist und die engste Zahl größer oder gleich der Parallelitätsniveau (ssize <ConcurrencyLevel) {++ SSHift; ssize << = 1; } // Berechnen Sie den Schaltwert der Segmentschloss this.segmentShift = 32 - SSHIFT; // Berechnen Sie den Maskenwert der Segment -Sperre this.segmentmask = ssize - 1; // Die Gesamtkapazität kann nicht größer sein als der Grenzwert, wenn (initialCapacity> maximum_capacity) {initialCapacity = maximum_capacity; } // Erhalten Sie die anfängliche Kapazität jedes Segmentschloss int c = initialCapacity /ssize; // Die Summe der segmentierten Sperrkapazität ist nicht geringer als die anfängliche Gesamtkapazität, wenn (c * ssize <initialCapacity) {++ C; } int Cap = min_segment_table_capacity; // Stellen Sie sicher, dass CAP eine Leistung von 2 ist und die engste Zahl größer oder gleich C ist, während (Cap <c) {Cap << = 1; } // Erstellen Sie ein neues Segment -Objekt -Template -Segment <K, v> S0 = neues Segment <K, v> (LoadFactor, (int) (Cap * loadFactor), (Hashentry <K, v> []) New Hashentry [Cap]); // Erstellen Sie ein neues Segment -Sperrarray des Segments der angegebenen Größe <k, v> [] ss = (Segment <k, v> []) neues Segment [SSIZE]; // Verwenden Sie Unsicher, um das 0. Element des Array unsicheren zuzuweisen. this.segmente = ss;}Concurrenthashmap verfügt über mehrere Konstruktoren, aber was oben veröffentlicht wird, ist der Kernkonstruktor und andere Konstruktoren, die die Initialisierung durchrufen. Der Kernkonstruktor muss drei Parameter übergeben, nämlich die anfängliche Kapazität, den Belastungsfaktor und die Parallelitätsstufe. Bei früherer Einführung früherer Mitgliedervariablen können wir wissen, dass die Standard -Anfangskapazität 16 beträgt, der Ladefaktor 0,75F und die Parallelitätsstufe 16 beträgt. Jetzt sehen wir den Code des Kernkonstruktors. Zunächst berechnen wir das SSIZE durch die eingehende Parallelitätslevel. SSIZE ist die Länge des Segmentarrays. Es muss garantiert eine Leistung von 2 sein. Auf diese Weise kann das Einweis des im Array gesperrten Segments durch Hash & Ssize-1 berechnet werden. Da das eingehende Parallelitätslevel nicht garantiert wird, dass es 2 ist, kann es nicht direkt als Länge des Segmentarrays verwendet werden. Daher müssen wir eine Kraft von 2 finden, die der Parallelitätslevel am nächsten liegt und sie als Länge des Arrays verwenden. Wenn die ConcurrencyLevel = 15 jetzt übergeben wird, kann der obige Code SSIZE = 16 und SSHIFT = 4 berechnen. Als nächstes können Sie SegmentShift = 16 und Segmentmask = 15 sofort berechnen. Beachten Sie, dass SegmentShift hier der Schaltwert der Segmentschloss und Segmentmask der Maskenwert der Segmentschloss ist. Diese beiden Werte werden verwendet, um das Index der Segmentschloss im Array zu berechnen, über das wir unten sprechen werden. Nach der Berechnung der Anzahl der Segmentschlösser SSIZE kann die Kapazität jedes Segmentschlosses basierend auf der Gesamteingangskapazität und des Werts C = InitialCapacity/Ssize berechnet werden. Die Kapazität des Segmentschlosses ist die Länge des Hashentry -Arrays, und es muss auch garantiert eine Leistung von 2 sein. Der oben berechnete Wert C kann dies nicht garantieren, sodass C nicht direkt als Länge des Hashentry -Arrays verwendet werden kann. Sie müssen eine weitere Leistung von 2 finden, die C am nächsten liegt, diesen Wert der Kappe zuordnen und dann CAP als Länge des Hashentry -Arrays verwenden. Nachdem wir SSIZE und CAP haben, können wir ein neues Segment -Sperrarray -Segment [] und ein Element -Array -Hashentry [] erstellen. Beachten Sie, dass im Gegensatz zu JDK1.6 nur das Segmentarray in JDK1.7 erstellt wurde und nicht initialisiert wurde. Der Betrieb der Initialisierung des Segments wurde dem Einfügungsvorgang überlassen.
V.
// Segment -Sperren basierend auf Hash -Code @SuppressWarnings ("Deaktiviert") Private Segment <k, v> SegmentForHash (int h) {long u = ((h >>> SegmentShift) & segmentmask) << SSHIFT) + SBASE; return (Segment <k, v>) unsicher.getObjectVolatile (Segmente, u);} // Element basierend auf Hash -Code @SuppressWarnings ("Unkontrolliert") statische endgültige <k, v> Hashentry <k, v> Eintriebsforhash (Segment <K, v> seg, int h) {Hashentry <K, V> [] Tab; Tab; Tab; return (Seg == null || (tab = Seg.table) == null)? NULL: (Hashentry <k, v>) unsicher.GetObjectVolatile (Tab, (lang) ((tab.length - 1) & h)) << TShift) + TBase);} In JDK1.7 wird unsicher verwendet, um Array -Elemente zu erhalten. Hier sind einige weitere Codes zur Berechnung von Array -Element -Offsets als JDK1.6. Wir werden diese Codes vorerst nicht achten. Jetzt müssen wir nur die folgenden zwei Punkte kennen:
A. Berechnen Sie das im Array gesperrte Segment -Einweis über den Hash -Code: (h >>> SegmentShift) und Segmentmask.
B. Berechnen Sie das Index der Elemente im Array nach Hash -Code: (tab.length - 1) & h.
Nehmen wir nun an, dass die beiden an den Konstruktor übergebenen Parameter initialCapacity = 128, ConcurrencyLevel = 16 sind. Nach der Berechnung können wir SSIZE = 16, SSHIFT = 4, SegmentShift = 28, Segmentmask = 15 erhalten. In ähnlicher Weise wird die Länge des Hashentry-Arrays in jeder Segmentschloss auf 8 berechnet, also Tab. Length-1 = 7. Basierend auf diesen Werten erläutern wir, wie Segmentschlösser und Elemente auf der Grundlage des gleichen Hash -Codes in der folgenden Abbildung basieren.
Es ist ersichtlich, dass die Segmentschloss und die Elementpositionierung durch den Hash -Code des Elements bestimmt werden. Die Positionierungssegmentschloss ist der hohe Wert des Hash -Codes (ab 32 Bit), und das Positionierungselement ist der niedrige Wert des Hash -Codes. Jetzt gibt es eine Frage. Sie beginnen vom linken Ende des 32-Bit- und dem rechten Ende des 32-Bit. Wird es irgendwann Konflikte geben? Wir können maximum_capacity = 1 << 30, max_segmente = 1 << 16 In der Mitgliedsvariable finden, was bedeutet, dass die Gesamtzahl der für die Positionierungssegmentschlösser und Positionierungselemente verwendeten Bits 30 nicht überschreitet, und die Anzahl der für die Positionierung von Segmentschlössern verwendeten Bits nicht mehr überschreitet, so dass mindestens 2 Bits übrig sind, so dass Konflikte keine Konflikte haben, müssen keine Konflikte verwendet werden. Es gibt keine Konflikte.
5. Wie findet man speziell Elemente?
// ValuEpublic V Get (Objektschlüssel) {Segment <k, v> s; Hashentry <k, v> [] Registerkarte; // Berechnen Sie den Hash -Code mit der Hash -Funktion int H = Hash (Schlüssel); // Berechnen Sie den Index der Segmentschloss basierend auf dem Hash -Code long u = (((h >>> SegmentShift) & Segmentmask) << SSHIFT) + SBASE; // Erhalten Sie die Segmentschloss und die entsprechende Hash -Tabelle, wenn ((s = (Segment <k, v>) unsicher.getObjectVolatile (Segmente, u)! = Null && (tab = s.table)! (Hashentry <k, v>) unsicher.GetObjectVolatile (Tab, (lang) ((tab.length - 1) & h) << TShift) + TBase); // Folgen Sie dem Wert des entsprechenden Elements gemäß dem Schlüssel und dem Hash und geben Sie den Wert zurück, wenn ((k = e.Key) == Key || (E.Hash == H && key.equals (k))) {return e.Value; }}} return null;}In JDK1.6 greift die GET -Methode des Segments auf Array -Elemente über Indexs zu, während in JDK1.7 die Elemente im Array durch die GetObjectVolatile -Methode von Unsicherheit gelesen werden. Warum tun das? Wir wissen, dass zwar die vom Segmentobjekt gehaltene Hashentry -Array -Referenz vom Typ flüchtig ist, die Elementreferenzen im Array nicht vom Typ flüchtig sind, so dass Multithreading -Modifikationen an Array -Elementen unsicher sind und Objekte, die noch nicht im Array konstruiert wurden, lesen können. In JDK1.6 ist die zweite Lektüre garantiert sicher, und in JDK1.7 ist die Lesung durch das GetObjectVolatile -Methode von Unsicherheit auch, um dies sicherzustellen. Das Lesen von Array -Elementen unter Verwendung der GetObjectVolatile -Methode erfordert zunächst den Offset des Elements im Array. Laut dem Hash -Code ist der Versatz der Segmentschloss im Array u, und dann wird der Offset u verwendet, um zu versuchen, das Segmentschloss zu lesen. Da das Segment -Sperr -Array während der Konstruktion nicht initialisiert wird, kann ein Nullwert ausgelesen werden, sodass zuerst ein Urteil erforderlich ist. Nachdem bestätigt wurde, dass das Segmentschloss und seine interne Hash -Tabelle nicht leer sind, werden die Elemente des Hashentry -Arrays durch den Hash -Code gelesen. Nach dem obigen Strukturdiagramm können Sie sehen, dass der Headerknoten der verknüpften Liste zu diesem Zeitpunkt erhalten wird. Dann durchqueren und die verknüpfte Liste von Anfang bis Ende durchsuchen. Wenn der entsprechende Wert gefunden wird, wird er zurückgegeben, andernfalls wird er null zurückgegeben. Das obige ist der gesamte Prozess des Findens von Elementen.
6. Wie kann man das Einfügungselement implementieren?
// Taste-Wert-Paare zum Set hinzufügen (ersetzen Sie, wenn es vorhanden ist) @SuppressWarnings ("Deaktiviert") public v put (k key, v value) {segment <k, v> s; // Der übergebene Wert kann nicht leer sein, wenn (value == null) neue nullpointerexception () veranstaltet; // Berechnen Sie den Hash -Code mit der Hash -Funktion int Hash = Hash (Schlüssel); // Berechnen Sie den Index der Segmentschloss basierend auf dem Hash -Code int j = (Hash >>> SegmentShift) und Segmentmask; // Versuchen Sie, die Segmentschloss basierend auf dem Index zu erhalten, wenn ((s = (Segment <k, v>) unsicher.getObject (Segmente, (j << sShift) + sbase)) == null) {// Wenn das erhaltene Segmentschloss leer ist, konstruieren Sie eine s = -Seuresegment (j); } // Rufen Sie die Put-Methode der Segment-Sperre-Rückgabe S. PUT (Schlüssel, Hash, Wert, Falsch) auf;} // Fügen Sie dem Satz ein Schlüssel-Wert hinzu (fügen Sie hinzu, wenn es nicht vorhanden ist) @SuppressWarnings ("deaktiviert") public v putifabsent (k key, v-Wert) {Segment <k, v> s; // Der übergebene Wert kann nicht leer sein, wenn (value == null) neue nullpointerexception () veranstaltet; // den Hash -Code mit Hash = Hash (Schlüssel) berechnen; // Berechnen Sie den Index der Segmentschloss basierend auf dem Hash -Code int j = (Hash >>> SegmentShift) und Segmentmask; // Versuchen Sie, die Segmentschloss basierend auf dem Index zu erhalten, wenn ((s = (Segment <k, v>) unsicher.GetObject (Segmente, (j << sShift) + sbase) == null) {// Konstruieren eines S = -S -SEFELEGENMENS (j); } // Kalender die Put -Methode der Segment -Sperre -Rückgabe S. PUT (Schlüssel, Hash, Wert, TRUE);}In Concurrenthashmap gibt es zwei Methoden, um Schlüsselwertpaare hinzuzufügen. Wenn es existiert, wird es überschrieben, wenn es durch die Put -Methode hinzugefügt wird. Die IFABSENT -Methode wird durch die Put -IfabSent -Methode hinzugefügt, sie wird nicht überschrieben. Beide Methoden rufen die Put -Methode der Segmentschloss an, um den Vorgang zu vervollständigen. Der letzte in übergebene Parameter ist jedoch unterschiedlich. Im obigen Code können wir zunächst sehen, dass wir den Index der Segmentsperrung im Array basierend auf dem Hash -Code des Schlüssels berechnen und dann die unsichere Klasse GetObject -Methode verwenden, um die Segmentschloss gemäß dem Index zu lesen. Da die Elemente im Segmentarray beim Erstellen der Concurrenthashmap nicht initialisiert werden, kann ein Nullwert gelesen werden, und eine neue Segmentschloss wird über die SEFELEGENGEN -Methode erstellt. Rufen Sie nach Erhalt der Segmentschloss die Put -Methode auf, um den Additionsvorgang abzuschließen. Schauen wir uns an, wie Sie es bedienen können.
// Schlüsselwertpaare endgültig v Put (K Key, int Hash, V -Wert, nur boolean ifababSent) {// Versuchen Sie, das Schloss zu erwerben, wenn es fehlschlägt, spin Hashentry <k, v> node = trylock ()? NULL: ScanandlockForput (Schlüssel, Hash, Wert); V OldValue; Versuchen Sie {Hashentry <k, v> [] tab = table; // Berechnen Sie den Index des Elements des Elements in Index = (tab.length - 1) & Hash; // Erhalten Sie den Header -Knoten der verlinkten Liste basierend auf dem Index Hashentry <K, v> first = Eintrag (Registerkarte, Index); für (Hashentry <k, v> e = First ;;) {// die verlinkte Liste übertragen, um das Element zu finden, und if (e! = null) {k k; if ((k = E.Key) == Key || (e.hash == Hash && key.equals (k)))) {oldValue = e.Value; // Entscheiden Sie, ob der alte Wert basierend auf den Parametern ersetzt werden soll, wenn (! OnlyIFABSent) {E. value = value; ++ modcount; } brechen; } e = e.Next; // Wenn nicht gefunden, fügen Sie der verknüpften Liste einen Knoten hinzu} else {// den Knotenknoten in die Header der verknüpften Liste einfügen, wenn (knoten! = Null) {node.setNext (zuerst); } else {node = new Hashentry <k, v> (Hash, Schlüssel, Wert, zuerst); } // Fügen Sie nach dem Einsetzen des Knotens immer 1 int c = count + 1 hinzu; // Wenn das Element den Schwellenwert überschreitet, erweitern Sie die Kapazität if (c> Schwellenwert && tab.length <maximum_capacity) {Rehash (Knoten); // Ansonsten ersetzen Sie den angegebenen Einweis für Hash -Tabellen durch den Knotenknoten} else {setEntryat (Registerkarte, Index, Knoten); } ++ modcount; count = c; oldValue = null; brechen; }}} endlich {Unlock (); } kehren Sie OldValue zurück;}Um die Sicherheit der Gewinde zu gewährleisten, müssen die Vorgänge in segmentierte Schlösser gesperrt werden, damit der Faden das Schloss zu Beginn erfasst und weiter ausführen wird, wenn die Akquisition erfolgreich ist. Wenn die Akquisition fehlschlägt, rufen Sie die ScanandLockForput -Methode zum Drehen auf. Scannen Sie während des Spinprozesses die Hash -Tabelle, um den angegebenen Schlüssel zu finden. Wenn der Schlüssel nicht vorhanden ist, wird ein neues Hashentry erstellt, sodass nach dem Erhalten des Schlosses nicht erneut erstellt werden muss. Um einige Dinge zu tun, während sie auf das Schloss warten, verschwendet es keine Zeit. Dies zeigt die guten Absichten des Autors. Wir werden die spezifische Spinmethode später im Detail erläutern. Ziehen Sie nun zuerst den Fokus zurück. Nachdem der Thread die Sperre erfolgreich erworben hat, wird das Element des angegebenen Indexs basierend auf dem berechneten Index eingereicht. Zu diesem Zeitpunkt wird der Headerknoten der verknüpften Liste erhalten. Wenn der Headerknoten nicht leer ist, wird die verknüpfte Liste durchsucht und durchsucht. Entscheiden Sie nach dem Finden, ob Sie es basierend auf dem Wert des einzigen Parameters ersetzen möchten. Wenn der Traversal nicht gefunden wird, zeigt ein neuer Hashentry auf den Headerknoten. Wenn beim Spin ein Hashentry erstellt wird, richten Sie zu diesem Zeitpunkt direkt den aktuellen Header -Knoten. Wenn der Spin nicht erstellt wird, wird hier ein neues Hashentry erstellt und auf den Headerknoten verweist. Überprüfen Sie nach dem Hinzufügen von Elementen zur verlinkten Liste, ob die Gesamtzahl der Elemente den Schwellenwert überschreitet. Wenn es überschreitet, rufen Sie Rehash für die Erweiterung an. Wenn es es nicht überschreitet, beziehen Sie sich direkt auf das entsprechende Indexelement des Arrays auf den neu hinzugefügten Knoten. Die SetEnryat -Methode ändert die Array -Elementreferenz, indem sie die PutOrderedObject -Methode von Unsicherheit aufruft, wodurch sichergestellt wird, dass andere Threads beim Lesen den neuesten Wert lesen können.
7. Wie kann ich die Löschung von Elementen implementieren?
// das angegebene Element löschen (direkt nach dem Finden des entsprechenden Elements löschen) public v Remove (Objektschlüssel) {// Verwenden Sie die Hash -Funktion, um den Hash -Code int Hash = Hash (Schlüssel) zu berechnen. // Erwerben Sie den Index der Segmentschloss basierend auf dem Hash -Code -Segment <k, v> S = SegmentForHash (Hash); // Kalenden Sie die Methode der Segmentschloss return s == null? NULL: S.Remove (Schlüssel, Hash, NULL);} // Löschen Sie das angegebene Element (entfernt den Wert, der dem angegebenen Wert entspricht). Segment <k, v> s; // kann sicherstellen, dass die Segmentschloss nicht leer ist, bevor Sie den Return -Wert entfernen.Concurrenthashmap liefert zwei Löschvorgänge, eine besteht darin, sie direkt nach dem Finden zu löschen, und das andere ist es, sie zuerst zu vergleichen und dann nach dem Finden zu löschen. Beide Löschmethoden können die entsprechende Segmentschloss basierend auf dem Hash -Code des Schlüssels ermitteln und dann die Löschvorrichtung abschließen, indem Sie die Methode der Segmentschloss entfernen. Schauen wir uns die Entfernung der Segmentschloss an.
// Löschen Sie das angegebene Element Final V REMET (Objektschlüssel, int Hash, Objektwert) {// Versuchen Sie, das Sperre zu erwerben. } V oldValue = null; Versuchen Sie {Hashentry <k, v> [] tab = table; // Berechnen Sie den Index des Elements des Elements in Index = (tab.length - 1) & Hash; // Erhalten Sie das Array -Element gemäß dem Index (Link -List -Header -Knoten) Hashentry <K, v> e = Eintrag (Registerkarte, Index); Hashentry <k, v> pred = null; // Übertragen Sie die verknüpfte Liste, um das Element zu finden, das gelöscht werden soll, während (e! = Null) {k k k; // Der nächste zeigt auf den Nachfolgerknoten des aktuellen Knotens Hashentry <k, v> next = e.Next; // Suchen Sie nach dem entsprechenden Knoten basierend auf Schlüssel und Hash if ((k = E.Key) == Key || (e.hash == Hash && key.equals (k))) {v v = e.Value; // Überspringen Sie den Wert, der in nicht gleich V übergeben wird, und löschen Sie ihn in anderen Fällen, wenn (value == null || value == v || value.equals (v)) {// Wenn Pred leer ist, bedeutet dies, dass der zu gelöschte Knoten der Header -Knoten ist, wenn (pred == null) {// Das Header -Node des verknüpften Listen -Listen -Setentryats (Tabryat, Index, Index, Index), nächst } else {// Setzen Sie die Nachfolge des Vorhersageknotens auf den nächsten Knoten Pred.setNext (Weiter); } ++ modcount; --zählen; // Notieren Sie den Wert des Element -Löschungs oldValue = v; } brechen; } // Wenn E nicht der Knoten ist, nach dem Sie suchen, verweisen Sie auf die Verweise auf sie pred = e; // Überprüfen Sie den nächsten Knoten e = Weiter; }} endlich {unlock (); } kehren Sie OldValue zurück;}Beim Löschen von Elementen in Segmentschlössern müssen Sie zuerst das Schloss erwerben. Wenn die Akquisition fehlschlägt, rufen Sie die Scanandlock -Methode zum Spinnen auf. Wenn die Akquisition erfolgreich ist, führen Sie den nächsten Schritt aus. Berechnen Sie zuerst das Array -Index und erhalten Sie dann die Elemente des Hashentry -Arrays über das Index. Hier wird der Kopfknoten der verknüpften Liste erhalten. Als nächstes durchqueren und durchsuchen Sie die verknüpfte Liste. Verwenden Sie zuvor den nächsten Zeiger, um den Nachfolgerknoten des aktuellen Knotens aufzuzeichnen, und vergleichen Sie dann den Schlüssel und den Hash, um festzustellen, ob es sich um den Knoten handelt, den Sie suchen. Wenn ja, führen Sie das nächste If -Urteil durch. Wenn der Wert leer ist oder der Wert gleich dem aktuellen Wert des Knotens ist, wird die IF -Anweisung für das Löschen eingegeben, andernfalls wird er direkt übersprungen. Es gibt zwei Situationen bei der Durchführung eines Löschvorgangs in einer IF -Anweisung. Wenn der aktuelle Knoten ein Headerknoten ist, stellen Sie den nächsten Knoten direkt als Headerknoten ein. Wenn der aktuelle Knoten kein Headerknoten ist, setzen Sie den Nachfolger des Vorhersageknotens auf den nächsten Knoten. Der Vorhersageknoten hier repräsentiert den Vorgänger des aktuellen Knotens. Jedes Mal vor dem Überprüfen des nächsten Knotens wird Pred auf den aktuellen Knoten hingewiesen, wodurch der Vorhersageknoten immer der Vorgänger des aktuellen Knotens ist. Beachten Sie, dass im Gegensatz zu JDK1.6 in JDK1.7 die nächste Variable des Hashentry -Objekts nicht endgültig ist, sodass Sie das Element löschen können, indem Sie direkt den Wert ändern, auf den als nächstes verwiesen wird. Da die nächste Variable flüchtig ist, kann der Lesungsthread den neuesten Wert sofort lesen.
8. Wie werden die Ersatzelemente speziell implementiert?
// Ersetzen Sie das angegebene Element (CAS -Betrieb) öffentlicher Boolescher Ersatz (K Key, v OldValue, v NewValue) {// Verwenden Sie die Hash -Funktion, um den Hash -Code int Hash = Hash (Schlüssel) zu berechnen; // Stellen Sie sicher, dass OldValue und NewValue nicht leer sind, wenn (oldValue == null || newValue == null) neue nullpointerexception () werfen; // Erhalten Sie den Index der Segmentschloss basierend auf dem Hash -Code -Segment <k, v> S = SegmentForHash (Hash); //Calling the replacement method of the segment lock returns s != null && s.replace(key, hash, oldValue, newValue);}//Replace element operation (CAS operation) final boolean replace(K key, int hash, V oldValue, V newValue) { //Try to acquire the lock, if it fails, spin if (!tryLock()) { scanAndLock(key, hash); } boolean ersetzt = false; Versuchen Sie {Hashentry <k, v> e; // Durchsuchen Sie den Header -Knoten direkt durch Hash und durchqueren Sie dann die verknüpfte Liste für (e = uneintriebsforHash (this, Hash); e! = Null; e = e.next) {k k; // Suchen Sie den Knoten, der basierend auf dem Schlüssel und Hash if ((k = e.Key) == Key || (e.hash == Hash && key.equals (k))) {// Wenn der angegebene aktuelle Wert korrekt ist, if (oldValue.equals (e.Value)) {e.value = newValue; ++ modcount; ersetzt = wahr; } // Ansonsten, wenn keine Operation durchgeführt wird, die Rückbruchpause; }}} endlich {Unlock (); } Rückgabe ersetzt;}Concurrenthashmap liefert auch zwei Ersatzvorgänge, eine soll direkt nach dem Finden ersetzen, und der andere ist zuerst zu vergleichen und dann zu ersetzen (CAS -Betrieb). Die Implementierung dieser beiden Operationen ist ungefähr gleich, mit der Ausnahme, dass der CAS -Betrieb eine zusätzliche Schicht von Vergleichsvorgängen hat, bevor wir ersetzt werden. Daher müssen wir nur einen der Operationen kurz verstehen. Hier verwenden wir CAS -Operationen zur Analyse, was immer noch eine alte Routine ist. Suchen Sie zuerst die entsprechende Segmentschloss basierend auf dem Hash -Code des Schlüssels und rufen Sie dann seine Ersatzmethode auf. Nach dem Eingeben der Ersatzmethode in der Segmentschloss müssen Sie zuerst das Schloss erwerben. Wenn die Akquisition fehlschlägt, drehen Sie sie. Wenn die Akquisition erfolgreich ist, fahren Sie mit dem nächsten Schritt fort. Ermitteln Sie zunächst den Header -Knoten der verknüpften Liste gemäß dem Hash -Code und durchqueren und suchen Sie nach dem Schlüssel und dem Hash. Vergleichen Sie nach dem Finden des entsprechenden Elements, ob der gegebene alte Wert der aktuelle Wert ist. Wenn nicht, geben Sie die Änderung auf und ersetzen Sie sie, wenn ja, durch den neuen Wert. Da das Wertfeld des Hashentry -Objekts vom Typ flüchtig ist, kann es direkt ersetzt werden.
9. Was genau hast du beim Spinnen gemacht?
// Spin warten, um das private Hashentry <K, v> scanandlockForput (K -Schlüssel, int Hash, V -Wert) zu erwerben (Key, Int Hash, V Value) {// den Header -Knoten gemäß dem Hash -Code -Hashentry <k, v> first = uneintrageForHash (thish); Hashentry <k, v> e = zuerst; Hashentry <k, v> node = null; int retries = -1; // Spin während (! Trylock ()) {Hashentry <k, v> f; if (return <0) {// Wenn der Header -Knoten leer ist, erstellen Sie einen neuen Knoten if (e == null) {if (node == null) {node = new Hashentry <k, v> (Hash, Schlüssel, Wert, Null); } retries = 0; // Ansonsten durchqueren Sie die verknüpfte Liste, um den Knoten zu finden} else if (key.equals (e.Key)) {retries = 0; } else {e = e.Next; } // Abrufen fügen hier jedes Mal 1 hinzu und bestimmen Sie, ob es den Maximalwert überschreitet. brechen; // Bei Wiederholungen sogar Zahlen bestimmen, ob sich der erste geändert hat} else if ((Retries & 1) == 0 && (f = uneinträgeforHash (this, Hash))! = First) {e = first = f; Wiederholungen = -1; }} Return Node;} // Spin -Warten, um Sperre zu erwerben (Operationen entfernen und ersetzen) private void scanandlock (Objektschlüssel, int Hash) {// den Header -Knoten der verknüpften Liste gemäß dem Hash -Code -Hashentry <k, v> first = Eintriebsforhash (this, Hash) erhalten; Hashentry <k, v> e = zuerst; int retries = -1; // Spin während (! Trylock ()) {Hashentry <k, v> f; if (retries <0) {// Übertragen Sie die verknüpfte Liste, um den Knoten zu finden if (e == null || key.equals (e.Key)) {retries = 0; } else {e = e.Next; } // Abrufen fügen hier jedes Mal 1 hinzu und bestimmen Sie, ob es den Maximalwert überschreitet. brechen; // Bei Wiederholungen sogar Zahlen bestimmen, ob sich der erste geändert hat} else if ((Retries & 1) == 0 && (f = uneinträgeforHash (this, Hash))! = First) {e = first = f; Wiederholungen = -1; }}}Wie bereits erwähnt, müssen die Vorgänge in segmentierten Schlössern vorgenommen, entfernen und ersetzen, dass das Schloss zuerst erworben wird. Erst nach erfolgreichem Erhalten kann der nächste Vorgang durchgeführt werden. Wenn die Akquisition fehlschlägt, wird Spin durchgeführt. Der Spinbetrieb wird auch in JDK1.7 hinzugefügt. Um häufiges Suspendieren und Aufwachen von Threads zu vermeiden, kann dies die Leistung während gleichzeitiger Operationen verbessern. Der ScanandLockForput wird in der Put -Methode aufgerufen und der Scanandlock wird in den Entfernen und Ersetzen aufgerufen. Die beiden Spin -Methoden sind ungefähr gleich. Hier analysieren wir nur die ScanandlockForput -Methode. Zunächst sollten Sie den Header -Knoten der verknüpften Liste basierend auf dem Hash -Code erhalten. Anschließend wird der Thread die zum Ausführen von WHOSE GEFOHREN eingeben. Die einzige Möglichkeit, die Schleife zu verlassen, besteht darin, das Schloss erfolgreich zu erwerben, und der Faden wird während dieser Zeit nicht ausgesetzt. Wenn die Schleife gerade eingegeben wird, beträgt der Wert der Wiederholungen -1. Zu diesem Zeitpunkt versucht der Thread nicht, das Schloss sofort zu erwerben. Stattdessen findet er zuerst den Knoten, der dem Schlüssel entspricht (falls er nicht gefunden wird, ein neues erstellt) und dann die Wiederholungen auf 0 festlegen. Als nächstes wird es immer wieder versuchen, das Schloss zu erwerben. Der entsprechende Rückgangswert wird auch jedes Mal 1 hinzugefügt, bis die maximale Anzahl von Versuchen die maximale Anzahl von Versuchen überschreitet. Wenn das Schloss nicht erhalten wurde, wird die Sperrmethode zum Blockieren und Erhalten gefordert. Während des Versuchs, das Schloss zu erwerben, wird prüfen, ob der Headerknoten jedes Mal geändert wurde (Wiederholungen sind gleichmäßig). Wenn es geändert wird, setzen Sie die Wiederholungen wieder auf -1 zurück und wiederholen Sie den Vorgang jetzt. Das macht der Thread beim Drehen. Es ist zu beachten, dass die Spin -Zeit des Fadens verlängert wird, wenn der Kopfknoten festgestellt wurde, um während des Spins zu verändern.
10. Welche Operationen werden durchgeführt, wenn die Hash -Tabelle erweitert wird?
// Hash erneut @SuppressWarnings ("Deaktiviert") private void rehash (Hashentry <k, v> node) {// Erhalten Sie den Verweis auf die alte Hash -Tabelle Hashentry <k, v> [] oldTable = Tabelle; // Erhalten Sie die Kapazität der alten Hash -Tabelle int oldCapacity = oldTable.length; // Berechnen Sie die Kapazität der neuen Hash -Tabelle (2 -mal der alten Hash -Tabelle) int NewCapacity = OldCapacity << 1; // Berechnen Sie den neuen Element -Schwellenwert. // Erstellen Sie ein neues Hashentry Array Hashentry <K, v> [] newtable = (Hashentry <k, v> []) New Hashentry [NewCapacity]; // neue Maskenwert int sizemask = newCapacity - 1; // Ruhe durch alle Elemente der alten Tabelle für (int i = 0; i <OldCapacity; i ++) {// den Header -Knoten der verknüpften Liste Hashentry <k, v> e = oldTable [i] erhalten; if (e! = null) {Hashentry <k, v> next = e.Next; // Berechnen Sie den Index des Elements in der neuen Tabelle int idx = e.hash & sizemask; // Als nächstes ist leer, um anzuzeigen, dass in der verknüpften Liste nur ein Knoten in der verlinkten Liste steht, wenn (next == null) {// den Knoten direkt in die neue Tabelle einfügen [idx] = e; } else {Hashentry <k, v> lastrun = e; int lastidx = idx; // Positionieren Sie den Lastrunknoten und legen Sie den Knoten nach Lastrun direkt in die neue Tabelle für (Hashentry <k, v> last = next; last! = Null; last = last.next) {int k = last.hash & sizemask; if (k! = lastidx) {lastIdx = k; Lastrun = letztes; }} newtable [lastidx] = lastrun; // Die Elemente vor dem Lastrun -Knoten der verlinkten Liste transipieren, kopieren Sie sie wiederum in die neue Tabelle für (Hashentry <k, v> p = e; p! = Lastrun; p = p.Next) {v v = p.Value; int h = p.hash; int k = h & sizemask; Hashentry <k, v> n = newtable [k]; newtable [k] = neuer Hashentry <k, v> (H, P.Key, v, n); }}}}} // Berechnen Sie den Index des eingehenden Knotens in der neuen Tabelle int nodeIndex = node.hash & sizemask; // den eingehenden Knoten zum Header -Knoten des verknüpften List -Knotens hinzufügen. // Tauschen Sie die neue Tabelle angegeben mit dem eingehenden Knoten. // Zeigen Sie auf die Hash -Tabelle Referenz auf die neue Tabelle Tabelle = newtable;}Die Rehash -Methode wird in der Put -Methode aufgerufen. Wir wissen, dass das neue Element beim Put -Methode erstellt und dem Hash -Array hinzugefügt wird. Je größer die Möglichkeit von Hash -Konflikten auftritt, desto größer wird die Leistung der Hash -Tabelle abnehmen. Daher wird jedes Mal überprüft, ob die Gesamtzahl der Elemente den Schwellenwert überschreitet. Wenn es den Schwellenwert überschreitet, wird die Rehash -Methode aufgefordert, die Kapazität zu erweitern. Da die Länge des Arrays nicht mehr geändert werden kann, sobald es bestimmt ist, muss ein neues Array erstellt werden, um das ursprüngliche Array zu ersetzen. Aus dem Code können Sie wissen, dass das neu erstellte Array doppelt so hoch ist wie die Länge des ursprünglichen Arrays (OldCapacity << 1). After creating a new array, you need to move all elements in the old array into the new array, so you need to calculate the subscript of each element in the new array. The process of calculating the new subscript is shown in the figure below.
我们知道下标直接取的是哈希码的后几位，由于新数组的容量是直接用旧数组容量右移1位得来的，因此掩码位数向右增加1位，取到的哈希码位数也向右增加1位。如上图，若旧的掩码值为111，则元素下标为101，扩容后新的掩码值为1111，则计算出元素的新下标为0101。由于同一条链表上的元素下标是相同的，现在假设链表所有元素的下标为101，在扩容后该链表元素的新下标只有0101或1101这两种情况，因此数组扩容会打乱原先的链表并将链表元素分成两批。在计算出新下标后需要将元素移动到新数组中，在HashMap中通过直接修改next引用导致了多线程的死锁。虽然在ConcurrentHashMap中通过加锁避免了这种情况，但是我们知道next域是volatile类型的，它的改动能立马被读线程读取到，因此为保证线程安全采用复制元素来迁移数组。但是对链表中每个元素都进行复制有点影响性能，作者发现链表尾部有许多元素的next是不变的，它们在新数组中的下标是相同的，因此可以考虑整体移动这部分元素。具统计实际操作中只有1/6的元素是必须复制的，所以整体移动链表尾部元素(lastRun后面的元素)是可以提升一定性能的。
注：本篇文章基于JDK1.7版本。
Das obige ist der gesamte Inhalt dieses Artikels. Ich hoffe, es wird für das Lernen aller hilfreich sein und ich hoffe, jeder wird Wulin.com mehr unterstützen.