Коллекции в Java: о чём многие забывают

в 12:15, , рубрики: java, коллекции

Из опыта code-review и ответов на StackOverflow набралось немало моментов, касающихся Java Collections API, которые мне казались очевидными, но другие разработчики о них почему-то не знали или знали, но не чувствовали уверенности их применять. В этой статье я собираю в общую кучу всё, что накопилось.

Содержание:

  1. List.subList
  2. PriorityQueue
  3. EnumSet и EnumMap
  4. Set.add(E) и Set.remove(E) возвращают булево значение
  5. Map.put(K, V), Map.remove(K), List.set(idx, E), List.remove(idx) возвращают предыдущий элемент
  6. Arrays.asList может быть ключом
  7. Collections.max
  8. Map.keySet() и Map.values()
  9. Arrays.asList может быть ключом
  10. Collections.max
  11. 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> leastDistinctN(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 можно использовать только в качестве учебного примера.

На сегодня всё. Программируйте с удовольствием!

Автор: lany

Источник

* - обязательные к заполнению поля


https://ajax.googleapis.com/ajax/libs/jquery/3.4.1/jquery.min.js