Проблема параллелизма с массивами (Java)

Question

Для алгоритма, над которым я работаю, я попытался разработать механизм внесения в черный список, который может заносить массивы определенным образом: если «1, 2, 3» занесен в черный список, «1, 2, 3, 4, 5» считается в черном списке.
Я вполне доволен решением, которое я нашел до сих пор. Но, похоже, возникают некоторые серьезные проблемы, когда я получаю доступ к черному списку из нескольких потоков. Метод «содержит» (см. Код ниже) иногда возвращает истину, даже если массив не занесен в черный список. Эта проблема не возникает, если я использую только один поток, поэтому, скорее всего, это проблема параллелизма.
Я попытался добавить синхронизацию, но это ничего не изменило. Я также попробовал несколько отличающиеся реализации, используя классы java.util.concurrent. Есть идеи как это исправить?

public class Blacklist {

private static final int ARRAY_GROWTH = 10;

private final Node root = new Node();

private static class Node{

    private volatile Node[] childNodes = new Node[ARRAY_GROWTH];

    private volatile boolean blacklisted = false;

    public void blacklist(){
        this.blacklisted = true;
        this.childNodes = null;
    }
}

public void add(final int[] array){

    synchronized (root) {

        Node currentNode = this.root;

        for(final int edge : array){
            if(currentNode.blacklisted)
                return;

            else if(currentNode.childNodes.length <= edge) {
                currentNode.childNodes = Arrays.copyOf(currentNode.childNodes, edge + ARRAY_GROWTH);
            }

            if(currentNode.childNodes[edge] == null) {
                currentNode.childNodes[edge] = new Node();
            }

            currentNode = currentNode.childNodes[edge];
        }

        currentNode.blacklist();
    }


}

public boolean contains(final int[] array){

    synchronized (root) {

        Node currentNode = this.root;

        for(final int edge : array){
            if(currentNode.blacklisted)
                return true;

            else if(currentNode.childNodes.length <= edge || currentNode.childNodes[edge] == null)
                return false;

            currentNode = currentNode.childNodes[edge];
        }

        return currentNode.blacklisted;

    }

}

}

Answer 1

Изменить: Я провел ваш код через набор тестов с десятью потоками, добавляющими и сравнивающими тысячи шаблонов, но я не нашел ничего плохого в вашей реализации. Я полагаю, что вы неверно истолковываете свои данные. Например, в многопоточной среде это иногда возвращает false:

// sometimes this can be false
blacklist.contains(pattern) == blacklist.contains(pattern);

Другой поток изменил черный список после первого вызова, но до второго вызова. Это нормальное поведение, и сам класс не может ничего сделать, чтобы остановить его. Если это не то поведение, которое вам нужно, вы можете синхронизировать его извне класса:

synchronized (blacklist) {
    // this will always be true
    blacklist.contains(pattern) == blacklist.contains(pattern);
}

Оригинальный ответ:
Вы синхронизируете корневой узел, но он не синхронизирует ни одного из его дочерних узлов. Все, что вам нужно сделать, чтобы сделать ваш класс пуленепробиваемым, это синхронизировать методы add(int[]) и contains(int[]), а затем не пропускать ссылки. Это гарантирует, что только один поток может когда-либо использовать объект черного списка одновременно.

Я возился с вашим кодом, пытаясь разобраться в нем, так что вы могли бы также иметь его:

import java.util.HashMap;
import java.util.Map;
import java.util.Stack;

public class Blacklist {
    private final Node root = new Node(Integer.MIN_VALUE, false);

    public synchronized void add(int[] array) {
        if (array == null) return;
        Node next, cur = root;

        for(int i = 0; i < array.length-1 && !cur.isLeaf(); i++) {
            next = cur.getChild(array[i]);

            if (next == null) { 
                next = new Node(array[i], false);
                cur.addChild(next);
            }

            cur = next;
        }

        if (!cur.isLeaf()) {
            next = cur.getChild(array[array.length-1]); 
            if (next == null || !next.isLeaf())
                cur.addChild(new Node(array[array.length-1], true));
        }
    }

    public synchronized boolean contains(int[] array) {
        if (array == null) return false;
        Node cur = root;

        for (int i = 0; i < array.length; i++) {
            cur = cur.getChild(array[i]);
            if (cur == null) return false;
            if (cur.isLeaf()) return true;
        }

        return false;
    }

    private static class Node {
        private final Map<Integer, Node> children; 
        private final int value;

        public Node(int _value, boolean leaf) { 
            children = (leaf?null:new HashMap<Integer, Node>());
            value = _value;
        }

        public void addChild(Node child) { children.put(child.value, child); }
        public Node getChild(int value) { return children.get(value); }
        public boolean isLeaf() { return (children == null); }

    }
}

Рамка Collections может упростить вам задачу. Вы не делаете себе никаких одолжений, переопределяя ArrayList.

Здесь я использую HashMap, чтобы вам не нужно было выделять более 9000 ссылок для чего-то вроде этого:

blacklist.add(new int[] {1, 2000, 3000, 4000});