如何比较两个地图并检索两个地图中出现的值的键？

Question

newPropertiesFile.keySet().parallelStream()    .filter(value -> oldPropertiesFile.keySet().parallelStream()            .filter(entry -> oldPropertiesFile.get(entry).toString().equals(newPropertiesFile.get(value).toString()))            .filter(values -> !values.equals(value)).count() > 0)    .collect(Collectors.toMap(entryKey -> (String) entryKey, entryKey -> newPropertiesFile.get(entryKey).toString()));例如，我有mapA = {(1,'a'),(2,'b'),(3,'c')}并mapB = {(5,'a'),(6,'d'),(7,'c')} 比较两个映射的 valueList，值'a'和'c'出现mapA在mapB它们的键是5和7resp。因此我需要 o/p:5,7我已经完成了上述操作并获得了所需的输出。但是 O(n^2) 的复杂度太高了。有什么优化方法吗？一个更简化的例子：mapA.keySet().parallelStream()    .filter(v->mapB.keySet().parallelStream()            .filter(e->mapB.get(v).equals(mapA.get(v)))            .filter(v->!v.equals(v)).count()>0)    .forEach(System.out::println);

Answer 1

让我们总结一下这方面的一些变化，因为最好的解决方案只有在阅读其他答案和评论后才会出现。

这个问题的简化问题是这样的。给定两张地图：

Map<Integer, String> mapA = Map.of(1, "a", 2, "b", 3, "c")

Map<Integer, String> mapB = Map.of(5, "a", 6, "d", 7, "c")

mapB找到对应于两个映射中出现的值的键。这个问题的解决方案是这样的（为清楚起见进行了编辑）：

Set<Integer> result = mapB.keySet().stream()

    .filter(keyB -> mapA.keySet().stream()

                        .filter(keyA -> mapA.get(keyA).equals(mapB.get(keyB)))

                        .count() > 0)

    .collect(toSet());

从本质上讲，这就像两个嵌套循环，循环遍历每个映射的键。内层循环获取每个键对应的值并计算匹配次数。如果至少有一个匹配项，则密钥将通过过滤器传递到结果。

OP 对此并不满意，并要求进行改进，尤其是在算法复杂性方面。如评论中所述，真正的问题可能有 15,000 个地图条目。该算法的复杂度为 O(n^2)，并且随着映射数量的增加，它的性能确实开始明显下降。有一些可以改进的小方法，例如使用anyMatch而不是filterand ，但是鉴于Eritrean 的回答count > 0中提出的替代方案，这些不是必需的：

Set<Integer> result = mapB.entrySet().stream()

    .filter(entry -> mapA.values().contains(entry.getValue()))

    .map(Map.Entry::getKey)

    .collect(toSet());

这更好，因为它使用containsmapAvalues()视图上的操作，替换了先前解决方案的内部流。但是，地图的值未编入索引，因此contains()对地图的值进行操作的唯一方法是（可能）搜索每个条目。这比以前好一些，如果找到匹配项，contains()可以立即返回；但如果未找到匹配项，则必须搜索地图的所有值。因此，平均而言，这种变化仍然在 O(n^2) 时间内运行。

缓解这种情况的一种方法是将 mapA 的值拉入HashSet. 这会将检查从线性时间减少contains()到恒定时间，将整体复杂度从 O(n^2) 降低到 O(n)。那看起来像这样：

Set<String> aValues = new HashSet<>(mapA.values());

Set<Integer> result = mapB.entrySet().stream()

    .filter(entry -> aValues.contains(entry.getValue()))

    .map(Map.Entry::getKey)

    .collect(toSet());

这是一个很大的改进，但事实证明根本没有必要使用流。回到问题陈述，它有一个子句“...两个映射中都出现的值”。这实质上是在值集合上进行集合交集。在 Java 中进行交集的方法是使用retainAll方法。也就是说，给定两个集合x和y，doingx.retainAll(y)将只保留x那些也出现在 中的元素y，并删除其他元素。这本质上是一个集合的交叉点。为此，retainAll通常必须contains重复调用y，因此确保操作快速是个好主意——就像使用HashSet.

好的，如果我们将值集合相交，这会为我们提供值——但我们需要键。特别是，我们想要 mapB 的键。我们该怎么做？

事实证明，values()地图的视图支持删除——确实retainAll如此——如果从中删除了一个值，则会从底层地图中删除相应的条目。在这种情况下，我们可以从 mapB（或副本）开始，获取其values()视图，调用retainAll我们之前加载到HashSet. 这在 mapB 中仅留下与 mapA 具有共同值的条目。由于我们对键而不是条目感兴趣，所以我们只获取视图keySet()。该代码如下所示：

Set<String> aValues = new HashSet<>(mapA.values());

Map<Integer, String> mapBcopy = new HashMap<>(mapB);

mapBcopy.values().retainAll(aValues);

Set<Integer> result = mapBcopy.keySet();

这演示了如何在集合视图上使用集合批量操作比使用流更简单地完成某些任务。