Y a-t-il une liste concurrente dans la JDK de Java?

Question

Comment puis-je créer une instance de Liste concurrentielle, où je peux accéder aux éléments par index? Le JDK a-t-il des classes ou des méthodes d'usine que je peux utiliser?

Answer 1

CopyOnWriteArrayList est une variante thread-safe de ArrayList dans laquelle toutes les opérations mutatives (ajout, modification, etc.) sont implémentées en faisant une copie fraîche du tableau sous-jacent.

CopyOnWriteArrayList est une alternative concurrente de List synchronisée implémentant l'interface List et faisant partie du package java.util.concurrent et c'est une collection thread-safe.

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

CopyOnWriteArrayList est fail-safe et ne lance pas ConcurrentModificationException lorsque CopyOnWriteArrayList sous-jacent est modifié pendant l'itération, utilise une copie séparée de ArrayList.

Cela est généralement trop coûteux car une copie de tableau est créée à chaque opération de mise à jour. CopyOnWriteArrayList est le meilleur choix uniquement pour une opération de lecture fréquente.

/**
         * Renvoie une copie superficielle de cette liste. (Les éléments eux-mêmes
         * ne sont pas copiés.)
         *
         * @return un clone de cette liste
         */
        public Object clone() {
            try {
                @SuppressWarnings("unchecked")
                CopyOnWriteArrayList clone =
                    (CopyOnWriteArrayList) super.clone();
                clone.resetLock();
                return clone;
            } catch (CloneNotSupportedException e) {
                // cela ne devrait pas se produire, puisque nous sommes 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

Si vous ne prévoyez jamais de supprimer des éléments de la liste (car cela nécessite de modifier l'index de tous les éléments après l'élément supprimé), vous pouvez utiliser la fonction ConcurrentSkipListMap<Integer, T> à la place de ArrayList<T> par exemple

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

Cela vous permettra d'ajouter des éléments à la fin de la "liste" comme suit, tant qu'il n'y a qu'un seul fil d'écriture (sinon il y a une condition de course entre map.size() y map.put() ) :

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

Vous pouvez aussi évidemment modifier la valeur de n'importe quel élément de la "liste" (c'est-à-dire de la carte) en appelant tout simplement map.put(index, item) .

Le coût moyen pour placer des éléments dans la carte ou les récupérer par index est O(log(n)), et ConcurrentSkipListMap est libre de tout verrou, ce qui le rend nettement meilleur que, par exemple, le programme Vector (l'ancienne version synchronisée de ArrayList ).

Vous pouvez itérer en avant et en arrière dans la "liste" en utilisant les méthodes de l'objet NavigableMap interface.

Vous pourriez regrouper tout ce qui précède dans une classe qui implémente la fonction List pour autant que vous compreniez les avertissements relatifs aux conditions de course (ou vous pourriez synchroniser uniquement les méthodes d'écriture) - et vous devriez lever une exception d'opération non prise en charge pour l'interface remove méthodes. L'implémentation de toutes les méthodes requises nécessite un certain nombre d'éléments standard, mais voici une tentative rapide d'implémentation.

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

N'oubliez pas que, même avec la synchronisation du fil d'écriture comme indiqué ci-dessus, vous devez veiller à ne pas créer de conditions de course qui pourraient vous faire perdre des éléments, si par exemple vous essayez d'itérer dans une liste dans un fil de lecture pendant qu'un fil d'écriture ajoute à la fin de la liste.

Vous pouvez même utiliser ConcurrentSkipListMap comme une liste à deux extrémités, tant que vous n'avez pas besoin que la clé de chaque élément représente la position réelle dans la liste (c'est-à-dire que l'ajout au début de la liste attribuera aux éléments des clés négatives). (La même mise en garde concernant les conditions de course s'applique ici, c'est-à-dire qu'il ne doit y avoir qu'un seul fil d'écriture).

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

La plupart du temps, si vous avez besoin d'une liste concurrente, elle se trouve à l'intérieur d'un objet modèle (car vous ne devriez pas utiliser des types de données abstraits tels qu'une liste pour représenter un nœud dans un graphe de modèle d'application) ou elle fait partie d'un service particulier, vous pouvez synchroniser l'accès vous-même.

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

En général, cela suffit pour avancer. Si vous avez besoin d'itérer, itérez sur une copie de la liste et pas sur la liste elle-même, et synchronisez uniquement la partie où vous copiez la liste et pas pendant que vous itérez dessus.

Aussi, lorsque vous travaillez de manière concurrente sur une liste, vous faites généralement plus que simplement ajouter, supprimer ou copier, ce qui signifie que l'opération devient suffisamment significative pour justifier sa propre méthode et que la liste devient un membre d'une classe spéciale représentant uniquement cette liste particulière avec un comportement sûr pour les threads.

Même si je suis d'accord qu'une implémentation de liste concurrente est nécessaire et que Vector / Collections.sychronizeList(list) ne font pas l'affaire car vous avez sûrement besoin de quelque chose comme compareAndAdd ou compareAndRemove ou get(..., ifAbsentDo), même si vous avez une implémentation ConcurrentList les développeurs introduisent souvent des bugs en ne tenant pas compte de ce qui constitue la véritable transaction lors de l'utilisation de listes (et maps) concurrentes.

Ces scénarios où les transactions sont trop petites par rapport à l'objectif prévu de l'interaction avec un TDA (type de données abstrait) concurrent m'ont toujours amené à cacher la liste dans une classe spéciale et à synchroniser l'accès aux méthodes de cet objet de classe en utilisant la synchronisation au niveau de la méthode. C'est le seul moyen d'être sûr que les transactions sont correctes.

J'ai vu trop de bugs pour faire autrement - du moins si le code est important et gère quelque chose comme de l'argent ou de la sécurité ou garantit certaines mesures de qualité de service (par exemple, envoyer un message au moins une fois et une seule fois).