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

Из опыта 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 list, int from, int to) {
    for(int idx = from; idx < to; idx++) {
        Item item = list.get(idx);
        ...
    }
}


Так незачем делать. Реализации алгоритма должно быть плевать, что она обрабатывает часть списка. Пишите: 

void processList(List 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 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 > List leastDistinctN(Collection input, int n) {
    assert n > 0;
    PriorityQueue 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 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> 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, Item> map = new HashMap<>();
for(Item item : items) {
        map.put(Arrays.asList(item.name, item.type), item);
}
Collection 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 можно использовать только в качестве учебного примера.

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

© Habrahabr.ru