查找具有公共值的映射集条目

Question

我有一个收藏如下

Map<String, Set<Long>> myMap = new HashMap<>();

我想知道这张地图上是否有任何条目被设置为同一张地图的另一个条目。

例如，让我们说地图有以下5个条目

a - {1, 2, 3}
b - {4, 5}
c - {1}
d - {2, 3}
e - {5}
f - {6}

因此，它可能有以下重叠项

a - {1, 2, 3}  and c - {1} 
b - {4, 5}     and e - {5}
a - {1, 2, 3}  and d - {2, 3}

或者只是一组按键列表，比如

a and c
b and e
a and d

我可以迭代每个键集，然后对每个键集使用disjoint或anyMatch，但我想知道是否有一种优化方法（Java8、9、10、11）。

Answer 1

将Map按Set中的元素数降序排序，即排序Map中的第一个条目包含包含最多元素的Set。在您的示例中，这将是以下条目：

a - {1, 2, 3}

排序后，取第二个条目，查看其集合是否是第一个条目的集合的子集。第二个条目是

b - {4, 5}

或

d - {2, 3}

然后取第三个条目，看看它的集合是第二个条目还是第一个条目的子集。继续，直到到达最后一个条目。

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Map;
import java.util.Set;
import java.util.stream.Collectors;

public class Subsets {

    public static void main(String args[]) {
        Map<String, Set<Long>> myMap = Map.of("a", Set.of(1L, 2L, 3L),
                                              "b", Set.of(4L, 5L),
                                              "c", Set.of(1L),
                                              "d", Set.of(2L, 3L),
                                              "e", Set.of(5L),
                                              "f", Set.of(6L));
        List<String> sortedKeys = myMap.entrySet()
                                       .stream()
                                       .sorted((e1, e2) -> (e2.getValue() == null ? 0 : e2.getValue().size()) - (e1.getValue() == null ? 0 : e1.getValue().size()))
                                       .map(e -> e.getKey())
                                       .collect(Collectors.toList());
        String[] keyArray = new String[sortedKeys.size()];
        sortedKeys.toArray(keyArray);
        List<String[]> subsets = new ArrayList<>();
        for (int i = 1; i < keyArray.length; i++) {
            Set<Long> source = myMap.get(keyArray[i]);
            for (int j = i - 1; j >= 0; j--) {
                Set<Long> target = myMap.get(keyArray[j]);
                if (target.containsAll(source)) {
                    subsets.add(new String[]{keyArray[i], keyArray[j]});
                }
            }
        }
        subsets.forEach(arr -> System.out.println(Arrays.toString(arr)));
    }
}

执行上述代码时产生的输出如下：

[d, a]
[e, b]
[c, a]

换句话说：

• d是a
的子集
• e是b
的子集
• c是a
的子集

嵌套的for循环的总迭代次数是15次，即O（nlog2n），而另一个答案是36次迭代，即O（n²）。

请注意，如果可以按排序顺序创建初始的映射，则无需执行排序。一种方法是使用LinkedHashMap作为映射实现。

myMap = new LinkedHashMap<>();
myMap.put("a", Set.of(1L, 2L, 3L));
myMap.put("b", Set.of(4L, 5L));
myMap.put("d", Set.of(2L, 3L));
myMap.put("c", Set.of(1L));
myMap.put("e", Set.of(5L));
myMap.put("f", Set.of(6L));

Answer 2

我相信这是可能的通过流。但在这种情况下，嵌套循环也可以。

import java.util.*;

class Main {
    public static void main(String[] args) {
        Map<String, Set<Long>> myMap = new HashMap<>();

        myMap.put("a", Set.of( 1l, 2l, 3l ));
        myMap.put("b", Set.of( 4l, 5l ));
        myMap.put("c", Set.of( 1l ));
        myMap.put("d", Set.of( 2l, 3l ));
        myMap.put("e", Set.of( 5l ));
        myMap.put("f", Set.of( 6l ));

        for(String aKey : myMap.keySet())
            for(String bKey : myMap.keySet())
                if(!aKey.equals(bKey) &&  myMap.get(aKey).containsAll(myMap.get(bKey))) 
                    System.out.println(aKey + " - " + myMap.get(aKey) + " and " + bKey + " - " + myMap.get(bKey));
    }
}