Dies ist ein von KI übersetzter Beitrag.
Sprache auswählen
Von durumis AI zusammengefasster Text
- Synchronisierte Sammlungen wie Vector, Hashtable und Collections.synchronizedXXX verwenden intern das synchronized-Schlüsselwort, um die Gleichzeitigkeit zu gewährleisten, können jedoch zu Leistungseinbußen führen, wenn mehrere Operationen gebündelt werden oder wenn Leistungseinbußen auftreten.
- Das Paket java.util.concurrent bietet parallele Sammlungen wie CopyOnWriteArrayList, ConcurrentMap, ConcurrentHashMap und andere Klassen, die eine höhere Leistung als synchronisierte Sammlungen bieten.
- Parallele Sammlungen wie CopyOnWriteArrayList und ConcurrentHashMap bieten eine höhere Leseleistung als synchronisierte Sammlungen und sind effektiv, wenn Schreibvorgänge relativ selten sind.
Synchronisierte Sammlung
Synchronisierte Sammlungen sind in der Regel Klassen wie die folgenden:
- Vektor
- Hashtable
- Collections.synchronizedXXX
Alle diese Klassen verwenden das Schlüsselwort synchronized in öffentlich deklarierten Methoden, um sicherzustellen, dass nur ein Thread gleichzeitig auf die Werte zugreifen kann und gleichzeitig die Gleichzeitigkeit gewährleistet.
Vektor
public class Vector extends AbstractList
implements List, RandomAccess, Cloneable, java.io.Serializable {
...
public synchronized boolean add(E e) {
modCount++;
add(e, elementData, elementCount);
return true;
}
... Betrachten wir die add()-Methode, die Elemente in der Vector-Klasse hinzufügt, sehen wir das Schlüsselwort synchronized. D. h. innerhalb von Vector wird der Einfügevorgang von Elementen synchronisiert.
Hashtable
public class Hashtable extends Dictionary
implements Map, Cloneable, java.io.Serializable {
...
public synchronized boolean contains(Object value) {
if (value == null) {
throw new NullPointerException();
}
Entry tab[] = table;
for (int i = tab.length ; i-- > 0 ;) {
for (Entry e = tab[i] ; e != null ; e = e.next) {
if (e.value.equals(value)) {
return true;
}
}
}
return false;
}
... Wenn wir uns die contains()-Methode in der Hashtable-Klasse ansehen, um zu überprüfen, ob der gleiche Wert vorhanden ist, stellen wir fest, dass das Schlüsselwort synchronized verwendet wird, genau wie in der Vector-Klasse.
Collections.synchronizedXXX
Schauen wir uns nun die SynchronizedList-Klasse an, die mit der Methode Collections.synchronizedList() erzeugt wird.
static class SynchronizedList extends SynchronizedCollection
implements List {
final Object mutex;
...
public E get(int index) {
synchronized (mutex) {return list.get(index);}
}
public E set(int index, E element) {
synchronized (mutex) {return list.set(index, element);}
}
public void add(int index, E element) {
synchronized (mutex) {list.add(index, element);}
}
public E remove(int index) {
synchronized (mutex) {return list.remove(index);}
}
... Wenn wir uns die Methoden der SynchronizedList-Klasse ansehen, stellen wir fest, dass alle das Schlüsselwort synchronized verwenden. Allerdings wurde die Synchronisation mithilfe eines Mutex über einen synchronisierten Block implementiert. Da alle Methoden das Mutex-Objekt gemeinsam nutzen, werden alle synchronisierten Blöcke anderer Methoden gesperrt, sobald ein Thread in den synchronisierten Block eingetreten ist.
Probleme mit synchronisierten Sammlungen
In einer Multithread-Umgebung kann es notwendig sein, synchronisierte Sammlungen zu verwenden. Es ist jedoch ratsam, andere Synchronisationsmethoden zu verwenden, wenn möglich. Es gibt dafür zwei Hauptgründe:
Mehrere Operationen als eine einzelne Operation zusammenfassen
Synchronisierte Sammlungsklassen gewährleisten die Gleichzeitigkeit in einer Multithread-Umgebung. Wenn jedoch mehrere Operationen zu einer einzigen Operation zusammengefasst werden müssen, können Probleme auftreten. Die Verwendung dieser synchronisierten Sammlungen kann zu Fehlfunktionen führen.
final List list = Collections.synchronizedList(new ArrayList());
final int nThreads = 2;
ExecutorService es = Executors.newFixedThreadPool(nThreads);
for (int i = 0; i < nThreads; i++) {
es.execute(new Runnable() {
public void run() {
while(true) {
try {
list.clear();
list.add("888");
list.remove(0);
} catch(IndexOutOfBoundsException e) {
e.printStackTrace();
}
}
}
}); Wenn der obige Code ausgeführt wird, tritt ein Fehler auf, wenn Thread A remove(0) ausführt und Thread B gleichzeitig clear() ausführt. Daher muss dies mit einem synchronisierten Block wie folgt umschlossen werden.
synchronized (list) {
list.clear();
list.add("888");
list.remove(0);Leistungseinbußen
Wenn alle Methoden, die auf ein gemeinsam genutztes Objekt zugreifen möchten, zu synchronisierten Methoden gemacht werden oder innerhalb der Methoden der gleiche synchronisierte Block definiert wird, kann kein anderer Thread alle synchronisierten Methoden verwenden, wenn ein Thread die Sperre erlangt hat. Dieser Thread befindet sich dann in einem Sperrzustand. Diese wiederholten Vorgänge können zu Leistungseinbußen führen.
Gleichzeitige Sammlung
Das Paket java.util.concurrent bietet verschiedene Arten von parallelen Sammlungen. In diesem Artikel werden nur einige davon behandelt.
- CopyOnWriteArrayList
- Eine Unterklasse der List-Klasse, die eine parallele Sammlung ist, die die Leistung von Operationen priorisiert, die die Objekt-Liste durchlaufen und abrufen.
- ConcurrentMap
- Eine parallele Sammlung, deren Schnittstelle Operationen wie put-if-absent, replace und bedingtes Entfernen definiert, die einen neuen Eintrag nur dann hinzufügen, wenn der hinzuzufügende Eintrag noch nicht vorhanden ist.
- ConcurrentHashMap
- Eine Unterklasse von ConcurrentMap, eine parallele Sammlung, die HashMap ersetzt und gleichzeitig die Parallelität gewährleistet.
- ConcurrentLinkedQueue
- Eine parallele Sammlung, die eine Queue im FIFO-Modus (First In First Out) ist. Wenn kein Element aus der Queue entnommen werden kann, wird sofort eine Rückgabe durchgeführt und eine andere Aufgabe ausgeführt.
- LinkedBlockingQueue
- Ähnlich wie ConcurrentLinkedQueue. Der Unterschied besteht darin, dass Operationen zum Entfernen von Elementen aus der Queue warten, bis ein neues Element hinzugefügt wird, wenn die Queue leer ist. Umgekehrt wird das Hinzufügen eines neuen Elements in die Queue warten, bis Platz frei wird, wenn die Queue eine bestimmte Größe hat und vollständig gefüllt ist.
- ConcurrentSkipListMap, ConcurrentSkipListSet
- Fortschrittliche Versionen der Klassen SortedMap bzw. SortedSet, die die Parallelität verbessern.
Der Austausch bestehender synchronisierter Sammlungsklassen durch parallele Sammlungen kann die Gesamtperformance ohne zusätzliche Risiken deutlich verbessern.
Lassen Sie uns die synchronisierten Sammlungen im Vergleich zu parallelen Sammlungen genauer betrachten.
CopyOnWriteArrayList
Es gibt zwei Möglichkeiten, eine synchronisierte ArrayList zu erstellen:
- Collections.synchronizedList()
- CopyOnWriteArrayList
Collections.synchronizedList() wurde in JDK 1.2 hinzugefügt. Diese Sammlung ist für alle Lese- und Schreibvorgänge synchronisiert. Dies kann als ein nicht flexibles Design angesehen werden. Daher wurde CopyOnWriteArrayList als Ergänzung eingeführt.
Lesevorgänge
SynchronizedList sperrt die Instanz selbst beim Lesen und Schreiben. CopyOnWriteArrayList hingegen kopiert bei jedem Schreibvorgang die Elemente aus dem ursprünglichen Array in ein neues temporäres Array und führt dann den Schreibvorgang in diesem temporären Array durch, bevor das ursprüngliche Array aktualisiert wird. Dadurch sind Lesevorgänge nicht gesperrt, was CopyOnWriteArrayList schneller macht als SynchronizedList.
public class CopyOnWriteArrayList implements List, RandomAccess, Cloneable, java.io.Serializable {
final transient Object lock = new Object();
private transient volatile Object[] array;
...
public E get(int index) {
return elementAt(getArray(), index);
}
... Dies ist die get()-Methode, die keine Synchronisierung enthält und daher nicht gesperrt ist.
Schreibvorgänge
CopyOnWriteArrayList verwendet beim Ausführen von Schreibvorgängen eine explizite Sperre. Letztendlich werden beide Sammlungstypen beim Ausführen dieses Vorgangs gesperrt. Da CopyOnWriteArrayList einen relativ teuren Kopiervorgang für das Array verwendet, kann es zu Leistungsproblemen kommen, wenn viele Schreibvorgänge ausgeführt werden.
public class CopyOnWriteArrayList implements List, RandomAccess, Cloneable, java.io.Serializable {
final transient Object lock = new Object();
private transient volatile Object[] array;
public void add(int index, E element) {
synchronized (lock) {
...
int numMoved = len - index;
if (numMoved == 0)
newElements = Arrays.copyOf(es, len + 1);
else {
newElements = new Object[len + 1];
System.arraycopy(es, 0, newElements, 0, index);
System.arraycopy(es, index, newElements, index + 1,
numMoved);
}
...
}
} Dies ist die add()-Methode, die einen synchronisierten Block verwendet, um eine Sperre zu setzen und das Array zu kopieren.
Iterator
In CopyOnWriteArrayList werden die Daten der Sammlung zum Zeitpunkt des Abrufens des Iterators iteriert. Da Änderungen an der Sammlung während der Iteration auf die Kopie angewendet werden, die unabhängig vom Iterator ist, gibt es keine Probleme mit der gleichzeitigen Verwendung.
CopyOnWriteArraySet
Es gibt zwei Möglichkeiten, eine synchronisierte Set zu erstellen:
- Collections.synchronizedSet()
- CopyOnWriteArraySet
Wie der Methodennamen andeutet, ist die Funktionsweise mit CopyOnWriteArrayList bis auf die Datenstruktur fast identisch.
Lesevorgänge
public class CopyOnWriteArraySet extends AbstractSet implements java.io.Serializable {
private final CopyOnWriteArrayList al;
public boolean contains(Object o) {
return al.contains(o);
} Dies ist die contains()-Methode, die zeigt, dass CopyOnWriteArraySet intern CopyOnWriteArrayList definiert und die Methoden von CopyOnWriteArrayList verwendet.
public boolean contains(Object o) {
return indexOf(o) >= 0;
}
public int indexOf(Object o) {
Object[] es = getArray();
return indexOfRange(o, es, 0, es.length);
}
private static int indexOfRange(Object o, Object[] es, int from, int to) {
if (o == null) {
for (int i = from; i < to; i++)
if (es[i] == null)
return i;
} else {
for (int i = from; i < to; i++)
if (o.equals(es[i]))
return i;
}
return -1;Wenn wir uns die contains()-Methode von CopyOnWriteArrayList ansehen, stellen wir fest, dass sie nicht gesperrt ist.
Schreibvorgänge
public class CopyOnWriteArraySet extends AbstractSet implements java.io.Serializable {
private final CopyOnWriteArrayList al;
public boolean add(E e) {
return al.addIfAbsent(e);
} Die add()-Methode verwendet ebenfalls die Methode von CopyOnWriteArrayList.
public boolean addIfAbsent(E e) {
Object[] snapshot = getArray();
return indexOfRange(e, snapshot, 0, snapshot.length) < 0
&& addIfAbsent(e, snapshot);
}
private boolean addIfAbsent(E e, Object[] snapshot) {
synchronized (lock) {
Object[] current = getArray();
int len = current.length;
if (snapshot != current) {
// Optimize for lost race to another addXXX operation
int common = Math.min(snapshot.length, len);
for (int i = 0; i < common; i++)
if (current[i] != snapshot[i]
&& Objects.equals(e, current[i]))
return false;
if (indexOfRange(e, current, common, len) >= 0)
return false;
}
Object[] newElements = Arrays.copyOf(current, len + 1);
newElements[len] = e;
setArray(newElements);
return true;
}Wenn wir uns die addIfAbsent()-Methode ansehen, stellen wir fest, dass sie beim Ausführen eines Schreibvorgangs eine Sperre setzt und das Array kopiert. Daher ist es auch bei CopyOnWriteArraySet, genau wie bei CopyOnWriteArrayList, empfehlenswert, nicht zu viele Schreibvorgänge durchzuführen.
ConcurrentHashMap
Es gibt zwei Möglichkeiten, eine synchronisierte HashMap zu erstellen:
- Collections.synchronizedMap(new HashMap<>())
- ConcurrentHashMap
ConcurrentHashMap ist wie HashMap eine auf Hash basierende Map. Im Vergleich zu synchronizedMap bietet es eine effizientere Möglichkeit, die Gleichzeitigkeit zu gewährleisten.
Vor Java 8 wurde ReentrantLock von Segment geerbt, um die Sperre durch Aufteilung in Bereiche zu gewährleisten.
Ab Java 8 werden die einzelnen Tabellen-Buckets unabhängig voneinander gesperrt. Wenn ein neuer Knoten in einen leeren Bucket eingefügt wird, wird anstelle einer Sperre der CAS-Algorithmus verwendet. Alle anderen Änderungen werden unter Verwendung einer teilweisen Sperre (synchronized block) auf Basis des ersten Knotens des jeweiligen Buckets ausgeführt, um Thread-Konflikte zu minimieren und gleichzeitig die Parallelität zu gewährleisten.
Schauen wir uns den Code der putVal()-Methode an, die einen neuen Knoten in ConcurrentHashMap einfügt, um zu verstehen, wie die Parallelität gewährleistet wird. Dieser Code bezieht sich auf Java 11.
Die putVal()-Methode kann grob in zwei Fälle (insgesamt vier Verzweigungen) unterteilt werden:
- Ein Knoten wird in einen leeren Hash-Bucket eingefügt
- Es ist bereits ein Knoten im Hash-Bucket vorhanden
final V putVal(K key, V value, boolean onlyIfAbsent) {
if (key == null || value == null) throw new NullPointerException();
int hash = spread(key.hashCode());
int binCount = 0;
for (Node[] tab = table;;) {
Node f; int n, i, fh; K fk; V fv;
if (tab == null || (n = tab.length) == 0)
tab = initTable();
// (1)
else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
// (2)
if (casTabAt(tab, i, null, new Node(hash, key, value)))
break;
}
else if ((fh = f.hash) == MOVED)
tab = helpTransfer(tab, f);
else if (onlyIfAbsent // check first node without acquiring lock
&& fh == hash
&& ((fk = f.key) == key || (fk != null && key.equals(fk)))
&& (fv = f.val) != null)
return fv;
// (3)
else {
V oldVal = null;
synchronized (f) {
if (tabAt(tab, i) == f) {
if (fh >= 0) {
binCount = 1;
for (Node e = f;; ++binCount) {
K ek;
// (4)
if (e.hash == hash &&
((ek = e.key) == key ||
(ek != null && key.equals(ek)))) {
oldVal = e.val;
if (!onlyIfAbsent)
e.val = value;
break;
}
Node pred = e;
// (5)
if ((e = e.next) == null) {
pred.next = new Node(hash, key, value);
break;
}
}
}
// (6)
else if (f instanceof TreeBin) {
Node p;
binCount = 2;
if ((p = ((TreeBin)f).putTreeVal(hash, key,
value)) != null) {
oldVal = p.val;
if (!onlyIfAbsent)
p.val = value;
}
}
else if (f instanceof ReservationNode)
throw new IllegalStateException("Recursive update");
}
}
...
}
}
... Ein Knoten wird in einen leeren Hash-Bucket eingefügt
(1) Um einen neuen Knoten einzufügen, wird der Wert des entsprechenden Buckets (tabAt()) abgerufen und geprüft, ob er leer ist.
static final Node tabAt(Node[] tab, int i) {
return (Node)U.getObjectAcquire(tab, ((long)i << ASHIFT) + ABASE); (2) Der volatile Variablen im Knoten wird zugegriffen und mit dem alten Wert (null) verglichen. Wenn sie gleich sind, wird der neue Knoten gespeichert. Wenn sie nicht gleich sind, wird die Schleife for erneut durchlaufen. Dieses Verfahren ist der CAS-Algorithmus.
static final boolean casTabAt(Node[] tab, int i, Node c, Node v) {
return U.compareAndSetObject(tab, ((long)i << ASHIFT) + ABASE, c, v); Mithilfe des CAS-Algorithmus werden Atomaartigkeit und Sichtbarkeitsprobleme gelöst, um die Gleichzeitigkeit zu gewährleisten.
Es ist bereits ein Knoten im Hash-Bucket vorhanden
(3) Wenn bereits ein Knoten vorhanden ist, wird mit einem synchronisierten Block sichergestellt, dass nur ein Thread zugreifen kann. In diesem Fall wird die Sperre auf den nicht leeren Hash-Bucket vom Typ Node
(4) Der neue Knoten wird ersetzt.
(5) Wenn eine Hash-Kollision auftritt, wird sie der separaten Verkettung hinzugefügt.
(6) Wenn eine Hash-Kollision auftritt, wird sie dem Baum hinzugefügt.
Referenz
Erwartete Interviewfragen und Antworten
Was sind die Probleme von Vector, HashTable und Collections.SynchronziedXXX?
Die Klassen Vector, HashTable und SynchronziedXxx verwenden synchronisierte Methoden oder Blöcke und teilen sich ein einziges Sperrobjekt. Daher kann, wenn ein Thread die Sperre für die Sammlung erwirbt, kein anderer Thread alle Methoden verwenden und befindet sich im Sperrzustand. Dies kann zu Leistungseinbußen in der Anwendung führen.
Was ist der Unterschied zwischen SynchronizedList und CopyOnArrayList?
SynchronizedList sperrt die Instanz selbst beim Lesen und Schreiben. CopyOnArrayList hingegen sperrt den entsprechenden Block beim Schreiben und kopiert die Elemente aus dem ursprünglichen Array in ein neues temporäres Array. Anschließend führt es den Schreibvorgang in diesem temporären Array aus, bevor das ursprüngliche Array aktualisiert wird. Dadurch sind Lesevorgänge nicht gesperrt, wodurch CopyOnArrayList eine bessere Leseleistung als SynchronizedList erzielt. Da jedoch ein relativ teurer Kopiervorgang für das Array durchgeführt wird, ist die Schreibgeschwindigkeit von CopyOnArrayList geringer als die von SynchronizedList.
Daher ist es effektiver, CopyOnArrayList zu verwenden, wenn mehr gelesen als geschrieben wird.
Was ist der Unterschied zwischen SynchronizedMap und ConcurrentHashMap?
SynchronziedMap sperrt die Instanz selbst beim Lesen und Schreiben. ConcurrentHashMap hingegen verwendet eine Methode, bei der jeder Tabellen-Bucket unabhängig voneinander gesperrt wird. Wenn ein neuer Knoten in einen leeren Bucket eingefügt wird, wird anstelle einer Sperre (Lock) der CAS-Algorithmus verwendet. Alle anderen Änderungen werden unter Verwendung einer teilweisen Sperre (synchronized block) auf Basis des ersten Knotens des jeweiligen Buckets ausgeführt, um Thread-Konflikte zu minimieren und gleichzeitig die Parallelität zu gewährleisten.
