Я хочу знать сравнение между List и Set с точки зрения производительности, распределения памяти и удобства использования.
Если у меня нет требования сохранять уникальность в списке объектов, не требуется, чтобы порядок вставки поддерживался, могу ли я использовать ArrayList и SortedSet/HashSet взаимозаменяемо? Будет ли полезно напрямую использовать класс Collections вместо даже списка/набора?
P.S. У меня также нет необходимости в списке или задавать определенные функции, предоставляемые java. Я использую List/Set вместо Array только потому, что они могут динамически расти без дополнительных усилий по программированию.
Если вы не заботитесь о заказе и не удаляете элементы, то действительно важно, нужно ли находить элементы в этой структуре данных и насколько быстро вам нужны эти поисковые запросы.
Поиск элемента по значению в HashSet составляет O(1). В ArrayList оно O(n).
Если вы используете контейнер для хранения множества уникальных объектов и перебираете их в конце (в любом порядке), то возможно ArrayList является лучшим выбором, поскольку он более простой и экономичный.
HashSet потребляет в 5,5 раз больше памяти, чем ArrayList для одного и того же количества элементов (хотя они оба по-прежнему линейные) и имеет значительно более медленную итерацию (хотя и с той же асимптотикой); быстрый поиск Google предполагает 2-3-кратное замедление для HashSet итерации против ArrayList.
Если вам не нужна уникальность или производительность contains, используйте ArrayList.
Если вы планируете добавлять элементы, а затем перебирать их, лучшим вариантом будет ArrayList, поскольку он ближе всего к массивам, которые вы заменяете. Это более эффективная память, чем LinkedList или любая реализация Set, имеет быструю вставку, итерацию и произвольный доступ.
Если у вас нет требования иметь уникальные элементы в коллекции, просто используйте ArrayList, если у вас нет особых потребностей.
Если у вас есть требование иметь только уникальные элементы в коллекции, используйте HashSet, если у вас нет особых потребностей.
Относительно SortedSet (и его реализация TreeSet), в соответствии с JavaDoc:
A Набор, который далее обеспечивает полное упорядочивание его элементов. Элементы упорядочиваются с использованием их естественного упорядочения или с помощью компаратора, обычно предоставляемого в процессе создания отсортированного набора.
Это означает, что он ориентирован на довольно конкретные варианты использования, когда элементы всегда должны быть упорядочены в 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);
}
Если вы сравните, поиск между 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
}