List 和 Set 的性能和内存分配比较

小开

最佳答案

如果您不关心排序，也不删除元素，那么它实际上归结为您是否需要在这个数据结构中查找元素，以及您需要这些查找的速度有多快。

通过值在 HashSet中查找元素是 O(1)，在 ArrayList中是 O(n)。

如果您只使用容器来存储一组惟一的对象，并在最后(以任意顺序)对它们进行迭代，那么可以说 ArrayList是一个更好的选择，因为它更简单、更经济。

小开

如果您没有要求在 收藏品中具有唯一的元素，那么只需使用 ArrayList，除非您有非常具体的需求。

如果您要求在 收藏品中只有唯一的元素，那么使用 HashSet，除非您有非常特殊的需求。

关于 SortedSet(以及它的实现者 TreeSet) ，根据 JavaDoc:

进一步提供其元素总排序的 Set。元素使用它们的自然顺序进行排序，或者使用通常在排序集创建时提供的比较器进行排序。

这意味着它的目标是非常特定的用例，当元素应该总是在 set中排序，这通常是不需要的。

小开

对于相同数量的元素(尽管它们仍然是线性的) ，HashSet比 ArrayList多消耗大约5.5倍的内存，并且迭代速度明显较慢(尽管具有相同的渐近性) ; 快速谷歌搜索表明，HashSet迭代比 ArrayList慢2-3倍。

如果您不关心唯一性或者 contains的性能，那么使用 ArrayList。

小开

如果您计划只添加元素，并在以后迭代它们，那么最好的选择是 ArrayList，因为它最接近要替换的数组。它比 LinkedList或任何 Set实现都更高效，具有快速插入、迭代和随机访问。

小开

如果需要经常使用 .contains(T)，请使用 HashSet。

例如:

private static final HashSet<String> KEYWORDS = Stream.of(new String[]{"if", "do", "for", "try", "while", "break", "return"}).collect(Collectors.toCollection(HashSet::new));


public boolean isKeyword(String str) {
return KEYWORDS.contains(str);
}

小开

如果你将比较，搜索之间的列表和集，集将更好，因为下划线哈希算法。

在列表的情况下，在最坏的情况下，包含将搜索到最后。对于 Set，由于散列和 bucket，它只搜索子集。

示例用例: 向 ArrayList 和 HashSet 中添加1到100 _ 000整数。在 ArrayList 和 HashSet 中搜索每个整数。

设置需要9毫秒，而 List 需要16232秒。

private static void compareSetvsList(){
List<Integer> list = new ArrayList<>() ;
Set<Integer> set = new HashSet<>() ;


System.out.println("Setting values in list and set .... ");
int counter = 100_000  ;


for(int i =0 ; i< counter ; i++){
list.add(i);
set.add(i);
}


System.out.println("Checking time .... ");
long l1 = System.currentTimeMillis();
for(int i =0 ; i< counter ; i++) list.contains(i);


long l2 = System.currentTimeMillis();
System.out.println(" time taken for list : "+ (l2-l1));


for(int i =0 ; i< counter ; i++)set.contains(i);


long l3 = System.currentTimeMillis();
System.out.println(" time taken for set : "+ (l3-l2));


//      for 10000   time taken for list : 123        time taken for set : 4
//      for 100000  time taken for list : 16232          time taken for set : 9
//      for 1000000 time taken for list : hung       time taken for set : 26


}