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

Question

我有一个程序从数据库中获取记录(使用Hibernate)并填充它们Vector.有关操作性能的问题,我做了一个测试,Vector替换为a HashSet.拥有300000条记录,速度增加非常快 - 45分钟到2分钟!

所以我的问题是,是什么造成了巨大的差异？只是所有方法Vector都是同步的,还是内部Vector使用数组的点而HashSet不是？或者是其他东西？

代码在单个线程中运行.

编辑:代码只插入Vector(和在其他情况下HashSet)的值.

Answer 1

如果它试图使用Vector as作为集合,并在添加它之前检查记录的存在,那么填充向量变为O(n ^ 2)操作,与O(n)相比HashSet.如果在向量的开头而不是在结尾插入每个元素,它也将成为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");
  }
}

输出:

所用时间:38毫秒

现在显然这不是很准确 - System.currentTimeMillis不是获得准确计时的最佳方式 - 但显然不需要花费45分钟.换句话说,如果你真的只是打电话,你应该在别处找问题Vector.add(item).

现在,更改上面的代码使用

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

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