ArrayList和HashSet的插入性能测试结果让我困惑

我WIRTE类测试的ArrayList和HashSet的之间的插入性能，如我所料，HashSet中插入性能会比ArrayList的好很多（也许这本书欺骗了我），但测试结果让我很困惑ArrayList和HashSet的插入性能测试结果让我困惑

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

我运行这个主梅托德很多次，结果没有这个之间有更多的不同，插入ArrayList的时间比插入HashSet的时间任何人可以解释这个怪异的结果要短得多。

来源

2013-02-25 Gospel

可能会有字符串缓存进行字符串。例如。花费时间为HashSet创建字符串，然后在ArrayList中对其进行缓存和重用。如果您颠倒顺序，您会得到什么结果（例如，先填充ArrayList，再填充HashSet第二个）？ – 2013-02-25 15:22:27

数据结构和算法的精确性能特征非常依赖于机器和实现。但是，对于我来说ArrayList插入会比插入一个常数因子要快。要插入到ArrayList中，只需要在数组中的某个特定索引处设置一个值。要插入散列集，您需要计算插入项的散列码并将其映射到数组索引，检查该索引并根据所找到的内容执行某些操作，最后插入数组。此外HashSet将有更糟的内存位置，所以你会更经常地得到缓存未命中。

还有一个数组大小调整的问题，两个数据结构都需要这样做，但两个数据结构都需要调整大约相同的速率（并且哈希表调整大小可能会因恒定因子而更加昂贵，由于重新哈哈哈）。

这两种算法都是恒定的（预计）时间，但是哈希表的数量比数组列表要多得多。所以不会因为一个不变因素而变慢就不奇怪了。（同样，确切的区别高度依赖于机器和实现。）

来源

2013-02-25 15:28:44 jacobm

哈希集和列表是不同类型的数据结构。所以你应该在选择之前思考你想要做什么。

HashSet的

更长的插入时间

上的元素

列表

快速追加时间

朗接入T快速访问时间上的元素IME

名单是更快，因为它只需在列表的末尾添加元素，HashSet中已找到在哪里插入，然后进行元素accessable，这是更多的工作（时间）将其添加到列表的末尾。

来源

2013-02-25 15:18:47 Peter

谢谢，我记得哈希码在元素插入之前使用了哈希码去掉元素位置哦，我想我应该更仔细地阅读本书~~谢谢你这么多 – Gospel 2013-02-25 15:27:52

列表有一个快速*追加*时间; *插入*时间取决于他们如何在内部实施。 – 2013-02-26 13:32:30

HashSet中插入性能会比ArrayList的

你从哪里得到这个想法好很多？
HashSet将在搜索即超越ArrayList：get()。
但插入他们有相当的表现。其实ArrayList甚至更快，如果你是阵列范围之内（不调整大小需要）和散列功能不好

来源

2013-02-25 15:24:06 Cratylus

HashSet的是通过哈希表支持。如果你知道散列表，你会知道有一个散列函数。还有碰撞处理（如果有碰撞），当你添加新的元素时。那么哈希集不处理冲突，只是如果散列相同覆盖旧值。但是，如果容量达到，它需要调整大小，并可能重新哈希。它会很慢。

的ArrayList只是对象追加到列表的末尾。如果大小达到，它确实调整大小。

来源

2013-02-25 15:24:31 Kent

其实，你正在得到正确的结果。另外，正如在上面的答案中指出的那样，这些是不同类型的数据结构。比较它们就像比较自行车和汽车的速度。我认为在HashSet中插入的时间必须多于在ArrayList中插入的时间，因为HashSet不允许重复键。所以我假设插入之前必须有一些类型的检查插入前的重复键和如何处理它们，这使得它们比ArrayList稍慢。

来源

2013-02-25 15:25:14 TheRookierLearner

ArrayList和HashSet的插入性能测试结果让我困惑

回答

相关问题