HashSet vs ArrayList 包含性能 [英] HashSet vs ArrayList contains performance

问题描述

在处理大量数据时，我经常发现自己在做以下事情:

When processing large amounts of data I often find myself doing the following:

HashSet<String> set = new HashSet<String> ();
//Adding elements to the set
ArrayList<String> list = new ArrayList<String> (set);

类似于转储"列表中集合的内容.我通常这样做是因为我添加的元素通常包含我想要删除的重复项，这似乎是删除它们的简单方法.

Something like "dumping" the contents of the set in the list. I usually do this since the elements I add often contain duplicates I want to remove, and this seems like an easy way to remove them.

只考虑这个目标(避免重复)我也可以写:

With only that objective in mind (avoiding duplicates) I could also write:

ArrayList<String> list = new ArrayList<String> ();
// Processing here
if (! list.contains(element)) list.add(element);
//More processing here

因此不需要将集合转储"到列表中.但是，在插入每个元素之前我会做一个小检查(我假设 HashSet 也这样做)

And thus no need for "dumping" the set into the list. However, I'd be doing a small check before inserting each element (which I'm assuming HashSet does as well)

这两种可能性中的任何一种显然更有效吗?

Is any of the two possibilities clearly more efficient?

推荐答案

集合将提供更好的性能 (O(n) vs O(n^2)对于列表)，这是正常的，因为集合成员资格(contains 操作)是集合的真正目的.

The set will give much better performance (O(n) vs O(n^2) for the list), and that's normal because set membership (the contains operation) is the very purpose of a set.

HashSet 的包含是 O(1) 与列表的 O(n) 相比，因此永远不要使用列表如果你经常需要运行 contains.

Contains for a HashSet is O(1) compared to O(n) for a list, therefore you should never use a list if you often need to run contains.

这篇关于HashSet vs ArrayList 包含性能的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！