Vector 和 HashSet 之间巨大的性能差异

Question

我有一个程序，它从数据库中获取记录（使用 Hibernate）并将它们填充到 Vector 中。操作性能存在问题，我用 HashSet 替换 Vector 进行了测试。有了 300000 条记录，速度增益是巨大的 - 45 分钟到 2 分钟！

所以我的问题是，是什么造成了如此巨大的差异？仅仅是因为 Vector 中的所有方法都是同步的，还是因为 Vector 内部使用数组而 HashSet 不同步？或者其他什么？

该代码在单线程中运行。

编辑： 该代码仅将值插入 Vector 中（在其他情况下，插入 HashSet）。

Answer 1

根据 Heinz Kabutz 博士的说法，他在他的一份时事通讯中说了这一点。

旧的 Vector 类以简单的方式实现序列化。它们只是执行默认的序列化，将整个 Object[] 按原样写入流中。因此，如果我们向List中插入一堆元素，然后清除它，Vector和ArrayList之间的区别是巨大的。

import java.util.*;
import java.io.*;

public class VectorWritingSize {
  public static void main(String[] args) throws IOException {
    test(new LinkedList<String>());
    test(new ArrayList<String>());
    test(new Vector<String>());
  }

  public static void test(List<String> list) throws IOException {
    insertJunk(list);
    for (int i = 0; i < 10; i++) {
      list.add("hello world");
    }
    ByteArrayOutputStream baos = new ByteArrayOutputStream();
    ObjectOutputStream out = new ObjectOutputStream(baos);
    out.writeObject(list);
    out.close();
    System.out.println(list.getClass().getSimpleName() +
        " used " + baos.toByteArray().length + " bytes");
  }

  private static void insertJunk(List<String> list) {
    for(int i = 0; i<1000 * 1000; i++) {
      list.add("junk");
    }
    list.clear();
  }
}

当我们运行此代码时，我们得到以下输出：

LinkedList used 107 bytes
ArrayList used 117 bytes
Vector used 1310926 bytes

Vector 在序列化时可以使用惊人数量的字节。教训在这里？ 永远不要在可序列化的对象中使用 Vector 作为列表。发生灾难的可能性太大了。

Answer 2

import java.util.*;

public class Test {
  public static void main(String[] args) {
    long start = System.currentTimeMillis();
    Vector<String> vector = new Vector<String>();
    for (int i = 0; i < 300000; i++) {
       if(vector.contains(i)) {
         vector.add("dummy value");
       }
     }
    long end = System.currentTimeMillis();
    System.out.println("Time taken: " + (end - start) + "ms");
  }
}

如果在将元素插入向量之前检查重复元素，则需要更多时间，具体取决于向量的大小。最好的方法是使用 HashSet 来获得高性能，因为 Hashset 不允许重复，并且在插入之前不需要检查重复元素。

Answer 3

在正常情况下，向 Vector 插入 300,000 条记录比向 HashSet 插入相同的记录要多花 43 分钟，这完全难以置信。

然而，我认为对于正在发生的事情有一个可能的解释。

首先，从数据库中出来的记录必须具有非常高的重复比例。或者至少，根据记录类的 equals/hashcode 方法的语义，它们必须是重复的。

接下来，我认为您一定非常接近填满堆了。

因此，HashSet 解决方案之所以如此快，是因为它的大部分记录都被 set.add 操作替换。相比之下，Vector 解决方案保留所有记录，并且 JVM 花费大部分时间通过运行 GC 来尝试压缩最后的 0.05% 内存，一遍又一遍。

测试这一理论的一种方法是使用更大的堆运行应用程序的 Vector 版本。

---

无论如何，调查此类问题的最佳方法是使用分析器运行应用程序，并查看所有 CPU 时间都去哪儿了。

Answer 4

Vector默认是同步的； HashSet 不是。这是我的猜测。获取监视器以进行访问需要时间。

我不知道你的测试中是否有读取，但是如果使用 get() 访问 Vector 条目，Vector 和 HashSet 都是 O(1) 。

Answer 5

Vector 已过时，不应再使用。使用 ArrayList 或 LinkedList（取决于您如何使用列表）进行配置文件，您将看到差异（同步与不同步）。
为什么要在单线程应用程序中使用 Vector？

Answer 6

如果您将它们插入到中间或开头而不是末尾，则 Vector 需要将它们全部移动。每一个插入。另一方面，哈希图并不真正关心或不必做任何事情。

Answer 7

如果它尝试将向量用作集合，并在添加记录之前检查记录是否存在，则填充向量将成为 O(n^2) 操作，与 HashSet 的 O(n) 相比。如果将每个元素插入向量的开头而不是末尾，它也将成为 O(n^2) 操作。

如果您只是使用collection.add(item)，那么我不会期望看到这种差异 - 同步不是那样 > 慢。

如果您可以尝试使用不同数量的记录来测试它，您可以看到每个版本如何随着 n 的增加而增长 - 这将使您更容易弄清楚发生了什么。

编辑：如果您只是使用 Vector.add 那么听起来可能会发生其他事情 - 例如，您的数据库在不同的测试运行之间表现不同。这是一个小测试应用程序：

import java.util.*;

public class Test {
  public static void main(String[] args) {
    long start = System.currentTimeMillis();
    Vector<String> vector = new Vector<String>();
    for (int i = 0; i < 300000; i++) {
      vector.add("dummy value");
    }
    long end = System.currentTimeMillis();
    System.out.println("Time taken: " + (end - start) + "ms");
  }
}

输出：

耗时：38ms

现在显然这不会很准确 - System.currentTimeMillis 不是获得准确计时的最佳方法 - 但显然不会花费 45 分钟。换句话说，如果您确实只是调用Vector.add(item)，则应该在其他地方寻找问题。

现在，更改上面的代码

vector.add(0, "dummy value"); // Insert item at the beginning

会产生巨大的差异 - 需要 42 秒而不是 38 毫秒。这显然要糟糕得多 - 但距离 45 分钟还有很长的路要走 - 我怀疑我的桌面速度是你的 60 倍。