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
操作)是集合的主要 目的 。
包含HashSet
会O(1)
与O(n)
列表进行比较,因此,如果您经常需要运行,则永远不要使用列表contains
。