Из опыта code-review и ответов на StackOverflow набралось немало моментов, касающихся Java Collections API, которые мне казались очевидными, но другие разработчики о них почему-то не знали или знали, но не чувствовали уверенности их применять. В этой статье я собираю в общую кучу всё, что накопилось.
Про это уже писали, но стоит повторить. Наверно, самый недооценённый метод из Collections API. Бывает, что надо каким-то образом обработать часть списка (например, в алгоритмах семейства «разделяй и властвуй» или при распараллеливании задачи). Многие создают метод или класс, который завязывается на три параметра: List, from и to:
Так незачем делать. Реализации алгоритма должно быть плевать, что она обрабатывает часть списка. Пишите:
И вызывайте
Даже если у вас всё в одном методе, удобнее воспользоваться расширенным циклом for, чем возиться с индексами:
Кроме того, subList — полнофункциональный список, он работает и на запись, внося соответствующие изменения в родительский список. Нужно удалить много элементов из середины списка? Ничего нет проще:
У популярных реализаций вроде ArrayList это выполняется очень быстро.
Надо выяснить, начинается ли список с определённых элементов? И тут subList в руки!
Надо добавить в один список все элементы другого списка за исключением первого? И тут subList придёт на помощь:
Не забывайте, что можно писать
Если subList — самый недооценённый метод, то PriorityQueue — это, на мой взгляд, самый недооценённый класс. Многие сталкиваются с задачей отыскать, скажем, 10 минимальных значений большого несортированного списка. Чаще всего список сортируют и потом берут первые 10 значений. Если исходный список менять нельзя, придётся его ещё скопировать для сортировки. А ведь очередь с приоритетом легко справится с этой задачей:
Такой код в зависимости от данных может работать гораздо быстрее, чем сортировка. Например, для n = 10 и случайно заполненного списка из миллиона элементов очередь с приоритетом почти в сто раз обгоняет подход с сортировкой. При этом дополнительной памяти требуется O(n) и входные элементы можно обрабатывать в потоковом режиме (например, выбрать 10 наименьших чисел из входного файла).
Вообще людям свойственно изучить пару-тройку структур данных и пользоваться ими везде. Не ленитесь, познакомьтесь с разными структурами.
До сих пор встречается код, где значения типа enum используют в качестве ключей в HashSet и HashMap. Хотя это работает, но оно неоправданно расточительно. Существующие специальные классы EnumSet и EnumMap значительно производительнее. Так если в enum не больше 64 разных значений, EnumSet хранит всё в одном поле типа long в битовой маске. EnumMap содержит все значения в обычном массиве той же длины, сколько элементов в enum, а ключи не хранит вовсе. Так как у каждого значения в enum есть порядковый номер ordinal(), можно легко перейти от enum-ключа к элементу массива. Также никогда не нужно менять размер массива.
Часто вижу подобный код:
Не надо забывать, что операция добавления в Set возвращает true, если добавление успешно (то есть элемента не было) и false, если такой элемент уже был. Незачем усложнять код и два раза пробивать элемент по хэш-таблице или двоичному дереву, ведь можно написать:
Аналогично с удалением. Цепочка
Из той же оперы ситуация. Методы, изменяющие или удаляющие элемент в коллекции возвращают предыдущее значение, и этим надо пользоваться. Не надо писать, например, так:
Написать просто
Многие почему-то забывают, что
Также работает
Бывает, что вам нужно сформировать Map или Set, используя кортеж значений. Например, у вас есть PoJo-объекты
Удивительно, насколько часто можно встретить написанный вручную код, который находит максимальный или минимальный элемент чего-то по какому-нибудь критерию. Казалось бы, такая тривиальная задача должна быть давно решена. На самом деле она и так давно решена: есть методы
К примеру, вам нужно найти ключ в Map, соответствующий максимальному значению. Пишите так:
Можно и через Stream API, но
Просто не используйте эти классы. Пользы от них никакой нет. Вместо Stack пользуйтесь ArrayDeque, вместо Vector — ArrayList, вместо Hashtable — HashMap. Если вам нужна потокобезопасность, они вам всё равно не помогут. Возможно, в девятке их всё-таки пометят @Deprecated (смотрите JEP 277).
С LinkedList случай особый. Вроде бы лучшего аналога связного списка нет и ходят легенды, что он на самом деле полезен. В действительности ситуаций, когда LinkedList лучше, чем ArrayList, в реальной жизни исключительно мало. До Java-8 LinkedList ещё мог пригодиться, если вы часто удаляете элементы, идущие не последовательно, по какому-то условию. В Java-8 для этих целей появился
На сегодня всё. Программируйте с удовольствием!
Содержание:
- List.subList
- PriorityQueue
- EnumSet и EnumMap
- Set.add(E) и Set.remove(E) возвращают булево значение
- Map.put(K, V), Map.remove(K), List.set(idx, E), List.remove(idx) возвращают предыдущий элемент
- Map.keySet() и Map.values()
- Arrays.asList может быть ключом
- Collections.max
- LinkedList, Stack, Vector, Hashtable
List.subList
Про это уже писали, но стоит повторить. Наверно, самый недооценённый метод из Collections API. Бывает, что надо каким-то образом обработать часть списка (например, в алгоритмах семейства «разделяй и властвуй» или при распараллеливании задачи). Многие создают метод или класс, который завязывается на три параметра: List, from и to:
void processListPart(List<Item> list, int from, int to) {
for(int idx = from; idx < to; idx++) {
Item item = list.get(idx);
...
}
}
Так незачем делать. Реализации алгоритма должно быть плевать, что она обрабатывает часть списка. Пишите:
void processList(List<Item> list) {
for(Item item : list) {
...
}
}
И вызывайте
processList(list.subList(from, to));
Даже если у вас всё в одном методе, удобнее воспользоваться расширенным циклом for, чем возиться с индексами:
for(Item item : list.subList(from, to)) {...}
Кроме того, subList — полнофункциональный список, он работает и на запись, внося соответствующие изменения в родительский список. Нужно удалить много элементов из середины списка? Ничего нет проще:
list.subList(from, to).clear();
У популярных реализаций вроде ArrayList это выполняется очень быстро.
Надо выяснить, начинается ли список с определённых элементов? И тут subList в руки!
List<String> prefix = Arrays.asList("a", "prefix", "values");
if(myList.size() >= prefix.size() &&
myList.subList(0, prefix.size()).equals(prefix)) {...}
Надо добавить в один список все элементы другого списка за исключением первого? И тут subList придёт на помощь:
list1.addAll(list2.subList(1, list2.size()));
Не забывайте, что можно писать
Arrays.asList(array).subList(from, to)
, поэтому вышесказанное применимо и для непримитивных массивов. Структурно менять вы их не сможете, но передавать кусок массива в метод, принимающий список для чтения — легко.PriorityQueue
Если subList — самый недооценённый метод, то PriorityQueue — это, на мой взгляд, самый недооценённый класс. Многие сталкиваются с задачей отыскать, скажем, 10 минимальных значений большого несортированного списка. Чаще всего список сортируют и потом берут первые 10 значений. Если исходный список менять нельзя, придётся его ещё скопировать для сортировки. А ведь очередь с приоритетом легко справится с этой задачей:
public static <T extends Comparable<T>> List<T> leastN(Collection<T> input, int n) {
assert n > 0;
PriorityQueue<T> pq = new PriorityQueue<>(Collections.reverseOrder());
for (T t : input) {
if (pq.size() < n) {
pq.add(t);
} else if (pq.peek().compareTo(t) > 0) {
pq.poll();
pq.add(t);
}
}
List<T> list = new ArrayList<>(pq);
Collections.sort(list);
return list;
}
Такой код в зависимости от данных может работать гораздо быстрее, чем сортировка. Например, для n = 10 и случайно заполненного списка из миллиона элементов очередь с приоритетом почти в сто раз обгоняет подход с сортировкой. При этом дополнительной памяти требуется O(n) и входные элементы можно обрабатывать в потоковом режиме (например, выбрать 10 наименьших чисел из входного файла).
Вообще людям свойственно изучить пару-тройку структур данных и пользоваться ими везде. Не ленитесь, познакомьтесь с разными структурами.
EnumSet и EnumMap
До сих пор встречается код, где значения типа enum используют в качестве ключей в HashSet и HashMap. Хотя это работает, но оно неоправданно расточительно. Существующие специальные классы EnumSet и EnumMap значительно производительнее. Так если в enum не больше 64 разных значений, EnumSet хранит всё в одном поле типа long в битовой маске. EnumMap содержит все значения в обычном массиве той же длины, сколько элементов в enum, а ключи не хранит вовсе. Так как у каждого значения в enum есть порядковый номер ordinal(), можно легко перейти от enum-ключа к элементу массива. Также никогда не нужно менять размер массива.
Set.add(E) и Set.remove(E) возвращают булево значение
Часто вижу подобный код:
if(!set.contains(item)) {
set.add(item);
// do something
} else {
// do something else
}
Не надо забывать, что операция добавления в Set возвращает true, если добавление успешно (то есть элемента не было) и false, если такой элемент уже был. Незачем усложнять код и два раза пробивать элемент по хэш-таблице или двоичному дереву, ведь можно написать:
if(set.add(item)) {
// do something
} else {
// do something else
}
Аналогично с удалением. Цепочка
if(set.contains(item)) { set.remove(item); ... }
заменяется на if(set.remove(item)) { ... }
.Map.put(K, V), Map.remove(K), List.set(idx, E), List.remove(idx) возвращают предыдущий элемент
Из той же оперы ситуация. Методы, изменяющие или удаляющие элемент в коллекции возвращают предыдущее значение, и этим надо пользоваться. Не надо писать, например, так:
Item item = myMap.get(key);
myMap.put(key, newItem);
Написать просто
Item item = myMap.put(key, newItem);
. Хотите поменять местами две записи в Map с ключами key1, key2? Временная переменная не нужна:myMap.put(key1, myMap.put(key2, myMap.get(key1)));
Map.keySet() и Map.values()
Многие почему-то забывают, что
Map.keySet()
и Map.values()
возвращают отображения исходного Map, которые позволяют удалять элементы (если Map модифицируемый). Надо оставить в Map только записи с определёнными значениями (и любыми ключами)? Пожалуйста:myMap.values().retainAll(toRetain);
Также работает
removeAll
, а с Java-8 ещё и removeIf
:// Сгруппируем сотрудников по названиям подразделений
Map<String, List<Employee>> perDepartment = employees.stream().collect(groupingBy(Employee::getDepartmentName, HashMap::new, toList()));
// Оставим только крупные подразделения с числом сотрудников от 10
perDepartment.values().removeIf(list -> list.size() < 10);
Arrays.asList может быть ключом
Бывает, что вам нужно сформировать Map или Set, используя кортеж значений. Например, у вас есть PoJo-объекты
Item
, у которых имеются поля name, type, version
. У них уже написан equals
и hashCode
, их можно складывать в HashSet
, всё нормально. Но вы хотите выбрать из коллекции уникальные объекты только по полям name
и type
, игнорируя version. Менять существующие equals
и hashCode
нельзя. В таких ситуациях люди часто создают отдельный класс только с полями name
и type
и используют его в качестве ключа. Однако для одноразовой операции проще использовать Arrays.asList()
:Map<List<Object>, Item> map = new HashMap<>();
for(Item item : items) {
map.put(Arrays.asList(item.name, item.type), item);
}
Collection<Item> unique = map.values();
Arrays.asList()
создаёт список из нужного числа элементов и у него как раз подходящие реализации equals
и hashCode
: никакой boilerplate не нужен. Так можно создать ключ любой длины, причём корректно обработаются null-значения и примитивы (брагодаря боксингу). Не сработает только, если вы хотите в составе ключа иметь массив.Collections.min/max
Удивительно, насколько часто можно встретить написанный вручную код, который находит максимальный или минимальный элемент чего-то по какому-нибудь критерию. Казалось бы, такая тривиальная задача должна быть давно решена. На самом деле она и так давно решена: есть методы
Collections.min
и Collections.max
. Раньше было не очень удобно писать компараторы, но в Java-8 всё стало легче.К примеру, вам нужно найти ключ в Map, соответствующий максимальному значению. Пишите так:
maxKey = Collections.max(map.entrySet(), Map.Entry.comparingByValue()).getKey();
Можно и через Stream API, но
Collections.max()
несколько быстрее. Если вы не можете использовать Java-8 и компараторы вроде Entry.comparingByValue()
вам недоступны, их нетрудно написать.Stack, Vector, Hashtable, LinkedList
Просто не используйте эти классы. Пользы от них никакой нет. Вместо Stack пользуйтесь ArrayDeque, вместо Vector — ArrayList, вместо Hashtable — HashMap. Если вам нужна потокобезопасность, они вам всё равно не помогут. Возможно, в девятке их всё-таки пометят @Deprecated (смотрите JEP 277).
С LinkedList случай особый. Вроде бы лучшего аналога связного списка нет и ходят легенды, что он на самом деле полезен. В действительности ситуаций, когда LinkedList лучше, чем ArrayList, в реальной жизни исключительно мало. До Java-8 LinkedList ещё мог пригодиться, если вы часто удаляете элементы, идущие не последовательно, по какому-то условию. В Java-8 для этих целей появился
List.removeIf
, который в ArrayList, конечно, реализован оптимальнее (элементы передвигаются только один раз). Если вам надо сделать много вставок в разные места (задача сама по себе экзотическая), скорее всего быстрее будет создать новый ArrayList, чем вставлять в существующий LinkedList. Ну и помните, что LinkedList кушает в несколько раз больше памяти, так как каждый элемент — это отдельный объект в куче со ссылками на следующий и предыдущий. LinkedList можно использовать только в качестве учебного примера.На сегодня всё. Программируйте с удовольствием!