75

我想知道 List 和 Set 在性能、内存分配和可用性方面的比较。

如果我不需要保持对象列表中的唯一性，也不需要维护插入顺序，我可以互换使用 ArrayList 和 SortedSet/HashSet 吗？直接使用 Collections 类而不是 list/set 会更好吗？

PS我也不需要列出或设置java提供的特定功能。我使用 List/Set 而不是 Array 只是因为它们可以动态增长而无需额外的编程工作。

4

6 回答 6

108

HashSet比相同数量的元素消耗大约 5.5 倍的内存ArrayList（尽管它们仍然是线性的），并且迭代速度明显较慢（尽管具有相同的渐近线）；快速的 Google 搜索表明HashSet迭代速度比ArrayList.

如果您不关心 的唯一性或性能contains，请使用ArrayList.

于 2012-05-29T12:57:48.497 回答
64

如果您不关心排序，也不删除元素，那么归根结底是您是否需要在此数据结构中查找元素，以及您需要这些查找的速度。

HashSet在 a is中按值查找元素O(1)。在一个ArrayList，它是O(n)。

如果您只使用容器来存储一堆独特的对象，并在最后迭代它们（以任何顺序），那么可以说ArrayList是一个更好的选择，因为它更简单、更经济。

于 2012-05-29T12:47:36.497 回答
4

If you plan only to add elements and later iterate over them, your best bet is ArrayList as it's closest to the arrays you are replacing. It's more memory efficient than LinkedList or any Set implementation, has fast insertion, iteration, and random access.

于 2012-05-29T12:58:47.727 回答
3

If you will compare, searching between List and Set, Set will be better because of the underline Hashing algorithm.

In the case of a list, in worst case scenario, contains will search till the end. In case of Set, because of hashing and bucket, it will search only subset.

Sample use case: Add 1 to 100_000 integer to ArrayList and HashSet. Search each integer in ArrayList and HashSet.

Set will take 9 milliseconds where as List will take 16232 seconds.

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

}
于 2019-01-24T19:18:23.790 回答
1

如果您不需要在集合中拥有独特的元素，只需使用ArrayList，除非您有非常特殊的需求。

如果您要求集合中只有唯一的元素，那么HashSet除非您有非常特殊的需求，否则请使用。

关于SortedSet（和它的实现者TreeSet），根据 JavaDoc：

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

这意味着它针对的是非常特定的用例，当元素应始终在 a 中排序时set，通常不需要。

于 2012-05-29T12:53:24.250 回答
1

Use HashSet if you need to use .contains(T) frequently.

Example:

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);
}
于 2016-04-24T18:12:08.547 回答