Статья является переводом статьи
"Top 10 questions about Java Collections".
Ниже представлены самые популярные вопросы по поводу коллекций в Java, заданные и обсужденные на Stackowerflow. До того, как Вы посмотрите на эти вопросы, хорошо бы посмотреть диаграмму иерархии классов.
1. Когда использовать LinkedList вместо ArrayList?
ArrayList по факту является массивом, его элементы могут быть доступны непосредственно по индексу. В случае переполнения массива появляется необходимость в новом, имеющем больше места. Размещение и перемещение всех элементов будет занимать O(n) времени. Также, необходимо добавление и удаление элементов для передвижения существующих элементов в массиве. Это, возможно, самое большое неудобство в использовании ArrayList.
LinkedList - это двойной список ссылок на элементы. Таким образом, для доступа к элементу в центре, приходится производить поиск с самого начала и до конца листа. С другой стороны, добавление и удаление элемента в LinkedList быстрее по той причине, что эти операции лишь изменяют сам список.
Самые плохие моменты времени сравниваются ниже:
|
Метод
|
Arraylist
|
LinkedList
|
|
get(index)
|
O(1)
|
O(n)
|
|
add(E)
|
O(n)
|
O(1)
|
|
add(E, index)
|
O(n)
|
O(n)
|
|
remove(index)
|
O(n)
|
O(n)
|
|
Iterator.remove()
|
O(n)
|
O(1)
|
|
Iterator.add(E)
|
O(n)
|
O(1)
|
Iterator itr = list.iterator();
while(itr.hasNext()) {
// do something
itr.remove();
}
Самый распространенный вариант ошибки:
for(Integer i: list) {
list.remove(i);
}
Вы получите ConcurrentModificationException во время работы кода выше. Так происходит по той причине, что итератор был сгенерирован для перемещения по всему списку, но в то же время лист изменяется вызовом Iterator.remove().
Как написано в документации по этому исключению,
"it is not generally permissible for one thread to modify a collection while another thread is iterating over it."
В целом, недопустима ситуация, при которой одна нить (thread) изменяет коллекцию в то время, как другая нить проходит по ней.
3. Как конвертировать List в массив int[]?
Самым легким путем для этого является использование ArrayUtils, располагающийся в библиотеке Apache Commons Lang.
int[] array = ArrayUtils.toPrimitive(list.toArray(new Integer[0]));
В JDK нету сокращения для этого выражения. Запомните, что Вы не можете использовать List.toArray() потому, что это выражение конвертирует List в Integer[] (который не является примитивным типом, прим. перевод.). Правильным путем будет следующий вариант:
int[] array = new int[list.size()];
for(int i=0; i < list.size(); i++) {
array[i] = list.get(i);
}
4. Как конвертировать массив int[] в List?
Самым простым способом также является использование ArrayUtils в библиотеке Apache Commons Lang, как и выше.
List list = Arrays.asList(ArrayUtils.toObject(array));
Также, в JDK нету сокращения для этого выражения.
int[] array = {1,2,3,4,5};
List list = new ArrayList();
for(int i: array) {
list.add(i);
}
5. Каким образом лучше фильтровать коллекцию?
Вы можете использовать сторонние пакеты, такие, как Guava или Apache Commons Lang для увеличения функционала. Оба этих пакета имеют метод filter() (в классе Collections2 от Guava и CollectionUtils от Apache). Метод filter() вернет элементы, которые совпадают со взятым Предикатом (Predicate).
В JDK все сложнее. Хорошие новости состоят в том, что в Java 8 предикаты будут добавлены (уже добавлены, прим. перевод.), но сейчас Вам необходимо использовать Iterator для перемещения по всей коллекции.
Iterator itr = list.iterator();
while(itr.hasNext()) {
int i = itr.next();
if (i > 5) { // filter all ints bigger than 5
itr.remove();
}
}
Конечно, Вы можете имитировать тот путь, которому следуют Guava и Apache, познакомившись с новым интерфейсом Predicate.
public interface Predicate {
boolean test(T o);
}
public static void filter(Collection collection, Predicate predicate) {
if ((collection != null) && (predicate != null)) {
Iterator itr = collection.iterator();
while(itr.hasNext()) {
T obj = itr.next();
if (!predicate.test(obj)) {
itr.remove();
}
}
}
}
Теперь мы можем использовать следующий код для фильтраци коллекции:
filter(list, new Predicate() {
public boolean test(Integer i) {
return i <= 5;
}
});
6. Как легко конвертировать List в Set?
Существует два пути для этого, в зависимости от того, как Вы хотите определять равенство. Первый кусок кода помещает список в HashSet. Дубликат в таком случае определяется в основном по hashCode(). Как правило, это будет работать. Но если Вам нужно учитывать путь сравнения, то будел лучше использовать вторую часть кода, где Вы можете определить Ваш собственный компаратор.
Set set = new HashSet(list);
Set set = new TreeSet(aComparator);
set.addAll(list);
7. Как я могу удалить повторяющиеся элементы из ArrayList?
Этот вопрос в некоторой степени связан с вопросом выше.
Если для Вас не имеет значения порядок элементов в ArrayList, умным ходом будет поместить лист в набор (Set) для удаления дублиуатов, а после этого вернуть назад в список (List).
Ниже пример.
ArrayList** list = ... // initial a list with duplicate elements
Set set = new HashSet(list);
list.clear();
list.addAll(set);
Если для Вас имеет значение порядок элементов, то порядок может быть обеспечен путем помещения списка в LinkedHashSet, который есть в стандартном JDK.
8. Сортированная коллекция
Существует несколько путей для поддержки сортированной коллекции в Java. Все из них обеспечивают коллекцию в натуральном порядке или по указанному компаратору. В случае с натуральным порядком Вам также нужно реализовать интерфейс Comparable в элементе.
- Collections.sort() может отсортировать List. Как указано в документации Java, эта сортировка стабильна и гарантирует производительность n log(n).
- PriorityQueue обеспечивает упорядоченную очередь. Различие между PriorityQueue и Collections.sort() в том, что PriorityQueue поддерживает порядок очереди все время, но Вы можете получить только первый элемент очереди. Вы не можете получить случайный доступ к элементу, например, как PriorityQueue.get(4).
- Если нету дубликатов в коллекции, можно выбрать TreeSet. Также, как и PriorityQueue, TreeSet поддерживает упорядоченный набор все время. Вы можете получить самый маленьний или самыый большой элемент из TreeSet, но вы все равно не можете иметь случайный доступ к элементам.
Проще говоря, Collections.sort() обеспечивает одноразовый упорядоченный список. PriorityQueue и TreeSet поддерживает упорядоченную коллекцию постоянно, за что приходится платить отсутствием индексированного доступа к элементам.
9. Collections.emptyList() или новый экземпляр
Тот же вопрос применяется к emptyMap() и emptySet().
Оба метода возвращают пустой список, но Collections.emptyList() непреложный (immutable) список. Это означает, что вы не можете добавлять новые элементы к "пустому" списку. На фоне, каждый вызов метода Collections.emptyList() фактически не создает новый экземпляр пустого списка. Вместо этого, оно будет использовать снова уже существующий пустой экземпляр. Если Вы знакомы с синглтоном (Singleton, тыц, прим. перевод.) как с паттерном проектирования, Вы должны понять что имеется в виду. Это должно Вам дать большую производительность, если вызывается часто.
10 Копирование коллекции, Collections.copy()
Существует два способа копирования исходного списка в назначенный. Один путь - использование конструктора ArrayList.
ArrayList dstList = new ArrayList(srcList);
Иной способ - использование метода Collections.copy(). Обратите внимание на первую строку: мы выделяем список как минимум такой же длины, что и длина исходного списка, потому что в документации Java о коллекциях сказано:
The destination list must be at least as long as the source list.
Что означает, что конечный список должен быть не короче, чем исходный.
ArrayList dstList = new ArrayList(srcList.size());
Collections.copy(dstList, srcList);
Оба метода являются поверхностным копироваием (shallow copy). Так какая же разница между этими двумя методами?
Во-первых, Collections.copy() не будет перераспределять вместимость коллекции dstList, даже если dstList не будет иметь достаточно пространства для содержания всех элементов из srcList. Вместо этого, он будет бросать IndexOutOfBoundsException. Можно спросить, есть ли польза от этого. Причина в том, что это гарантирует то, что метод запускается линейно по времени. Также, это подходит в случае, когда Вы хотите использовать снова массивы, а не выделять снова память в конструкторе ArrayList.
Вместо заключения
Если после прочтения статьи у Вас еще остались вопросы, смело задавайте их в комментарии. Также, если Вы нашли какую-либо неточность в переводе или еще какую-либо ошибку, то пишите в ЛС, будет поправлена, а Вам будет спасибо.
Оригинал.
ПЕРЕЙДИТЕ В ПОЛНУЮ ВЕРСИЮ
все браво оперируют этим, а определения я не видел…
что такое n — это размерность массива или номер индекса к которому обращаешься? Можно предположить, что О — это единичная операция…, но что это за операция, она веддь тоже разная для разных типов массивов, стало быть и сравнивать их нельзя…
как можна сравнивать листы по методам например по тому ж get(), потому что последний елемент линкен листа я могу достать за O(1) а не за O(n).
в
видимо, мое ООП не настолько сильно) что это означает? откуда ноль?