java - 在Java中找到两个大(大小~900K)字符串 vector 之间的孤儿的最快方法是什么？

Question

我目前正在开发一个需要处理大量数据的 Java 程序。我有两个 vector ...

        Vector collectionA = new Vector();
        Vector collectionB = new Vector();

...在处理过程中它们都将包含大约 900,000 个元素。

我需要找到collectionB中不包含在collectionA中的所有项目。现在，我就是这样做的:

        for (int i=0;i<collectionA.size();i++) {
            if(!collectionB.contains(collectionA.elementAt(i))){
                // do stuff if orphan is found
            }
        }

但这会导致程序运行很长时间，这是 Not Acceptable 。

有什么方法可以调整它，以便我可以显着缩短运行时间吗？

我想我读过一次，使用 ArrayList 而不是 Vector 更快。使用 ArrayLists 而不是 Vectors 对解决这个问题有帮助吗？

Answer 1

使用 HashSet 进行查找。

说明:

当前，您的程序必须测试 CollectionB 中的每个项目，看看它是否等于当前正在处理的 CollectionA 中的项目(contains() 方法需要检查每个项目)。

你应该这样做:

Set<String> set = new HashSet<String>(collectionB);

for (Iterator i = collectionA.iterator(); i.hasNext(); ) {
  if (!set.contains(i.next())) {
    // handle
  }
}

使用 HashSet 会有所帮助，因为该集合将为每个元素计算哈希，并将该元素存储在与一系列哈希值关联的存储桶中。当检查某个项目是否在集合中时，该项目的哈希值将直接标识该项目应该位于哪个桶中。现在只需检查该桶中的项目即可。

使用像 TreeSet 这样的 SortedSet 也会比 Vector 有所改进，因为要找到项目，只需找到它所在的位置检查小费，而不是检查所有位置。哪种 Set 实现效果最好取决于数据。