1

我写了一个类来测试arraylist和hashset之间的插入性能，正如我所料，hashset的插入性能会比arraylist好得多（可能是书欺骗了我），但是测试结果让我很困惑

    HashSet<String> hashSet = new HashSet<String>();

    long start = System.currentTimeMillis();
    for (int i = 0; i < 900000; i++) {
        hashSet.add(String.valueOf(i));
    }

    System.out.println("Insert HashSet Time: " + (System.currentTimeMillis() - start));


    ArrayList<String> arrayList = new ArrayList<String>();

    start = System.currentTimeMillis();

    for (int i = 0; i < 900000; i++) {
        arrayList.add(String.valueOf(i));
    }
    System.out.println("Insert ArrayList Time: " + (System.currentTimeMillis() - start));

result:
Insert HashSet Time: 978
Insert ArrayList Time: 287

我多次运行这个主要方法，结果与此没有更多不同，插入数组列表时间比插入哈希集时间短得多，谁能解释这个奇怪的结果。

4

5 回答 5

4

哈希集和列表是不同类型的数据结构。所以你应该在选择一个之前考虑一下你想用它们做什么。

哈希集

更长的插入时间

快速访问元素

列表

快速追加时间

元素访问时间长

列表更快，因为它可以只在列表末尾添加元素，哈希集必须找到插入位置然后使元素可访问，这是更多的工作（时间），因为将其添加到列表的末尾。

于 2013-02-25T15:18:47.720 回答
2

数据结构和算法的确切性能特征是高度特定于机器和实现的。ArrayList但是，对于我来说插入比HashSet插入快一个常数因子似乎并不奇怪。要插入ArrayList，您只需在数组中的特定索引处设置一个值。要插入哈希集中，您需要计算插入项目的哈希码并将其映射到数组索引，检查该索引并可能根据您找到的内容执行一些操作，最后插入到数组中。此外，这HashSet将具有更差的内存局部性，因此您将更频繁地获得缓存未命中。

还有数组调整大小的问题，这两种数据结构都需要这样做，但是两种数据结构都需要以大致相同的速率调整大小（并且由于重新散列，哈希表调整大小也可能因常数因素而更昂贵） .

两种算法都是恒定的（预期的）时间，但是与哈希表相比，与数组列表有关的事情要多得多。因此，它会因常数因素而变慢也就不足为奇了。（同样，确切的差异在很大程度上取决于机器和实现。）

于 2013-02-25T15:28:44.687 回答
0

实际上，您得到了正确的结果。此外，正如上述答案所指出的，这些是不同类型的数据结构。比较它们就像比较自行车和汽车的速度。我认为插入 a 的时间HashSet必须多于插入 an 的时间，ArrayList因为HashSet不允许重复键。所以我假设在插入之前必须在插入之前对重复键进行某种检查，以及如何处理它们，这使得它们与ArrayList.

于 2013-02-25T15:25:14.377 回答
0

HashSet 由哈希表支持。如果您了解哈希表，您就会知道有一个哈希函数。当您在其中添加新元素时，还会发生碰撞处理（如果发生碰撞）。好吧 hashSet 不处理冲突，如果哈希相同，只需覆盖旧值。但是，如果达到容量，则需要调整大小，并可能重新散列。这会很慢。

ArrayList 只是将对象附加到列表的末尾。如果大小达到，它会调整大小。

于 2013-02-25T15:24:31.013 回答
0

hashset 插入性能会比 arraylist 好很多

你从哪里得到这个想法的？
HashSet将在搜索方面表现出色ArrayList，即：get().
但在插入时，它们具有可比的性能。ArrayList如果您在数组限制内（不需要调整大小）并且哈希函数不好，实际上会更快

于 2013-02-25T15:24:06.673 回答