Set<Set> Java中的等式

Question

我有一个返回Set<Set<String>>的方法。在我的测试中，我试图使用Set方法检查预期的contains()是否存在。

例如：input = "cat", "dog", "god"

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

现在，如果我执行output.contains(new HashSet<>(Arrays.asList("cat")))，它将返回true。

但是如果我做了output.contains(new HashSet<>(Arrays.asList("dog", "god")))，它会返回false。

根据我的理解，在这两种情况下它都应该返回true。

我在这里错过了什么？

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

问题在您的findAndAdd方法中，您正在变异外部Set (groups)的一个元素(group)，因此更改它的hashCode()。因此，groups.contains(set2)无法找到groups中存在的Set，因为它在错误的桶(匹配新的hashCode())中查找，而不是在添加到的桶(匹配原始hashCode())中查找。

您可以在修改代码之前从group Set中删除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 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);
 }

当我尝试您的代码并进行更改时，在这两种情况下我都得到了true。

输出：

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

Answer 2

当您使用Set set2 = new HashSet<>(Arrays.asList("god", "dog"));时，您不是在检查组合"god" and "dog"，而是检查每个元素god，然后dog是否存在于您的Set<Set<String>>中，并且在您的集合中只有一个元素cat是分开的。就像：

groups contains `god` -> no
groups contains `dog` -> no

return false

要解决您的问题，您可以像这样使用等号：

groups.stream().anyMatch(a -> a.equals(set2))// or groups.stream().anyMatch(set2::equals)

或

groups.stream().anyMatch(a -> a.containsAll(set2))

Answer 3

尝尝这个。

static String sort(String s) {
    int[] sortedCP = s.codePoints().sorted().toArray();
    return new String(sortedCP, 0, sortedCP.length);
}

public static Set<Set<String>> group(Set<String> words) {
    Map<String, Set<String>> map = new HashMap<>();
    for (String word : words)
        map.computeIfAbsent(sort(word), k -> new HashSet<>()).add(word);
    return new HashSet<>(map.values());
}

和

Set<String> words = new HashSet<>(Arrays.asList("cat", "dog", "god"));
System.out.println(group(words));

结果：

[[cat], [god, dog]]

中间变量map

{act=[cat], dgo=[god, dog]}