Что могут спросить на собеседовании: структуры данных в Java. Часть 2

ЧАСТЬ 1 Сейчас говорим о базе, которую должен знать каждый Java developer. О тех классических знаниях, с которых все и начинается. Сегодня хотелось бы затронуть одну из основополагающих тем любого собеседования — структуры данных в Java. Итак, вместо хождения вокруг да около, мы начнем. Ловите продолжение списка вопросов, которые могут вам задать по этой теме на собеседовании.

6. Расскажите о List

List — это интерфейс, представляющий упорядоченную структуру объектов, которая и называется списком.“Фишка” этой структуры — то, что элементы, содержащиеся в List, можно вставить, изменить или удалить по индексу, то есть внутреннему идентификатору List. Иными словами, индекс означает: «сколько элементов от начала списка». У первого элемента List индекс 0, у второго — 1, и так далее. Таким образом, пятый элемент находится на расстоянии четырех элементов от начала списка. Как говорилось выше, в списке важен порядок добавления элементов. Поэтому структура данных и называется списком. Перечислим уникальные для этой структуры методы, которые направлены на работу с элементами по индексу:

• get — возвращает элемент в указанной позиции (по значению индекса),
• remove — удаляет элемент в указанной позиции,
• set — заменяет элемент в указанной позиции на указанный в методе элемент.

Основные реализации — ArrayList и LinkedList. Подробнее о них поговорим немного позже. Vector — список, который ориентирован на многопоточное использование, поэтому в данном классе каждый метод синхронизирован. Но учтите, что если вы хотите обезопасить некоторые действия со списками, вы будете синхронизировать целую последовательность операций. А синхронизация отдельных операций и менее безопасна, и гораздо медленнее. Конечно, Vector также имеет накладные расходы на блокировку, даже если вам эта блокировка и не нужна. Поэтому сейчас этот класс считается устаревшим и не используется. Кстати: ArrayList является аналогом Vector, но не использует блокировку, поэтому используется повсеместно. Stack — это подкласс класса Vector с одним конструктором по умолчанию и всеми методами класса Vector, а также несколькими собственными (о них мы поговорим чуть ниже). В качестве примера можно представить процесс в виде стопки папок с документами. Наверх стопки вы кладете по одной папке, и брать данные папки можно только в обратном порядке, начиная с верхней. Собственно, это и есть механизм типа LIFO, то есть Last In First Out, последний пришел — первым ушел. Стек реализует свои собственные методы:

• push — добавляет переданный элемент на вершину стека;
• peek — возвращает элемент, который находится на вершине стека;
• pop — также возвращает элемент, который находится на вершине стека, но при этом удаляет его;
• empty — проверяет, пуст ли стек — true, или нет — false;
• search — выполняет поиск заданного элемента в стеке. Если элемент найден, возвращается его порядковый номер относительно верхушки стека. Если же элемент не найден, возвращается значение -1.

В данный момент подкласс Stack фактически не используется в силу своей простоты и негибкости, но, тем не менее, он может вам встретиться. Например, когда вы получаете некоторую ошибку, и в консоли видите стек сообщений о ней. Подробнее о стеке и очереди можно почитать вот в этой статье.

7. Расскажите о Map

Как сказано выше, Map — это коллекция имеющая отдельную структуру интерфейсов и их реализаций. Отдельная она потому, что здесь значения не хранятся по одному, а в паре “ключ – значение”.Основные методы Map:

• put(K key, V value) — добавление элемента в Map;
• get(Object key) — поиск значения по ключу;
• containsKey(Object key) — проверка Map на наличие данного ключа;
• containsValue(Object value) — проверка Map на наличие данного значения;
• remove(Object key) — удаление значения по его ключу.

Как вы видите, большинство операций работает с помощью использования ключа. В качестве ключей, как правило, выбираются неизменные объекты (immutable). Типичный пример данного объекта — String. Основные реализации Map:

1. HashMap — предназначена для хранения значений в произвольном порядке, но позволяет быстро искать элементы карты. Позволяет задавать ключ ключевым словом null, но не более одного раза, т.к. пары с одинаковыми ключами записываются поверх друг друга. Главным условием является уникальность ключей: значения же могут повторяться (может быть несколько null значений).
2. LinkedHashMap — аналог HashMap, который хранит значения в порядке добавления. Соответственно, как и LinkedList, у него есть header — голова двусвязного списка. При инициализации указывает сам на себя.

   Также у LinkedHashMap есть accessOrder, который указывает, каким образом будет осуществляться доступ к элементам во время использования итератора. При accessOrder false доступ будет осуществляться в порядке вставки элементов. При значении true элементы будут в порядке последнего доступа (элемент, к которому было последнее обращение будет помещен в конец).

3. TreeMap — это Map, сортирующая элементы по значениям ключа. Аналог TreeSet, но для пар с ориентировкой на значения ключей. Для задания правил сортировки TreeMap ключи должны реализовывать Comparable интерфейс. В ином случае должен быть Comparator, ориентированный на ключи (тот, который задается в конструктор TreeMap), TreeSet — реализован с объектом TreeMap внутри, в котором, собственно, и происходит вся магия.

   Подробнее про сортировку в TreeMap с помощью красно-черных деревьев можно почитать в статье об особенностях TreeMap.

4. Hashtable — аналогичен HashMap, но но не позволяет хранить null ни в качестве ключей, ни в качестве значений. Он тщательно синхронизирован с точки зрения многопоточности, что в свою очередь означает, что он безопасен с точки зрения многопоточности. Но данная реализация устаревшая и медленная, поэтому сейчас вы и не встретите Hashtable в более-менее новых проектах.

8. ArrayList vs LinkedList. Какой предпочтительней использовать?

Этот вопрос, пожалуй, самый популярный по структурам данных и несет в себе некоторые подводные камни. Прежде чем отвечать на него, давайте узнаем подробнее об этих структурах данных. ArrayList реализует интерфейс List, работает за счет внутреннего массива, который расширяется по мере необходимости. Когда внутренний массив полностью заполняется, и при этом нужно вставить новый элемент то создается новый массив, с размером (oldSize * 1,5) +1. После этого все данные из старого массива копируются в новый +новый элемент, старый же будет удален сборщиком мусора. Метод add добавляет элемент в последнюю пустую ячейку массива. То есть, если у нас там уже есть 3 элемента, он добавит следующий в 4-ю ячейку. Давайте пройдемся по производительности базовых методов:

• get(int index) — взятие элемента в массиве по индексу работает быстрее всего за O(1);
• add(Object obj) — если достаточно места во внутреннем массиве для нового элемента, то при обычной вставке будет затрачено время O(1), так как добавление идет целенаправленно в последнюю ячейку.

  Если же нужно создавать новый массив и копировать в него содержимое, то время у нас будет прямо пропорционально количеству элементов в массиве O(n);

• remove(int index) — при удалении элемента, к примеру, из середины, мы получим время O(n/2), так как нужно будет передвигать элементы справа от него на одну ячейку назад. Соответственно, если удаление с начала списка, то O(n), c конца — O(1);
• add(int index, Object obj) — ситуация, схожая с удалением: при добавлении в середину нам нужно будет передвинуть элементы справа на одну ячейку вперед, поэтому время — O(n/2). Разумеется, с начала — O(n), с конца — O(1);
• set(int index, Object obj) — тут ситуация иная, так как требуется только найти нужный элемент и записать поверх него, не передвигая остальные, поэтому O(1).

Подробнее про ArrayList — в этой статье. LinkedList реализует сразу два интерфейса — List и Queue, поэтому и владеет свойствами и методами, присущими обоим структурам данных. От List он взял доступ к элементу по индексу, от Queue — наличие “головы” и “хвоста”. Внутри он реализован как структура данных, представляющая двусвязный список. То есть, у каждого элемента есть ссылка на следующий и предыдущий, кроме “хвоста” и “головы”.

• get(int index) — при поиске элемента, который находится в середине списка, начинается перебор всех элементов по порядку, пока не будет найден нужный. По логике поиск должен занимать O(n/2), но у LinkedList есть еще и хвост, поэтому перебор ведется одновременно с двух сторон. Соответственно, время уменьшается до O(n/4).

  Если же элемент будет недалеко от начала списка или конца, то и время будет O(1);

• add(Object obj) — при добавлении нового элемента, у элемента-”хвоста” добавится ссылка на следующий элемент, а новый получит ссылку на этот предыдущий элемент и станет новым “хвостом”. Соответственно, время будет O(1);
• remove(int index) — логика, схожая с методом get(int index). Для удаления элемента из середины списка, его нужно сначала найти. Это опять же O(n/4), в то время как само удаление фактически ничего не занимает, так как там только меняются указатель соседних объектов (они начинают ссылаться друг на друга). Если элемент в начале или в конце, то опять же — O(1);
• add(int index, Object obj) и set(int index, Object obj) — у методов временная сложность будет идентична get(int index), так как основное время занимает поиск элемента. Поэтому для середины списка — O(n/4), для начала — O(1).

Больше о работе с LinkedList рассказано в этой статье. Давайте все это рассмотрим в таблице:Как вы уже наверное поняли, однозначно ответить на данный вопрос нельзя. Ведь при разных ситуациях они и работают с разной скоростью. Поэтому, когда вам задают подобный вопрос, вы должны сразу спросить, на что будет ориентирован данный список и какие операции будут чаще всего производиться. Уже отталкиваясь от этого, давать ответ, но с пояснениями, почему именно так. Подведем же небольшие итоги по нашему сравнению: ArrayList:

• лучший выбор, если наиболее частая операция — поиск элемента, перезапись элемента;
• худший выбор, если операция — вставка и удаление в начале-середине, потому что будут проходить операции сдвига элементов справа.

LinkedList:

• лучший выбор, если нашей частой операцией является вставка и удаление в начале-середине;
• худший выбор, если наиболее частая операция — поиск.

9. Как хранятся элементы в HashMap?

Коллекция HashMap содержит в себе внутренний массив Node [] table, ячейки которого еще называют бакетами (корзинами). Node содержат в себе:

• key — ссылку на ключ,
• value — ссылку на значение,
• hash — значение hash,
• next — ссылку на следующий Node.

В одной ячейке массива table[] может содержаться ссылка на объект Node со ссылкой на следующий элемент Node, а он может иметь ссылку на другой, и так далее… В итоге, данные элементы Node могут образовывать односвязный список, с элементами со ссылкой на следующие. При этом значение hash у элементов одной цепочки одинаковое. После небольшого отступления давайте посмотрим, как происходит сохранение элементов в HashMap:

1. Ключ проверяется на равенство null. Если он null, то key будет сохранен в ячейке table[0], потому что хэш-код для null всегда равен 0.
2. Если ключ не null, то у объекта key вызывается метод hashcode(), который выдаст его хэш-код. Этот хэш-код используется для определения ячейки массива, где будет храниться объект Node.
3. Далее данный hashcode помещается в внутренний метод hash(), который высчитывает hashcode, но уже в пределах размера массива table[].
4. Дальше, в зависимости от значения hash, Node помещается в конкретную ячейку в массиве table[].
5. Если же ячейка table[], используемая для сохранения текущего элемента Node не пуста, а уже имеет какой-то элемент, то происходит перебор элементов Node по значению next, пока не будет достигнут последний элемент. То есть, тот, у которого поле next равно null.

   Во время данного перебора сравниваются ключ охраняемого объекта Node с ключами перебираемых:

   • если будет найдено соответствие, то перебор закончится, и новый Node перезапишет Node, в котором найдено соответствие (перезапишется только его поле value);
   • если соответствия ключей не найдены, то новый Node станет последним в этом списке, а предыдущий будет иметь ссылку next на него.

Часто на собеседованиях мелькает вопрос: что такое коллизия? Ситуацию, когда в ячейке массива table[] хранится не один элемент, а цепочка из двух и более, и называется коллизия. В обычных случаях, когда в одной ячейке table[] хранится только один элемент, доступ к элементам HashMap имеет константную временную сложность O(1). Но когда в ячейке с нужным элементом присутствует цепочка элементов (коллизия), то O(n), так как в таком случае время прямо пропорционально зависит от количества перебираемых элементов.

10. Расскажите об итераторе

В схеме с отображением иерархии Collection выше интерфейс Collection был тем, с чего начиналась вся иерархия, но на практике все не совсем так. Collection наследуется от интерфейса с методом iterator(), который возвращает объект, реализующий интерфейс Iterator<E>. Интерфейс Iterator имеет вид:

public interface Iterator <E>{
   
    E next();
    boolean hasNext();
    void remove();
}

next() — вызывая данный метод, можно будет получить следующий элемент. hasNext() — дает возможность узнать, есть ли следующий элемент, и не достигнут ли конец коллекции. И когда элементы еще есть, то hasNext() вернет значение true. Как правило, hasNext() вызывается перед методом next(), так как при достижении конца коллекции next() будет выбрасывать исключение NoSuchElementException. remove() — удаляет элемент, который получен последним вызовом next(). Предназначением Iterator является перебор элементов. Например:

Set<Integer> values = new TreeSet<>();
  values.add(5);
values.add(3);
values.add(6);
values.add(8);
values.add(2);
values.add(4);
values.add(1);
values.add(7);

Iterator<Integer> iter = values.iterator();
while(iter.hasNext()){
  System.out.println(iter.next());
}

Собственно, цикл for-each loop и реализован под капотом с помощью итератора. Подробнее об этом можно почитать тут. List предоставляет свою версию итератора, но более крутую и навороченную — ListIterator. Данный интерфейс расширяет Iterator, и у него есть дополнительные методы:

• hasPrevious вернет true, если в коллекции имеется предыдущий элемент, иначе — false;
• previous возвращает текущий элемент и переходит к предыдущему; если такого нет, то выбрасывается исключение NoSuchElementException;
• add вставит переданный объект перед элементом, который должен быть возвращен следующим вызовом next();
• set присваивает текущему элементу ссылку на переданный объект;
• nextIndex возвращает индекс следующего элемента. Если такого нет, то возвращается размер списка;
• previousIndex возвращает индекс предыдущего элемента. Если такого нет, то возвращается число -1.

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