Сравнение производительности и распределения памяти между списком и набором

Я хочу узнать сравнение между List и Set с точки зрения производительности, распределения памяти и удобства использования.

Если у меня нет каких-либо требований по сохранению уникальности в списке объектов, также не требуется поддерживать порядок вставки, могу ли я использовать ArrayList и SortedSet / HashSet взаимозаменяемо? Будет ли хорошо использовать класс Collections вместо списка / набора?

Постскриптум У меня также нет необходимости перечислять или устанавливать конкретные функции, предоставляемые Java. Я использую List / Set вместо Array только потому, что они могут динамически расти без дополнительных усилий программирования.

 Jon Skeet29 мая 2012 г., 14:47
Какиеdo тебе нужно из коллекции?
 Marko Topolnik29 мая 2012 г., 14:52
В настоящее время вы заявляете, что вам нужна коллекцияonly to add elements, Это чепуха. Там должна быть какая-то операция чтения, которая вам также нужна. Уточнить.
 Kazekage Gaara29 мая 2012 г., 14:46
Для начинающих :stackoverflow.com/questions/1035008/…
 Marko Topolnik29 мая 2012 г., 14:49
Вам необходимо точно указать, какие операции вы планируете использовать для этого. Каждая реализация - это компромисс в пользу одной операции за счет других.
 Marko Topolnik29 мая 2012 г., 14:53
Коллекция не класс, кстати. Даже не абстрактный класс.

Ответы на вопрос(6)

Если вы сравните, поиск между List и Set, Set будет лучше из-за подчеркнутого алгоритма хеширования.

В случае списка, в худшем случае, содержит поиск до конца. В случае Set, из-за хеширования и сегмента, он будет искать только подмножество.

Пример использования: Добавьте от 1 до 100_000 целых чисел в ArrayList и HashSet. Поиск каждого целого числа в ArrayList и HashSet.

Установка займет 9 миллисекунд, в то время как список займет 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

}

Если вы планируете только добавлять элементы, а затем перебирать их, лучше всегоArrayList так как он ближе всего к массивам, которые вы заменяете. Это более эффективно, чем памятьLinkedList или любойSet реализация, имеет быструю вставку, итерацию и произвольный доступ.

Если у вас нет требования иметь уникальные элементы вcollection просто используйтеArrayList если у вас нет особых потребностей.

Если у вас есть требование иметь только уникальные элементы вcollectionзатем используйтеHashSet если у вас нет особых потребностей.

Что касаетсяSortedSet (и это разработчикTreeSet), согласно JavaDoc:

A Set that further provides a total ordering on its elements. The elements are ordered using their natural ordering, or by a Comparator typically provided at sorted set creation time.

Это означает, что он нацелен на вполне конкретные случаи использования, когда элементы должны всегда упорядочиваться вset, который обычно не нужен.

использованиеHashSet если вам нужно использовать.contains(T) часто.

Пример:

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);
}

HashSet потребляет примерно в 5,5 раз больше памяти, чемArrayList для одного и того же числа элементов (хотя они оба все еще линейны) и имеют значительно более медленную итерацию (хотя и с одинаковой асимптотикой); быстрый поиск в Google предполагает 2-3-кратное замедление дляHashSet итерация противArrayList.

Если вы не заботитесь об уникальности или производительностиcontainsзатем используйтеArrayList.

 29 мая 2012 г., 15:36
В настоящее время они с большей вероятностью составляют 8 байт / элемент.
 29 мая 2012 г., 15:15
В принципе, правило состоит в том, что массивы составляют 4 байта на элемент, иArrayList состоит из немногим больше, чем массив (с некоторым пространством для роста) и постоянным числомint поля.
 29 мая 2012 г., 15:02
Хорошо, если вы знаете количество элементов, ожидаемых заранее, и выделитеArrayList соответственно, оно ближе к 8 разам. Но это не похоже на то, что мы можем сделать такое предположение о ситуации ОП.
 29 мая 2012 г., 15:39
Зависит от того, используете ли вы 32-битную или 64-битную виртуальную машину. Это сказало,HashSet хуже от 8-байтовых ссылок, чемArrayList делает - добавление дополнительных 4 байтов на ссылку, на основе диаграммы потребления связанной памяти, приноситArrayList до ~ 12 байт на элемент иHashSet до ~ 52 байт на элемент.)
Решение Вопроса

Если вы не заботитесь о порядке и не удаляете элементы, тогда все сводится к тому, нужно ли вам находить элементы в этой структуре данных и насколько быстро вам нужны эти поиски.

Нахождение элемента по значению вHashSet являетсяO(1), ВArrayListэтоO(n).

Если вы используете контейнер только для хранения набора уникальных объектов и перебора их в конце (в любом порядке), то, вероятно,ArrayList это лучший выбор, поскольку он более простой и экономичный.

 29 мая 2012 г., 14:53
Нахождение элемента вArrayList являетсяO(n)? Не найти элемент вArrayList такое прямой доступ через индекс?
 29 мая 2012 г., 14:59
@PauKiatWee: я имею в виду «найти по значению». OP уже заявил, что он не заботится о порядке элементов, поэтому доступ по индексу явно не имеет значения.
 29 мая 2012 г., 14:58
Я предполагаю, что "найти элемент" он имеет в видуcontains.
 04 февр. 2017 г., 06:36
Поиск элемента по значению в HashSet - это O (1) Как это?

Ваш ответ на вопрос