java - ArrayList与HashSet的性能

我知道在需要存储重复项时，我们更喜欢ArrayList而不是HashSet，并且HashSet使用hashCode()函数为其数组中的每个元素计算索引。

因此，这意味着如果我们要存储单个元素，则ArrayList所花的时间应少于HashSet。如果我在任何地方错了，请纠正我。

但是，当我通过代码检查性能时，我得到了不同的行为。

情况1：

import java.util.*;
class HashsetVSArraylist
{
 public static void main(String args[])
 {
  ArrayList<Integer> a1=new ArrayList<Integer>();
  long nanos = System.nanoTime();

  a1.add(1);

  System.out.println("ArrayList Time:"+(System.nanoTime()-nanos)+"ns");

  HashSet<Integer> h1=new HashSet<Integer>();
  nanos = System.nanoTime();

  h1.add(2);

  System.out.println("HashSet Insertion Time:"+(System.nanoTime()-nanos)+"ns");
 }
}

Output:
ArrayList Time:495087ns
HashSet Insertion Time:21757ns

情况2：

import java.util.*;
class HashsetVSArraylist
{
 public static void main(String args[])
 {
  HashSet<Integer> h1=new HashSet<Integer>();
  long nanos = System.nanoTime();

  h1.add(2);

  System.out.println("HashSet Insertion Time:"+(System.nanoTime()-nanos)+"ns");

  ArrayList<Integer> a1=new ArrayList<Integer>();
  nanos = System.nanoTime();

  a1.add(1);

  System.out.println("ArrayList Time:"+(System.nanoTime()-nanos)+"ns");
 }
}

Output:
HashSet Insertion Time:582527ns
ArrayList Time:21758ns

现在，我假设HashSet应该花更多时间插入单个元素。但是，在两种情况下，行为都是不同的...花费较少的时间来处理数据结构，该结构在代码中排在第二位。此外，当插入的元素数大于1000时，行为也会改变。

请解释发生了什么。

最佳答案

您的基准测试已被破坏。在尝试进行Java基准测试之前，请阅读：Dynamic compilation and performance measurement和：Anatomy of a flawed microbenchmark。

简短的解释是，您尝试测量的总时间太短了，太短了，基准测试结果将被微小的OS和CPU详细信息以及Java VM仍在忙于编译字节码的事实所淹没在机器代码开始运行时对其进行处理。

同时，这是一个有点疯狂的比较ArrayList和HashList性能时，他们有两个不同的目的，但所有其他条件相同，ArrayList中的实现是显著更简单，所以你的假设是无疑是正确的;它会更快。

关于java - ArrayList与HashSet的性能，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/29553136/