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

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'inmapA出现在mapB，它们的键是5和7分别。

因此我需要的 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 count > 0，但考虑到 Eritrean的答案中提出的替代方案，这些不是必需的：

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方法是使用方法。也就是说，给定两个集合xand y， dox.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();

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