CODEWITHSUNDEEP
java
Linda Li
Linda Li

Reputation: 11

Why does this code NOT throw a ConcurrentModificationException?

I'm trying to understand why some of my code doesn't throw a ConcurrentModificationException. I am looping through elements of a Set and then adding more elements to the set, but I expected an exception.

Problem: Given a directed tree, return true if two given nodes have a common ancestor. Note this is not a rooted tree (i.e. a tree with one root). We are given edge pairs that are (parent, child). Nodes have unique IDs. 

import java.io.*;
import java.util.*;


class Solution {
  public static void main(String[] args) {
    int[][] pairs = {{11,6},{9,6},{9,8},{10,8}, {6,2},{5,2},{5,1},{8,3},{8,4}};

    System.out.println(hasCommonAncestor(pairs, 3,4));
    System.out.println(hasCommonAncestor(pairs, 2,4));    
    System.out.println(hasCommonAncestor(pairs, 1,3));
    System.out.println(hasCommonAncestor(pairs, 6,8));    

  }


  private static boolean hasCommonAncestor(int[][] pairs, int a, int b) {
    Map<Integer, Set<Integer>> firstLevelParents = new HashMap<>();

    for(int[] pair : pairs) {
      int parent = pair[0];
      int child = pair[1];
      Set<Integer> parents = firstLevelParents.getOrDefault(child, new HashSet<>());
      parents.add(parent);
      firstLevelParents.put(child, parents);
    }


    Set<Integer> aParents = firstLevelParents.get(a);
    Set<Integer> bParents = firstLevelParents.get(b);

    for(Integer parent : aParents) {
      Set<Integer> parentsParents = firstLevelParents.getOrDefault(parent, new HashSet<>());
      aParents.addAll(parentsParents);
    }

    for(Integer parent : bParents) {
      Set<Integer> parentsParents = firstLevelParents.getOrDefault(parent, new HashSet<>());
      bParents.addAll(parentsParents);
    }


    return aParents.removeAll(bParents);
  }
}

Upvotes: 1

Views: 81

Answers (1)

kingkupps
kingkupps

Reputation: 3494

This code may still throw a ConcurrentModificationException under certain inputs. From the Javadoc for the exception:

Note that fail-fast behavior cannot be guaranteed as it is, generally speaking, impossible to make any hard guarantees in the presence of unsynchronized concurrent modification. Fail-fast operations throw ConcurrentModificationException on a best-effort basis. Therefore, it would be wrong to write a program that depended on this exception for its correctness: ConcurrentModificationException should be used only to detect bugs.

As an example, this code works fine:

public final class Main {

    public static void main(String[] args) {
        Set<Integer> numbers = new HashSet<>();
        numbers.add(1);
        numbers.add(2);
        numbers.add(3);

        for (Integer n : numbers) {
            numbers.add(n + 1);
        }

        System.out.println(numbers); // [1, 2, 3, 4]
    }
}

But this will throw a ConcurrentModificationException:

public final class Main {

    public static void main(String[] args) {
        Set<Integer> numbers = new HashSet<>();
        numbers.add(1);
        numbers.add(2);
        numbers.add(3);

        for (Integer n : numbers) {
            // Changed 1 to a 10.
            numbers.add(n + 10);
        }

        System.out.println(numbers);
    }
}

In other words, some paths of your code may lead to a ConcurrentModificationException but others may not and you should not depend on this result.

Upvotes: 2

Related Questions