Problème de concurrence avec les tableaux (Java)

Question

Pour un algorithme sur lequel je travaille, j'ai essayé de développer un mécanisme de liste noire qui peut blacklister des tableaux d'une manière spécifique: Si "1, 2, 3" est sur liste noire "1, 2, 3 , 4, 5 "est également considéré comme sur liste noire.
Je suis assez content de la solution que j'ai trouvée jusqu'à présent. Mais il semble y avoir de sérieux problèmes lorsque j'accède à une liste noire à partir de plusieurs threads. La méthode "contient" (voir le code ci-dessous) renvoie parfois la valeur true, même si un tableau n'est pas sur liste noire. Ce problème ne se produit pas si je n'utilise qu'un seul thread, il s'agit donc probablement d'un problème de concurrence.
J'ai essayé d'ajouter une synchronisation, mais cela n'a rien changé. J'ai également essayé quelques implémentations légèrement différentes en utilisant les classes java.util.concurrent. Des idées pour résoudre le problème?

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: j'ai couru votre code par une suite de test avec dix fils en ajoutant et en comparant des milliers de modèles, mais je ne pouvais trouver rien de mal à votre mise en œuvre. Je crois que vous interprétez mal vos données. Par exemple, dans un environnement fileté ce retourne parfois faux:

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

Un autre thread a modifié la liste noire entre après le premier appel, mais avant le second appel. C'est un comportement normal et la classe elle-même ne peut rien faire pour l'arrêter. Si ce n'est pas le comportement que vous voulez, vous pouvez synchroniser de l'extérieur de la classe:

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

réponse originale:
Vous synchronisez le noeud racine, mais cela ne se synchronisent pas de ses enfants . Tout ce que vous avez à faire pour rendre votre classe à l'épreuve des balles est de synchroniser les méthodes add(int[]) et contains(int[]) et de ne laisser échapper aucune référence. Cela garantit qu'un seul thread peut jamais utiliser un objet liste noire en même temps.

Je tripoté avec votre code tout en essayant de donner un sens, alors vous pourriez aussi bien avoir:

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

    } 
} 

Le Collections framework peut rendre les choses beaucoup plus facile pour vous. Vous ne vous faites aucune faveur en réimplémentant ArrayList.

Ici, j'utiliser un HashMap afin que vous n'avez pas d'allouer plus de 9000 références pour quelque chose comme ceci:

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