HashSet vs ArrayList包含性能


问题内容

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

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也是如此)

这两种可能性中的任何一种是否明显更有效?


问题答案:

集合将提供更好的性能(O(n)O(n^2)列表相比),这是正常的,因为集合成员资格(contains操作)是集合的主要 目的

包含HashSetO(1)O(n)列表进行比较,因此,如果您经常需要运行,则永远不要使用列表contains