Gibt es eine gleichzeitige Liste im JDK von Java?

Question

Wie kann ich eine gleichzeitige Listeninstanz erstellen, bei der ich auf Elemente nach Index zugreifen kann? Verfügt das JDK über Klassen oder Fabrikmethoden, die ich verwenden kann?

Answer 1

CopyOnWriteArrayList ist eine thread-sichere Variante von ArrayList, bei der alle mutativen Operationen (Hinzufügen, Setzen und so weiter eine neue Kopie des zugrunde liegenden Arrays erstellt wird.

CopyOnWriteArrayList ist eine gleichzeitige Alternative zu synchronisierten List implementiert List-Schnittstelle und seine Teil von java.util.concurrent packageand seine Thread-sichere Sammlung.

public class CopyOnWriteArrayList<E>
    implements List<E>, RandomAccess, Cloneable, java.io.Serializable

CopyOnWriteArrayList ist ausfallsicher und löst keine ConcurrentModificationException aus, wenn die zugrundeliegende CopyOnWriteArrayList während der Iteration geändert wird, indem eine separate Kopie von ArrayList verwendet wird.

Dies ist normalerweise zu kostspielig, da bei jedem Aktualisierungsvorgang eine geklonte Kopie erstellt wird. CopyOnWriteArrayList ist die beste Wahl nur für häufige Lesevorgänge.

/**
         * 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

Answer 2

Wenn Sie nie vorhaben, Elemente aus der Liste zu löschen (da dies eine Änderung des Index aller Elemente nach dem gelöschten Element erfordert), dann können Sie ConcurrentSkipListMap<Integer, T> anstelle von ArrayList<T> z.B.

NavigableMap<Integer, T> map = new ConcurrentSkipListMap<>();

So können Sie am Ende der "Liste" Elemente wie folgt hinzufügen, Solange es nur einen Schreibfaden gibt (andernfalls gibt es eine Wettlaufsituation zwischen map.size() y map.put() ):

// Add item to end of the "list":
map.put(map.size(), item);

Sie können natürlich auch den Wert eines beliebigen Elements in der "Liste" (d. h. der Karte) ändern, indem Sie einfach map.put(index, item) .

Die durchschnittlichen Kosten für das Einfügen von Elementen in die Karte oder das Abrufen von Elementen nach Index sind O(log(n)) und ConcurrentSkipListMap ist sperrfrei, was es deutlich besser macht als etwa Vector (die alte synchronisierte Version von ArrayList ).

Sie können die "Liste" vorwärts und rückwärts durchlaufen, indem Sie die Methoden der NavigableMap Schnittstelle.

Sie könnten all das in eine Klasse packen, die die List Schnittstelle, vorausgesetzt, Sie verstehen die Vorbehalte gegen Wettlaufbedingungen (oder Sie könnten nur die Writer-Methoden synchronisieren) -- und Sie müssten eine nicht unterstützte Operationsausnahme für die remove Methoden. Um alle erforderlichen Methoden zu implementieren, ist eine ganze Menge Boilerplate erforderlich, aber hier ist ein schneller Versuch einer Implementierung.

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();
    }
}

Vergessen Sie nicht, dass Sie auch bei der oben gezeigten Synchronisierung mit dem Writer-Thread darauf achten müssen, dass keine Race Conditions auftreten, die zum Fallenlassen von Elementen führen könnten, wenn Sie z. B. versuchen, eine Liste in einem Reader-Thread zu durchlaufen, während ein Writer-Thread gerade das Ende der Liste ergänzt.

Sie können sogar ConcurrentSkipListMap als Liste mit zwei Enden, solange der Schlüssel der einzelnen Elemente nicht die tatsächliche Position innerhalb der Liste repräsentieren muss (d.h. das Hinzufügen am Anfang der Liste weist den Elementen negative Schlüssel zu). (Auch hier gilt der Vorbehalt der Race Condition, d. h. es sollte nur einen Writer-Thread geben).

// 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);

Answer 3

Wenn Sie eine gleichzeitige Liste benötigen, die sich innerhalb eines Modellobjekts befindet (da Sie keine abstrakten Datentypen wie eine Liste verwenden sollten, um einen Knoten in einem Anwendungsmodellgraphen darzustellen) oder Teil eines bestimmten Dienstes ist, können Sie den Zugriff selbst synchronisieren.

class MyClass {
  List<MyType> myConcurrentList = new ArrayList<>();
  void myMethod() {
    synchronzied(myConcurrentList) {
      doSomethingWithList;
    }
  }
}

Oft reicht das schon aus, um Sie in Schwung zu bringen. Wenn Sie iterieren müssen, iterieren Sie über eine Kopie der Liste, nicht über die Liste selbst, und synchronisieren Sie nur den Teil, in dem Sie die Liste kopieren, nicht während Sie über sie iterieren.

Auch bei der gleichzeitigen Arbeit an einer Liste tun Sie in der Regel etwas mehr als nur das Hinzufügen oder Entfernen oder Kopieren, was bedeutet, dass die Operation sinnvoll genug wird, um eine eigene Methode zu rechtfertigen, und die Liste wird Mitglied einer speziellen Klasse, die nur diese bestimmte Liste mit Thread-sicheres Verhalten.

Auch wenn ich zustimme, dass eine gleichzeitige Liste Implementierung benötigt wird und Vector / Collections.sychronizeList(list) nicht den Trick tun, wie sicher Sie etwas wie compareAndAdd oder compareAndRemove oder get(..., ifAbsentDo) benötigen, auch wenn Sie eine ConcurrentList-Implementierung haben Entwickler oft Bugs einführen, indem Sie nicht berücksichtigen, was die wahre Transaktion bei der Arbeit mit einer gleichzeitigen Listen (und Karten) ist.

Diese Szenarien, in denen die Transaktionen zu klein sind für das, was der beabsichtigte Zweck der Interaktion mit einem gleichzeitigen ADT (abstrakter Datentyp) immer dazu führen, dass ich die Liste in einer speziellen Klasse verstecken und synchronisieren Zugriff auf diese Klasse Objekte Methode mit der synchronisierten auf der Methodenebene. Das ist der einzige Weg, um sicher zu sein, dass die Transaktionen korrekt sind.

Ich habe zu viele Fehler gesehen, um es anders zu machen - zumindest, wenn der Code wichtig ist und etwas wie Geld oder Sicherheit behandelt oder einige Maßnahmen zur Dienstqualität garantiert (z. B. das Senden von Nachrichten mindestens einmal und nur einmal).