Equality in Set<Set> Java

Question

I have a method that returns Set<Set<String>>. In my test, I am trying to check if the expected Sets are present using contains() method.

eg. input = "cat", "dog", "god"

output = [[cat], [dog, god]]

Now, if I do output.contains(new HashSet<>(Arrays.asList("cat"))) it returns true.

But if I do output.contains(new HashSet<>(Arrays.asList("dog", "god"))) it returns false.

According to my understanding, it should return true in both cases.

What am I missing here?

public class AnagramGroups {
     public Set<Set<String>> group(Set<String> words) {
         Set<Set<String>> groups = new HashSet<>();
         for(String word: words) {
             findAndAdd(word, groups);
         }
         return groups;
     }

     private void findAndAdd(String word, Set<Set<String>> groups) {
         for(Set<String> group: groups) {
             boolean found = false;
             for(String str: group) {
                 if(isAnagram(str, word)) {
                     found = true;
                 }
                 break;
             }
             if(found) {
                 group.add(word);
                 return;
             }
         }
         Set<String> set = new HashSet<>();
         set.add(word);
         groups.add(set);
     }

     private boolean isAnagram(String str, String word) {
         Set<Character> characters = new HashSet<>();
         for(char c: str.toCharArray()) {
             characters.add(c);
         }
         for(char c: word.toCharArray()) {
             if(!characters.contains(c)) {
                 return false;
             }
             characters.remove(c);
         }
         return characters.isEmpty();
     }

     public static void main(String[] args) {
         Set<Set<String>> groups = new AnagramGroups()
             .group(new HashSet<>(Arrays.asList("cat", "god", "dog")));
         System.out.println(groups);

         Set set1 = new HashSet<>(Arrays.asList("cat"));
         Set set2 = new HashSet<>(Arrays.asList("god", "dog"));
         System.out.println(groups.contains(set1));
         System.out.println(groups.contains(set2));

         groups.add(new HashSet<>(Arrays.asList("god", "dog")));
         System.out.println(groups);
     }
}

Answer 1

The issue is in your findAndAdd method, where you are mutating an element (group) of the outer Set (groups), therefore changing its hashCode(). As a result, groups.contains(set2) cannot find a Set that is present in groups, since it looks for it in the wrong bucket (matching the new hashCode()) instead of the bucket to which it was added (matching the original hashCode()).

You can fix your code by removing the group Set from groups before mutating it and then re-add it.

Change your code from:

 private void findAndAdd(String word, Set<Set<String>> groups) {
     for(Set<String> group: groups) {
         boolean found = false;
         for(String str: group) {
             if(isAnagram(str, word)) {
                 found = true;
             }
             break;
         }
         if(found) {
             group.add(word);
             return;
         }
     }
     Set<String> set = new HashSet<>();
     set.add(word);
     groups.add(set);
 }

to:

 private void findAndAdd(String word, Set<Set<String>> groups) {
     for(Set<String> group: groups) {
         boolean found = false;
         for(String str: group) {
             if(isAnagram(str, word)) {
                 found = true;
             }
             break;
         }
         if(found) {
             groups.remove(group);
             group.add (word);
             groups.add(group);
             return;
         }
     }
     Set<String> set = new HashSet<>();
     set.add(word);
     groups.add(set);
 }

When I tried your code and made that change, I got true in both cases.

Output:

[[cat], [god, dog]]
true
true
[[cat], [god, dog]]