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 也这样做）

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

原文由 Jorge 发布，翻译遵循 CC BY-SA 4.0 许可协议

Answer 1

该集合将提供更好的性能（ O(n) vs O(n^2) 对于列表），这是正常的，因为集合成员资格（ 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 。

原文由 Dici 发布，翻译遵循 CC BY-SA 4.0 许可协议

Answer 2

ArrayList 使用数组存储数据。 ArrayList.contains 的复杂度为 O(n)。所以基本上一次又一次地在数组中搜索将具有 O(n^2) 复杂性。

而 HashSet 使用散列机制将元素存储到各自的桶中。 HashSet 的操作对于长值列表会更快。它将到达 O(1) 中的元素。

原文由 YoungHobbit 发布，翻译遵循 CC BY-SA 3.0 许可协议