Hoe kan ik een gelijktijdige List-instantie maken, waar ik toegang heb tot elementen per index? Heeft de JDK klassen of fabrieksmethoden die ik kan gebruiken?
Antwoord 1, autoriteit 100%
Er is een gelijktijdige lijstimplementatie in java.util.concurrent. CopyOnWriteArrayListin het bijzonder.
Antwoord 2, autoriteit 90%
ConcurrentLinkedQueue
Als u niet geïnteresseerd bent in toegang op basis van indexen en alleen de kenmerken van een lijst wilt die de volgorde van invoegen behouden, kunt u een java.util.concurrent.ConcurrentLinkedQueue. Omdat het Iterable implementeert, kun je, zodra je klaar bent met het toevoegen van alle items, de inhoud doorlopen met de verbeterde syntaxis:
Queue<String> globalQueue = new ConcurrentLinkedQueue<String>();
//Multiple threads can safely call globalQueue.add()...
for (String href : globalQueue) {
//do something with href
}
Antwoord 3, autoriteit 73%
Je kunt heel goed Collections gebruiken .synchronizedList(List)als alles wat je nodig hebt een eenvoudige aanroepsynchronisatie is:
List<Object> objList = Collections.synchronizedList(new ArrayList<Object>());
Antwoord 4, autoriteit 27%
Omdat het verkrijgen van de positie en het verkrijgen van het element van de gegeven positie natuurlijk enige vergrendeling vereist (je kunt niet hebben dat de lijst structurele veranderingen heeft tussen die twee bewerkingen).
Het idee van een gelijktijdige verzameling is dat elke bewerking op zich atomair is en kan worden uitgevoerd zonder expliciete vergrendeling/synchronisatie.
Daarom is het niet zo logisch om het element op positie nuit een gegeven Listte halen als een atomaire operatie in een situatie waarin gelijktijdige toegang wordt verwacht.
p>
Antwoord 5, autoriteit 14%
Je hebt deze opties:
-
Collections.synchronizedList(): u kunt elke implementatie vanListinpakken (ArrayList,LinkedListof een lijst van derden). Toegang tot elke methode (lezen en schrijven) wordt beveiligd metsynchronized. Wanneer uiterator()of verbeterde for loop gebruikt, moet u de hele iteratie handmatig synchroniseren. Tijdens het itereren worden andere threads volledig geblokkeerd, zelfs niet voor lezen. Je kunt ook apart synchroniseren voor elkehasNextennextaanroep, maar dan isConcurrentModificationExceptionmogelijk. -
CopyOnWriteArrayList: het is duur om aan te passen, maar wacht-vrij om te lezen. Iterators gooien nooitConcurrentModificationException, ze retourneren een momentopname van de lijst op het moment dat de iterator wordt gemaakt, zelfs als de lijst wordt gewijzigd door een andere thread tijdens het itereren. Handig voor niet vaak bijgewerkte lijsten. Bulkbewerkingen zoalsaddAllhebben de voorkeur voor updates – de interne array wordt minder vaak gekopieerd. -
Vector: lijkt erg opsynchronizedList(new ArrayList<>()), maar iteratie is ook gesynchroniseerd. Iterators kunnen echterConcurrentModificationExceptiongooien als de vector tijdens het itereren door een andere thread wordt gewijzigd.
Andere opties:
QueueofDequekan een alternatief zijn als u alleen aan het einde van de lijst toevoegt/verwijdert of deze herhaalt.Queuestaat alleen toevoegen aan het ene uiteinde toe en verwijderen aan het andere uiteinde,Dequestaat toevoegen en verwijderen aan beide uiteinden toe. Er is geen toegang via index. Er zijn meerdere implementaties met betere gelijktijdigheidseigenschappen dan welkeListdan ook kan bieden. Kijk naar “Alle bekende implementatieklassen” in de Wachtrij javadoc, de implementaties in het pakketjava.util.concurrentzijn gelijktijdig. Je kunt ook een kijkje nemen op JCTools, het bevat snellere wachtrij-implementaties die gespecialiseerd zijn voor één consument of één producent.Collections.unmodifiableList(): WAK-FREE, Draadveilig, maar niet-modificeerbaarList.of& amp;List.copyOf: een ander Niet-modificeerbare lijst in Java 9 en hoger.
Antwoord 6, Autoriteit 2%
COPICOONWRAYARAYLIST is een draadveilige variant van Arrayclist waarin
Alle mutatieve operaties (toevoegen, ingesteld, enzovoort) worden geïmplementeerd door
Een verse kopie van de onderliggende array maken.
COPICAONWRIKEARLAYLIST is een gelijktijdig alternatief voor gesynchroniseerde lijst implementeert lijstinterface en het deel van Java.Util.Concurrent PackageAND zijn een draadveilige collectie.
public class CopyOnWriteArrayList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable
COPICAONWRIKEARLAYLIST is fail-safe en gooft geen concurrentmodificationException wanneer onderliggende copyonwriterraylist is gewijzigd tijdens iteratie Gebruik een apart exemplaar van arrayclist.
Dit is gewoonlijk te duur omdat kopieerarray betrof elke update-operatie een gekloonde kopie wordt gemaakt. COPICAONWRAYARAYLIST is de beste keuze alleen voor frequente leesbewerking.
/**
* Returns a shallow copy of this list. (The elements themselves
* are not copied.)
*
* @return a clone of this list
*/
public Object clone() {
try {
@SuppressWarnings("unchecked")
CopyOnWriteArrayList<E> clone =
(CopyOnWriteArrayList<E>) super.clone();
clone.resetLock();
return clone;
} catch (CloneNotSupportedException e) {
// this shouldn't happen, since we are Cloneable
throw new InternalError();
}
}
-
http://gee.cs.oswego.edu/dl/classes/EDU/oswego/cs/dl/util/concurrent/CopyOnWriteArrayList.html
-
https:// docs.oracle.com/javase/9/docs/api/java/util/concurrent/CopyOnWriteArrayList.html
- https://www .logicbig.com/tutorials/core-java-tutorial/java-collections/concurrent-collection-cheatsheet.html
Antwoord 7
Als u nooit van plan bent om elementen uit de lijst te verwijderen (omdat hiervoor de index van alle elementen na het verwijderde element moet worden gewijzigd), kunt u ConcurrentSkipListMap<Integer, T>gebruiken in plaats van ArrayList<T>, bijv.
NavigableMap<Integer, T> map = new ConcurrentSkipListMap<>();
Hierdoor kunt u als volgt items aan het einde van de “lijst” toevoegen, zolang er maar één schrijverthread is(anders is er een race-conditie tussen map.size()en map.put()):
// Add item to end of the "list":
map.put(map.size(), item);
Je kunt natuurlijk ook de waarde van elk item in de “lijst” (d.w.z. de kaart) wijzigen door simpelweg map.put(index, item)aan te roepen.
De gemiddelde kosten om items op de kaart te zetten of ze op te halen via index zijn O(log(n)), en ConcurrentSkipListMapis lock-free, wat het aanzienlijk beter maakt dan bijvoorbeeld Vector(de oude gesynchroniseerde versie van ArrayList).
Je kunt heen en weer door de “lijst” bladeren met behulp van de methoden van de NavigableMap-interface.
Je zou al het bovenstaande kunnen inpakken in een klasse die de List-interface implementeert, zolang je de voorbehouden voor racecondities begrijpt (of je zou alleen de schrijversmethoden kunnen synchroniseren) — en je zou om een niet-ondersteunde bewerkingsuitzondering te genereren voor de remove-methoden. Er is nogal wat standaardwerk nodig om alle vereiste methoden te implementeren, maar hier is een snelle poging tot implementatie.
import java.util.Collection;
import java.util.Iterator;
import java.util.List;
import java.util.ListIterator;
import java.util.NavigableMap;
import java.util.Objects;
import java.util.Map.Entry;
import java.util.concurrent.ConcurrentSkipListMap;
public class ConcurrentAddOnlyList<V> implements List<V> {
private NavigableMap<Integer, V> map = new ConcurrentSkipListMap<>();
@Override
public int size() {
return map.size();
}
@Override
public boolean isEmpty() {
return map.isEmpty();
}
@Override
public boolean contains(Object o) {
return map.values().contains(o);
}
@Override
public Iterator<V> iterator() {
return map.values().iterator();
}
@Override
public Object[] toArray() {
return map.values().toArray();
}
@Override
public <T> T[] toArray(T[] a) {
return map.values().toArray(a);
}
@Override
public V get(int index) {
return map.get(index);
}
@Override
public boolean containsAll(Collection<?> c) {
return map.values().containsAll(c);
}
@Override
public int indexOf(Object o) {
for (Entry<Integer, V> ent : map.entrySet()) {
if (Objects.equals(ent.getValue(), o)) {
return ent.getKey();
}
}
return -1;
}
@Override
public int lastIndexOf(Object o) {
for (Entry<Integer, V> ent : map.descendingMap().entrySet()) {
if (Objects.equals(ent.getValue(), o)) {
return ent.getKey();
}
}
return -1;
}
@Override
public ListIterator<V> listIterator(int index) {
return new ListIterator<V>() {
private int currIdx = 0;
@Override
public boolean hasNext() {
return currIdx < map.size();
}
@Override
public V next() {
if (currIdx >= map.size()) {
throw new IllegalArgumentException(
"next() called at end of list");
}
return map.get(currIdx++);
}
@Override
public boolean hasPrevious() {
return currIdx > 0;
}
@Override
public V previous() {
if (currIdx <= 0) {
throw new IllegalArgumentException(
"previous() called at beginning of list");
}
return map.get(--currIdx);
}
@Override
public int nextIndex() {
return currIdx + 1;
}
@Override
public int previousIndex() {
return currIdx - 1;
}
@Override
public void remove() {
throw new UnsupportedOperationException();
}
@Override
public void set(V e) {
// Might change size of map if currIdx == map.size(),
// so need to synchronize
synchronized (map) {
map.put(currIdx, e);
}
}
@Override
public void add(V e) {
synchronized (map) {
// Insertion is not supported except at end of list
if (currIdx < map.size()) {
throw new UnsupportedOperationException();
}
map.put(currIdx++, e);
}
}
};
}
@Override
public ListIterator<V> listIterator() {
return listIterator(0);
}
@Override
public List<V> subList(int fromIndex, int toIndex) {
// TODO Auto-generated method stub
return null;
}
@Override
public boolean add(V e) {
synchronized (map) {
map.put(map.size(), e);
return true;
}
}
@Override
public boolean addAll(Collection<? extends V> c) {
synchronized (map) {
for (V val : c) {
add(val);
}
return true;
}
}
@Override
public V set(int index, V element) {
synchronized (map) {
if (index < 0 || index > map.size()) {
throw new IllegalArgumentException("Index out of range");
}
return map.put(index, element);
}
}
@Override
public void clear() {
synchronized (map) {
map.clear();
}
}
@Override
public synchronized void add(int index, V element) {
synchronized (map) {
if (index < map.size()) {
// Insertion is not supported except at end of list
throw new UnsupportedOperationException();
} else if (index < 0 || index > map.size()) {
throw new IllegalArgumentException("Index out of range");
}
// index == map.size()
add(element);
}
}
@Override
public synchronized boolean addAll(
int index, Collection<? extends V> c) {
synchronized (map) {
if (index < map.size()) {
// Insertion is not supported except at end of list
throw new UnsupportedOperationException();
} else if (index < 0 || index > map.size()) {
throw new IllegalArgumentException("Index out of range");
}
// index == map.size()
for (V val : c) {
add(val);
}
return true;
}
}
@Override
public boolean remove(Object o) {
throw new UnsupportedOperationException();
}
@Override
public V remove(int index) {
throw new UnsupportedOperationException();
}
@Override
public boolean removeAll(Collection<?> c) {
throw new UnsupportedOperationException();
}
@Override
public boolean retainAll(Collection<?> c) {
throw new UnsupportedOperationException();
}
}
Vergeet niet dat zelfs met de threadsynchronisatie van de schrijver zoals hierboven weergegeven, u moet oppassen dat u niet in race-omstandigheden terechtkomt die ertoe kunnen leiden dat u items laat vallen, als u bijvoorbeeld probeert een lijst in een reader te doorlopen thread terwijl een schrijverthread wordt toegevoegd aan het einde van de lijst.
U kunt zelfs ConcurrentSkipListMapgebruiken als een dubbele lijst, zolang u niet de sleutel van elk item nodig heeft om de werkelijke positie in de lijst weer te geven (dwz toevoegen aan het begin van de lijst zal items negatieve sleutels toewijzen). (Dezelfde waarschuwing voor racecondities is hier van toepassing, d.w.z. er zou maar één schrijversthread moeten zijn.)
// Add item after last item in the "list":
map.put(map.isEmpty() ? 0 : map.lastKey() + 1, item);
// Add item before first item in the "list":
map.put(map.isEmpty() ? 0 : map.firstKey() - 1, item);
Antwoord 8
Meestal als u een gelijktijdige lijst nodig heeft, bevindt deze zich in een modelobject (omdat u geen abstracte gegevenstypen zoals een lijst moet gebruiken om een knooppunt in een applicatiemodelgrafiek weer te geven) of als het onderdeel is van een bepaalde service, kunt u synchroniseren de toegang zelf.
class MyClass {
List<MyType> myConcurrentList = new ArrayList<>();
void myMethod() {
synchronzied(myConcurrentList) {
doSomethingWithList;
}
}
}
Vaak is dit voldoende om u op weg te helpen. Als je moet herhalen, herhaal dan een kopie van de lijst, niet de lijst zelf, en synchroniseer alleen het deel waar je de lijst kopieert, niet terwijl je eroverheen herhaalt.
Ook wanneer u gelijktijdig aan een lijst werkt, doet u meestal meer dan alleen toevoegen, verwijderen of kopiëren, wat betekent dat de bewerking zinvol genoeg wordt om zijn eigen methode te vragen en de lijst lid wordt van een speciale klasse die alleen deze specifieke lijst vertegenwoordigt met thread veilig gedrag.
Zelfs als ik het ermee eens ben dat een gelijktijdige lijstimplementatie nodig is en Vector / Collections.sychronizeList(list) niet voldoende is, omdat je zeker iets nodig hebt als CompareAndAdd of CompareAndRemove of get(…, ifAbsentDo), zelfs als je hebt een ConcurrentList-implementatie ontwikkelaars introduceren vaak bugs door niet te overwegen wat de echte transactie is bij het werken met gelijktijdige lijsten (en kaarten).
Deze scenario’s waarin de transacties te klein zijn voor wat het beoogde doel van de interactie met een gelijktijdige ADT (abstract gegevenstype) er altijd toe leidt dat ik de lijst in een speciale klasse verberg en de toegang tot deze klasseobjecten synchroniseer met behulp van de gesynchroniseerde op methodeniveau. Het is de enige manier om er zeker van te zijn dat de transacties correct zijn.
Ik heb te veel bugs gezien om het op een andere manier te doen – tenminste als de code belangrijk is en iets als geld of beveiliging afhandelt of bepaalde kwaliteit van de service-maatregelen garandeert (bijvoorbeeld het verzenden van een bericht ten minste één keer en slechts één keer).