java - HashSet vs ArrayList 包含性能

Question

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

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

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

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

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

因此无需将集合“转储”到列表中。但是，在插入每个元素之前我会做一个小检查(我假设 HashSet 也是如此)

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

Answer 1

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

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