2

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

4

4 回答 4

4

您可以将列表逐个添加到集合数据结构中。令人高兴的是，该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 对要比较。

于 2013-09-18T16:28:20.903 回答
1

使用Map.containsValue(). 不会比你描述的更有效，但代码会更干净。链接-> http://docs.oracle.com/javase/7/docs/api/java/util/Map.html#containsValue%28java.lang.Object%29

此外，根据您这样做的确切原因，可能值得研究此界面-> http://google-collections.googlecode.com/svn/trunk/javadoc/com/google/common/collect/BiMap.html

于 2013-09-18T16:32:19.690 回答
0

不确定这是否是更好的方法，但更简洁的方法是创建一个实现 Comparable 并保存您的 List 之一的对象。您可以像上面描述的那样实现 hashcode() 和 equals() 并更改您的地图以包含此类的实例，而不是直接包含列表。

然后，您可以使用 HashSet 有效地发现哪些列表是相等的。或者您可以将映射的值集合添加到 HashSet 并将哈希集的大小与 Map 的大小进行比较。

于 2013-09-18T16:24:54.520 回答
0

从'List.equals（Object o）'的JavaDoc：

比较指定对象与此列表是否相等。当且仅当指定对象也是一个列表时返回 true，两个列表具有相同的大小，并且两个列表中所有对应的元素对都相等。（如果 (e1==null ? e2==null : e1.equals(e2)) 两个元素 e1 和 e2 相等。）换句话说，如果两个列表以相同的顺序包含相同的元素，则它们被定义为相等. 此定义确保 equals 方法在 List 接口的不同实现中正常工作。

这让我相信它正在做你提议的同样的事情：检查以确保双方都是一个列表，然后比较大小，然后检查每一对。我不会在那里重新发明轮子。

您可以hashCode()改用，但那里的 JavaDoc 似乎也表明它正在循环：

返回此列表的哈希码值。列表的哈希码定义为以下计算的结果：

 int hashCode = 1;
  Iterator<E> i = list.iterator();
  while (i.hasNext()) {
      E obj = i.next();
      hashCode = 31*hashCode + (obj==null ? 0 : obj.hashCode());
  }

所以，我认为你没有节省任何时间。但是，您可以编写一个自定义 List 来计算放入项目时的哈希值。然后您可以抵消执行循环的成本。

于 2013-09-18T16:27:57.907 回答