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

Question

Для алгоритма, над которым я работаю, я попытался разработать механизм черного списка, который может черным списком массивов определенным образом: если «1, 2, 3» занесено в черный список «1, 2, 3» , 4, 5 "также считается внесенным в черный список.
Я доволен решением, которое я придумал до сих пор. Но, похоже, есть некоторые серьезные проблемы, когда я получаю доступ к черному списку из нескольких потоков. Метод «содержит» (см. Код ниже) иногда возвращает true, даже если массив не внесен в черный список. Эта проблема не возникает, если я использую только один поток, поэтому, скорее всего, это проблема параллелизма.
Я попытался добавить некоторую синхронизацию, но ничего не изменил. Я также пробовал несколько несколько разных реализаций с использованием классов 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

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

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

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

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

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

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

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 framework может сделать вещи намного проще для вас. Вы не делаете никаких выгод, переопределяя ArrayList.

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

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