Готовимся к собеседованию: что нужно знать о коллекциях в Java

Галопом по Европам, или Кратко об интерфейсах

Set — это неупорядоченное множество уникальных элементов.

Например, мешочек с бочонками для игры в лото: каждый номер от 1 до 90 встречается в нём ровно один раз, и заранее неизвестно, в каком порядке бочонки вынут при игре.

List — упорядоченный список, в котором у каждого элемента есть индекс. Дубликаты значений допускаются.

Например, последовательность букв в слове: буквы могут повторяться, при этом их порядок важен.

Queue — очередь. В таком списке элементы можно добавлять только в хвост, а удалять — только из начала. Так реализуется концепция FIFO (first in, first out) — «первым пришёл — первым ушёл». Вам обязательно напомнят это правило, если попробуете пролезть без очереди в магазине:

А ещё есть LIFO (last in, first out), то есть «последним пришёл — первым ушёл». Пример — стопка рекламных буклетов на ресепшене отеля: первыми забирают самые верхние (положенные последними). Структуру, которая реализует эту концепцию, называют стеком.

Deque может выступать и как очередь, и как стек. Это значит, что элементы можно добавлять как в её начало, так и в конец. То же относится к удалению.

Map состоит из пар «ключ-значение». Ключи уникальны, а значения могут повторяться. Порядок элементов не гарантирован. Map позволяет искать объекты (значения) по ключу.

Пример: стопка карточек с иностранными словами и их значениями. Для каждого слова (ключ) на обороте карточки есть вариант перевода (значение), а вытаскивать карточки можно в любом порядке.

Соберём всё вместе

Такие разные реализации

Реализаций интерфейсов так много, что при желании можно организовать вполне себе упорядоченный Map и даже отсортированное множество. Пройдёмся кратко по основным классам.

Реализации List

Класс ArrayList подойдёт в большинстве случаев, если вы уже определились, что вам нужен именно список (а не Map, например).

Строится на базе обычного массива. Если при создании не указать размерность, то под значения выделяется 10 ячеек. При попытке добавить элемент, для которого места уже нет, массив автоматически расширяется — программисту об этом специально заботиться не нужно.

Список проиндексирован. При включении нового элемента в его середину все элементы с большим индексом сдвигаются вправо:

При удалении элемента все остальные с бо́льшим индексом сдвигаются влево:

Класс LinkedList реализует одновременно List и Deque. Это список, в котором у каждого элемента есть ссылка на предыдущий и следующий элементы:

Благодаря этому добавление и удаление элементов выполняется быстро — времязатраты не зависят от размера списка, так как элементы при этих операциях не сдвигаются: просто перестраиваются ссылки.

В целом так и есть, но вы можете блеснуть эрудицией — рассказать, что под капотом. При добавлении элементов в ArrayList (или их удалении) вызывается нативный метод System.arraycopy. В нём используются ассемблерные инструкции для копирования блоков памяти. Так что даже для больших массивов эти операции выполняются за приемлемое время.

public void add(int index, E element) {
   rangeCheckForAdd(index);

   ensureCapacityInternal(size + 1);  // Increments modCount!!
   System.arraycopy(elementData, index, elementData, index + 1,
                    size - index);
   elementData[index] = element;
   size++;
}

Реализации Queue

Про одну из них, LinkedList, мы рассказали выше.

Класс ArrayDeque — это реализация двунаправленной очереди в виде массива с переменным числом элементов.

Новые значения можно добавлять в начало или конец списка, и удалять оттуда же. Причём эти операции выполняются быстрее, чем при использовании LinkedList.

Класс PriorityQueue — упорядоченная очередь. По умолчанию элементы добавляются в естественном порядке: числа по возрастанию, строки по алфавиту и так далее, либо алгоритм сравнения задаёт разработчик.

Этот класс может быть полезен, например, для нахождения n минимальных чисел в большом неупорядоченном списке:

public static <T extends Comparable<T>> List<T> findLeastN(Collection<T> collection, int n) {
   checkIfNGreaterZero(n); //проверим, что n > 0 
   checkIfCollectionNotNull(collection); //проверим, что список не равен null
   
   PriorityQueue<T> priorityQueue = new     PriorityQueue<>(Collections.reverseOrder());/*создадим очередь с обратной сортировкой*/
   for (T t : collection) {/*для каждого элемента переданной коллекции*/
       if (priorityQueue.size() < n) {//если размер очереди < n
           priorityQueue.add(t);//добавим элемент t в очередь
       } else if (priorityQueue.peek().compareTo(t) > 0) {/*иначе, если первый, а значит максимальный, элемент очереди(его вернёт peek) больше t*/
           priorityQueue.poll(); //удалим первый элемент очереди
           priorityQueue.add(t);//добавим вместо него t        
       }
   }
   List<T> list = new ArrayList<>(priorityQueue);
   Collections.sort(list);/*создадим список из полученной очереди и отсортируем его в естественном порядке (задан по умолчанию в методе sort)*/
   return list;
}

Такая реализация выгоднее по скорости и объёму памяти, чем подход с сортировкой первоначального списка.

Реализации Set

Класс HashSet использует для хранения данных в хеш-таблице. Это значит, что при манипуляциях с элементами используется хеш-функция — hashCode() в Java.

Например, администратор в гостинице может класть ключ в коробку с номером от 1 до 9, вычисляя его по такому алгоритму: складывать все цифры номера, пока не получится одноразрядное число.

Здесь алгоритм вычисления — хеш-функция, а результат вычисления — хеш-код.

Тогда ключ от номера 356 попадёт в коробку 5 (3 + 5 + 6 = 14; 1 + 4 = 5), а ключ от номера 123 — в коробку с номером 6.

Добавление, поиск и удаление элементов при такой организации происходит за постоянное время, независимо от числа элементов в коллекции.

О классе TreeSet вспоминают в тех случаях, когда множество должно быть упорядочено. Каким образом упорядочивать — определяет разработчик при создании нового TreeSet. По умолчанию элементы располагаются в естественном порядке. Организованы они в виде красно-чёрного дерева.

Реализации Map

Класс HashMap хранит данные в виде хеш-таблицы, как и HashSet. Более того, HashSet внутри использует HashMap. При этом ключом выступает сам элемент.

// Dummy value to associate with an Object in the backing Map
private static final Object PRESENT = new Object();

/**
* Constructs a new, empty set; the backing <tt>HashMap</tt> instance has
* default initial capacity (16) and load factor (0.75).
*/
public HashSet() {
   map = new HashMap<>();
}

Класс TreeMap строится тоже на базе красно-чёрного дерева. Элементы здесь упорядочены (в естественном или заданном при создании порядке) в каждый момент времени. При этом вставка и удаление более затратны, чем в случае с HashMap.

Класс LinkedHashMap расширяет возможности HashMap тем, что позволяет итерироваться по элементам в порядке их добавления. Как и в LinkedList, здесь каждая пара-значение содержит ссылку на предыдущий и последующий элементы.

Попрактикуемся

Чтобы убедиться, что вы не просто вызубрили теорию, а хорошо понимаете предмет, на собеседовании вам могут предложить задания вроде «что произойдёт при выполнении кода»

Разберём типовые задачи на понимание коллекций.

Задачи для ArrayList

Вариант попроще

Что будет напечатано после выполнения кода ниже:

import java.util.ArrayList;
 
public class SimpleTestArrayList {
 
   public static void main (String[] args){
       ArrayList<String> list = new ArrayList<>();
       list.add("test1");
       list.add("test2");
       list.add("test3");
       System.out.print(list.get(1)+":");
       list.add(1, "test4");
       System.out.print(list.get(1)+":");
       for (int i=0; i< list.size(); i++){
           System.out.print(list.get(i)+":");
       }
   }
}

Правильный ответ: test2:test4:test1:test4:test2:test3:

Объяснение

Элементы в ArrayList нумеруются начиная с нуля. Поэтому элемент с номером 1 — это test2.

Следующим действием мы добавляем строку «test4» в ячейку с индексом 1. При этом элементы с бо́льшим индексом сдвигаются вправо.

Вторая часть вывода (test4) показывает, что теперь по индексу 1 извлекается именно test4.

Далее мы обходим все элементы списка и убеждаемся, что они выводятся именно в порядке добавления.

Вариант посложнее

Что будет выведено при выполнении кода:

import java.util.ArrayList;

public class TestArrayList {
   public static void main(String args[]) {
       ArrayList<String> list = new ArrayList<>();
       String t1 = "test1";
       String t2 = "test2";
       list.add(t1);
       list.add(t2);
       System.out.print(list.size() + ":");
       t1 = "test3";
       list.remove(t1);
       System.out.print(list.size());
   }
}

Правильный ответ: 2:2

Объяснение

Первая часть понятна: добавили два элемента, поэтому размер списка равен двум. Остаётся вопрос: почему не был удалён «test1»?

Перед удалением элемента его нужно найти в списке. ArrayList и остальные коллекции, которые не используют алгоритмы хеширования, применяют для поиска метод equals().

Строки сравниваются по значению, поэтому «test3» не эквивалентно «test1» и «test2». А раз ни один элемент не соответствует критерию поиска, ничего не удалится — размер списка останется прежним.

Проверьте себя: подумайте, что произойдёт, если вместо

 list.remove(t1);

написать

list.remove(“test1”);

Задачи для Set

Вариант попроще

Что выведет фрагмент кода ниже:

import java.util.HashSet;
 
public class SimpleTestSet {
 
   public static void main (String[] args){
       HashSet<String> set = new HashSet<>();
       set.add("Иван");
       set.add("Марья");
       set.add("Пётр");
       set.add("Иван");
       System.out.print(set.size()+":");
       for (String s: set){
           System.out.print(s+" ");
       }
   }
}

Правильный ответ: 3:, а дальше точно не известно.

Объяснение

Так как строки сравниваются по значению, а дубликаты во множествах недопустимы, второй «Иван» не станет частью множества. В итоге размер множества будет равен 3.

В каком порядке будут выведены элементы множества — определённо мы сказать не можем: во множествах порядок добавления не сохраняется.

Вариант посложнее

Что выведет фрагмент кода:

import java.util.HashSet;

class Person {
   String name;
   Person(String name) { this.name = name; }
   public String toString() { return name; }
}

class TestHashSet {
   public static void main(String args[]) {
       HashSet<Person> set = new HashSet<>();
       Person p1 = new Person("Иван");
       Person p2 = new Person("Мария");
       Person p3 = new Person("Пётр");
       Person p4 = new Person("Мария");
       set.add(p1);
       set.add(p2);
       set.add(p3);
       set.add(p4);
       System.out.print(set.size());
   }
}

Правильный ответ: 4.

Объяснение

Как же так, ведь во множество должны попадать уникальные элементы?

Прежде чем добавить новый элемент в множество, вычисляется его hashCode() — чтобы определить бакет, куда он может быть помещён.

Если бакет пуст, элемент будет добавлен. Иначе уже добавленные элементы с таким же значением хеша сравниваются с кандидатом при помощи метода equals(). Если дубликат не найден, новый элемент становится частью множества. Он попадёт в тот же бакет.

Мы добавляем в Set объекты типа Person — созданного нами класса. Этот класс, как и все ссылочные типы, наследуется от класса Object.

Так как мы не переопределили метод hashCode(), будет использована родительская реализация. В ней хеш вычисляется на основе данных адреса (реализация зависит от JVM).

Метод equals() тоже не переопределён. В классе-родителе этот метод просто сравнивает ссылки на объекты. Это значит, что даже если хеш случайно совпадёт для каких-то из четырёх элементов, equals() в любом случае вернёт false.

Таким образом, каждый из четырёх кандидатов попадёт в множество.

Проверьте себя: изменится ли что-нибудь, если переопределить hashCode() вот так:

@Override
public int hashCode() {
   return 10;
}

А если ещё и equals() переопределить, как на фрагменте ниже:

@Override
public boolean equals(Object o) {
   return true;
}

Что дальше?

Если хотите освоить программирование на Java — приходите на наш курс «Профессия Java-разработчик». Вы изучите коллекции, узнаете о многопоточности, работе с сетью и базами данных с помощью магии Java. А мы проверим домашку, познакомим с единомышленниками, поможем устроиться на работу.