數組併發問題（Java）

Question

對於我正在處理的算法，我試圖開發一個黑名單機制，可以以特定方式將數組列入黑名單：如果「1,2,3」被列入黑名單「1,2,3 ，4，5「也被列入黑名單。
我很滿意迄今爲止所提出的解決方案。但是當我從多個線程訪問黑名單時，似乎存在一些嚴重的問題。即使數組未被列入黑名單，方法「contains」（見下面的代碼）有時也會返回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

編輯： 我跑你的代碼通過測試套件有十個線程添加和比較千種圖案，但我能找到什麼不對您的實現。我相信你誤解了你的數據。例如，在一個線程環境中，這有時會返回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 framework可以讓事情更容易爲你。通過重新實現ArrayList，你沒有做任何好處。

這裏我用一個HashMap，這樣你就不必分配了這樣的事情在9000參考資料：

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