6. Расскажите о List
List — это интерфейс, представляющий упорядоченную структуру объектов, которая и называется списком.“Фишка” этой структуры — то, что элементы, содержащиеся в List, можно вставить, изменить или удалить по индексу, то есть внутреннему идентификатору List. Иными словами, индекс означает: «сколько элементов от начала списка». У первого элемента List индекс 0, у второго — 1, и так далее. Таким образом, пятый элемент находится на расстоянии четырех элементов от начала списка. Как говорилось выше, в списке важен порядок добавления элементов. Поэтому структура данных и называется списком. Перечислим уникальные для этой структуры методы, которые направлены на работу с элементами по индексу:- get — возвращает элемент в указанной позиции (по значению индекса),
- remove — удаляет элемент в указанной позиции,
- set — заменяет элемент в указанной позиции на указанный в методе элемент.
- push — добавляет переданный элемент на вершину стека;
- peek — возвращает элемент, который находится на вершине стека;
- pop — также возвращает элемент, который находится на вершине стека, но при этом удаляет его;
- empty — проверяет, пуст ли стек — true, или нет — false;
- search — выполняет поиск заданного элемента в стеке. Если элемент найден, возвращается его порядковый номер относительно верхушки стека. Если же элемент не найден, возвращается значение -1.
7. Расскажите о Map
Как сказано выше, Map — это коллекция имеющая отдельную структуру интерфейсов и их реализаций. Отдельная она потому, что здесь значения не хранятся по одному, а в паре “ключ – значение”.Основные методы Map:- put(K key, V value) — добавление элемента в Map;
- get(Object key) — поиск значения по ключу;
- containsKey(Object key) — проверка Map на наличие данного ключа;
- containsValue(Object value) — проверка Map на наличие данного значения;
- remove(Object key) — удаление значения по его ключу.
- HashMap — предназначена для хранения значений в произвольном порядке, но позволяет быстро искать элементы карты. Позволяет задавать ключ ключевым словом null, но не более одного раза, т.к. пары с одинаковыми ключами записываются поверх друг друга. Главным условием является уникальность ключей: значения же могут повторяться (может быть несколько null значений).
- LinkedHashMap — аналог HashMap, который хранит значения в порядке добавления. Соответственно, как и LinkedList, у него есть header — голова двусвязного списка. При инициализации указывает сам на себя.
Также у LinkedHashMap есть accessOrder, который указывает, каким образом будет осуществляться доступ к элементам во время использования итератора. При accessOrder false доступ будет осуществляться в порядке вставки элементов. При значении true элементы будут в порядке последнего доступа (элемент, к которому было последнее обращение будет помещен в конец).
- TreeMap — это Map, сортирующая элементы по значениям ключа. Аналог TreeSet, но для пар с ориентировкой на значения ключей. Для задания правил сортировки TreeMap ключи должны реализовывать Comparable интерфейс. В ином случае должен быть Comparator, ориентированный на ключи (тот, который задается в конструктор TreeMap), TreeSet — реализован с объектом TreeMap внутри, в котором, собственно, и происходит вся магия.
Подробнее про сортировку в TreeMap с помощью красно-черных деревьев можно почитать в статье об особенностях TreeMap.
- 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).
- 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).
Операция | ArrayList | LinkedList |
---|---|---|
Взятие по индексу get(index) | O(1) | В середине O(n/4) |
Добавить новый элемент add(obj) | O(1) Если нужно скопировать массив то — O(n) |
O(1) |
Удалить элемент remove(int index) | Из начала — O(n) Из середины — O(n/2) Из конца — O(1) |
В середине — O(n/4) В конце или в начале — O(n) |
Добавить элемент add(int index, Object obj) | В начало — O(n) В середину — O(n/2) В конец — O(1) |
В середине — O(n/4) В конце или в начале — O(n) |
Заменить элемент set(index, obj) | O(1) | В середине — O(n/4) В конце или в начале — O(n) |
- лучший выбор, если наиболее частая операция — поиск элемента, перезапись элемента;
- худший выбор, если операция — вставка и удаление в начале-середине, потому что будут проходить операции сдвига элементов справа.
- лучший выбор, если нашей частой операцией является вставка и удаление в начале-середине;
- худший выбор, если наиболее частая операция — поиск.
9. Как хранятся элементы в HashMap?
Коллекция HashMap содержит в себе внутренний массив Node [] table, ячейки которого еще называют бакетами (корзинами). Node содержат в себе:- key — ссылку на ключ,
- value — ссылку на значение,
- hash — значение hash,
- next — ссылку на следующий Node.
- Ключ проверяется на равенство null. Если он null, то key будет сохранен в ячейке table[0], потому что хэш-код для null всегда равен 0.
- Если ключ не null, то у объекта key вызывается метод hashcode(), который выдаст его хэш-код. Этот хэш-код используется для определения ячейки массива, где будет храниться объект Node.
- Далее данный hashcode помещается в внутренний метод hash(), который высчитывает hashcode, но уже в пределах размера массива table[].
- Дальше, в зависимости от значения hash, Node помещается в конкретную ячейку в массиве table[].
- Если же ячейка table[], используемая для сохранения текущего элемента Node не пуста, а уже имеет какой-то элемент, то происходит перебор элементов Node по значению next, пока не будет достигнут последний элемент. То есть, тот, у которого поле next равно null.
Во время данного перебора сравниваются ключ охраняемого объекта Node с ключами перебираемых:
- если будет найдено соответствие, то перебор закончится, и новый Node перезапишет Node, в котором найдено соответствие (перезапишется только его поле value);
- если соответствия ключей не найдены, то новый Node станет последним в этом списке, а предыдущий будет иметь ссылку next на него.
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.