java - 如何检测 Map> 中的重复列表

Question

我有一个 Map<String,List<String>> 形式的 map .键是文档编号，列表是符合某些条件并在文档中找到的术语列表。为了检测重复文档，我想知道 List<String> 中是否有任何两个具有完全相同的元素(这包括重复值)。List<String>已排序，因此我可以遍历 map 并首先检查 List.size() .对于任意两个列表大小相同，然后我必须将这两个列表与 List.equals() 进行比较.Map 和关联的列表永远不会很大，所以即使这种蛮力方法不能很好地扩展它就足够了。但我想知道是否有更好的方法。一种不涉及太多的方式显式循环和一种在 Map 和/或 Lists 变得更大时不会产生组合爆炸的方法。最后，我只需要对以下问题给出是/否的答案:是否有任何列表相同？

Answer 1

您可以将列表一个一个地添加到集合数据结构中。令人高兴的是，add 方法会告诉您集合中是否已经存在相等列表:

HashSet<List<String>> set = new HashSet<List<String>>();
for (List<String> list : yourMap.values()) {
    if (!set.add(list)) {
        System.out.println("Found a duplicate!");
        break;
    }
}

该算法将在 O(N) 时间内查找是否存在重复列表，其中 N 是字符串列表中的字符总数。这比比较每对列表要好得多，因为对于 n 个列表，有 n(n-1)/2 对要比较。