Коллекции #

Обязательно к прочтению

• ArrayList - https://habr.com/ru/articles/128269/
• LinkedList - https://habr.com/ru/articles/127864/
• HashMap - https://habr.com/ru/articles/128017/

1. Расскажите как выглядит иерархия коллекций #

Collection и Map - два интерфейса, которые находятся на вершине иерархии JCF. Интерфейс Collection расширяют интерфейсы:

• List
• Queue
• Set

2. Что такое ArrayList? #

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

3. ArrayList. Какая размерность массива по умолчанию? #

Capacity = 10

Можно ли задать начальную емкость/размер списка?

Да, через конструктор (List<String> list = new ArrayList<String>(15))

4. ArrayList. Что происходит под капотом при добавлении/удалении элемента в начало/середину/конец списка? #

Добавление в конец списка:

1. Проверяется достаточно ли места для добавления нового элемента. Если достаточно, то переходим к п. 2, если нет:
   • Создается новый массив размером в 1.5 раза больше
   • Копируются все элементы из старого массива
2. Новый элемент добавляется в конец

Добавление в начало/середину списка:

1. Проверяется, достаточно ли места для добавления нового элемента. Если достаточно, переходим к п. 2, если нет:
   • Создается новый массив размером в 1.5 раза больше
   • Копируются все элементы из старого массива
2. Все элементы, начиная с нужного индекса, сдвигаются на один вправо
3. Элемент с нужным индексом перезаписывается новым значением

Описанные операции копирования и сдвига элементов осуществляются функцией System.arraycopy(). Т.е. в случае добавления в конец списка System.arraycopy() будет вызвана 0 или 1 раз, в случае добавления в середину — 1 или 2 раза.

Прим. В старых версиях Java (как минимум в 6-й, которую использует автор статей из верхушки текущей страницы) при недостатке места для добавления нового элемента создавался массив размером 1.5*старый_размер + 1

5. ArrayList - сложность операций #

ArrayList — это реализация динамического массива в Java. Основные характеристики производительности операций зависят от внутреннего устройства структуры данных

ArrayList. Какая скорость добавления элемента в начало/середину/конец списка?

ArrayList. Какая скорость удаления элемента в начале/середине/конце списка?

ArrayList. Какая скорость доступа по индексу и значению?

Сложность по времени ArrayList.contains()

Время выполнения: O(n), где n — количество элементов. contains() выполняет линейный поиск, сравнивая элементы по порядку.

6. Что такое LinkedList? #

Классический двусвязный список, основанный на объектах с ссылками между ними. Реализует интерфейсы List и Deque. Данные хранятся в объектах типа Node

7. LinkedList. Что происходит под капотом при добавлении/удалении элемента в начало/середину/конец списка? #

При создании LinkedList-а, у нас создается псевдо элемент - Header в котором хранятся next и prev, которые пока указывают сами на себя. После добавления элемента, ссылки next и prev у каждого объекта будут указывать на предыдущий и следующий.

8. LinkedList - сложность операций #

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

LinkedList. Какая скорость добавления элемента в начало/середину/конец списка?

LinkedList. Какая скорость удаления элемента в начале/середине/конце списка?

LinkedList. Какая скорость доступа по индексу и значению

9. ArrayList vs LinkedList #

Где какой использовать?

• ArrayList следует использовать, когда в приоритете доступ по индексу, так как эти операции выполняются за константное время. Добавление в конец списка в среднем тоже выполняется за константное время. Кроме того в ArrayList нет дополнительных расходов на хранение связки между элементами. Минусы в скорости вставки/удаления элементов находящихся не в конце списка, так как при этой операции все элементы правее добавляемого/удаляемого сдвигаются.

• LinkedList удобен когда важнее быстродействие операций вставки/удаления, которые в LinkedList выполняются за константное время. Операции доступа по индексу производятся перебором с начала или конца (смотря что ближе) до нужного элемента. Дополнительные затраты на хранение связки между элементами.

Одним словом - если часто вставляете/удаляете - выбирайте в пользу LinkedList, в противном случае ArrayList

Преподаватель и сотрудник компании JetBrains Тагир Фаридович Валеев на своих лекциях утверждает, что НЕ стоит использовать LinkedList, т.к. он не оптимизирован. Все задачи можно решить с такой же скоростью или быстрее используя ArrayList/ArrayDeque

Какая скорость вставки в отсортированный массив ArrayList и LinkedList

• ArrayList:

  • Сложность: O(n), так как требуется сдвиг элементов, чтобы освободить место для нового элемента.
  • Подходит, если вставки происходят редко.

• LinkedList:

  • Сложность: O(n), так как требуется найти позицию для вставки (линейный поиск) и изменить ссылки.
  • Лучше подходит для частых операций вставки, особенно в начале / конце списка.

10. Что такое TreeMap? #

Класс в Java, который реализует интерфейс NavigableMap, который в свою очередь наследуется от SortedMap. Представляет собой ассоциативный массив, где ключи отсортированы в естественном порядке (или по заданному компаратору). Единственная коллекция, которая не использует equals() и hashCode(). Основана на красно-черных деревьях

11. TreeMap - сложность операций #

О(log n) (т.к каждый раз отметается половина)

12. Внутреннее устройство TreeMap #

Древовидная структура: под капотом TreeMap использует структуру данных, которая называется красно-чёрное дерево.

13. Что такое HashMap? #

Ассоциативный массив, хранит пары “ключ-значение”. Ключ-уникальный, значение-может повторяться. Каждая ячейка массива - бакет(корзина), хранящий в себе односвязный список узлов. Если у односвязного списка node больше 8 элементов (коллизии), он превращается в красно-чёрное дерево, обратно - если количество элементов в бакете уменьшилось до 6. Может содержать один ключ null и любое количество значений null. Не отсортирован и не упорядочен

14. Внутреннее устройство HashMap #

В HashMap бакет — это элемент массива, в котором хранятся записи (ключ-значение). Если у нескольких ключей совпадает хеш, их записи попадают в один бакет, где организуются в виде связного списка или сбалансированного дерева (в зависимости от Java версии).

Сколько изначально бакетов создается?

По умолчанию - 16

В каком случае количество бакетов увеличивается?

Если массив бакетов заполнен на 75 процентов - создается х2 от начального размера

Чтобы определить номер бакета есть формула. Какие в ней переменные?

bucketIndex = (hash & (capacity - 1));

1. hash — хэш-код ключа, который возвращает метод key.hashCode().
2. capacity — текущая ёмкость таблицы (всегда степень двойки, например, 16, 32).
3. bucketIndex — индекс бакета, в котором будет храниться элемент.

Операция побитового & (AND) используется вместо %, так как она быстрее и эффективнее для степеней двойки.

15. HashMap - сложность операций #

16. Процесс добавления объекта в HashMap #

1. Вычисляем хеш-код ключа и бакет, в который будет добавлен новый элемент
2. Если бакет пустой — просто добавляем элемент, если нет:
   • идем по ключам элементов связного списка (или TreeMap) и сравниваем с ключом добавляемого элемента по хеш-коду и equals()
   • если ключи равны — перезаписываем значение по этому ключу, если нет — переходим к следующему элементу
   • если не нашли ключ добавляемого элемента (равный и по хеш-коду, и по equals()) — добавляем этот элемент в конец связного списка (или в TreeMap)

17. Будет ли работать HashMap, если все добавляемые ключи будут иметь одинаковый hashCode()? #

Да, будет, но в этом случае HashMap вырождается в связный список и теряет свои преимущества

18. Ключи в HashMap #

Почему предпочтительно использовать в качестве ключа immutable объект?

Потому что, если изменить объект на котором основан ключ, то у него поменяется хеш-код найти элемент в HashMap-е не получится. Именно поэтому предпочтительно использовать immutable объекты (например String)

HashMap. Собственный объект в качестве ключа

Для своего класса в качестве ключа нужен hashCode/equals

Почему строка является популярным ключом в HashMap?

1. Иммутабельность (неизменяемость)
2. Хорошая реализация методов hashCode() и equals()

19. Что такое HashSet? #

HashSet — коллекция, не содержащая в себе дубликатов

20. Как HashSet связан с HashMap? #

HashSet использует HashMap для хранения элементов

21. Внутреннее устройство HashSet #

Сколько изначально бакетов создается?

По умолчанию создается - 16

В каком случае количество бакетов увеличивается

Если массив бакетов заполнен на 75 процентов - создается х2 от начального размера

22. HashSet - сложность операций #

О(1). Благодаря хеш-коду

23. Процесс добавления объекта в HashSet? #

HashSet использует HashMap под капотом: объекты являются ключами, а вместо значений используется константа-заглушка. Поэтому алгоритм добавления идентичен HashMap (элемент HashSet == ключ HashMap)

1. Вычисляем хэш-код объекта и бакет, в который будем добавлять объект
2. Если бакет пустой — объект добавляется в бакет, если нет:
   • идем по ключам элементов связного списка (или TreeMap) и сравниваем с добавляемым объектом по хеш-коду и equals()
   • если ключ элемента и объект равны — добавление игнорируется, если нет — переходим к следующему элементу
   • если совпадений не найдено — добавляем объект в конец связного списка (или в TreeMap)

24. Будет ли работать HashSet, если все добавляемые элементы будут иметь одинаковый hashCode()? #

Да, будет, но его производительность ухудшится. Если все элементы имеют одинаковый хеш-код, они все будут размещены в одном бакете, что приведет к увеличению времени поиска

25. Что такое Queue? #

Queue - это интерфейс в Java, который представляет собой коллекцию элементов, работающую по принципу “первый вошел — первый вышел” (FIFO — First In, First Out).

26. Queue - сложность операций #

О(1)

27. Назовите главные реализации Queue? #

1. LinkedList
2. ArrayDeque

28. Что такое Deque? #

Deque (Double-Ended Queue) — это интерфейс в Java, который представляет собой очередь с двумя концами. Это означает, что элементы могут быть добавлены или удалены как с начала, так и с конца очереди. Таким образом, Deque может работать как очередь (FIFO) и как стек (LIFO).

Что значит двунаправленный?

Двунаправленный (или двухсторонний) в контексте Deque (Double-Ended Queue) означает, что элементы можно добавлять и удалять с обеих сторон очереди

29. Назовите главные реализации Deque? #

1. LinkedList
2. ArrayDeque (Double ended queue)

30. Dequeue - сложность операций #

О(1)

31. Какая коллекция реализует дисциплину обслуживания LIFO? FIFO? #

• ArrayDeque

32. HashMap vs TreeMap #

33. Как с собой связаны Iterable и foreach? #

1. Iterable — это интерфейс в Java, который определяет метод iterator(). Он позволяет объекту предоставлять итератор для перебора его элементов.
2. foreach — синтаксический сахар, который компилируется в использование итератора.

List<String> list = List.of("a", "b", "c");

// Использование foreach
for (String item : list) {
    System.out.println(item);
}

// Как это работает под капотом:
Iterator<String> iterator = list.iterator();
while (iterator.hasNext()) {
    String item = iterator.next();
    System.out.println(item);
}

Вывод: foreach работает только с объектами, реализующими интерфейс Iterable, что обеспечивает возможность итерации.

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

Да, можно удалить элемент, но только с использованием итератора. Удаление через метод remove() коллекции при итерации приведёт к выбросу исключения ConcurrentModificationException.

Пример правильного удаления:

List<String> list = new ArrayList<>(List.of("a", "b", "c"));
Iterator<String> iterator = list.iterator();

while (iterator.hasNext()) {
    String item = iterator.next();
    if ("b".equals(item)) {
        iterator.remove(); // Удаление через итератор
    }
}

System.out.println(list); // [a, c]

Удаление с использованием самого списка вызовет ошибку:

for (String item : list) {
    if ("b".equals(item)) {
        list.remove(item); // Ошибка: ConcurrentModificationException
    }
}

Виды итераторов. Fail-Fast vs Fail-Safe

Fail-fast и fail-safe представляют две разные стратегии обработки ошибок, применяемые при работе с коллекциями в Java.

Итераторы fail-fast были добавлены в Java для обеспечения безопасности при работе с многопоточными коллекциями. Они основаны на модели “чистого” итератора, который не позволяет изменять список, пока он перебирается. Если во время перебора элементов коллекции происходит изменение структуры коллекции (например, добавление или удаление элемента), то итератор быстро завершает работу и выбрасывает исключение ConcurrentModificationException, чтобы предотвратить возможные ошибки в работе программы.

Итераторы fail-safe предоставляют альтернативный подход для работы с коллекциями. Они не используют блокировку при доступе к коллекции и не генерируют исключение ConcurrentModificationException при изменении коллекции во время итерации. Вместо этого они работают с копией коллекции, которая создается перед началом итерации, и гарантируют, что оригинальная коллекция не будет изменена никаким другим потоком во время итерации. Это обеспечивает более предсказуемое поведение итератора, но может приводить к неожиданному поведению в случае изменения коллекции другим потоком.

Таким образом, основная разница между fail-fast и fail-safe заключается в том, что fail-fast выбрасывает исключение при обнаружении изменений в коллекции, а fail-safe работает с копией коллекции, чтобы избежать конфликтов при изменении коллекции другим потоком. Решение о том, какой тип итератора использовать, зависит от требований проекта и особенностей работы с коллекцией. Если коллекция используется только в одном потоке или изменения происходят редко, то можно использовать итераторы fail-fast. Если же коллекция используется в многопоточной среде или изменения происходят часто, то следует использовать итераторы fail-safe.

34. Реализации интерфейса Map. Почему интерфейс Map выделен отдельно? #

Интерфейс Map выделен отдельно, так как он не является коллекцией в привычном смысле. Его предназначение — хранить пары “ключ-значение”, а не просто элементы.

35. Какую коллекцию использовать для уникальных отсортированных значений? #

TreeSet — хранит элементы в отсортированном порядке (по естественному порядку или по предоставленному компаратору) и гарантирует их уникальность.

36. HashTable - что это такое? #

HashTable — это реализация структуры данных хэш-таблицы в Java, которая позволяет хранить пары “ключ-значение”. Она принадлежит пакету java.util и была введена в ранних версиях Java.

1. Потокобезопасность: Методы синхронизированы, поэтому она подходит для многопоточных сред. Однако это снижает производительность по сравнению с несинхронизированными коллекциями, такими как HashMap.
2. Запрещены null ключи и значения: Попытка использовать null вызовет исключение NullPointerException.
3. Наследие: Считается устаревшим, так как современные альтернативы, такие как ConcurrentHashMap, более эффективны.

37. Arrays.asList() and List.of() #

38. Структуры данных. Какая сложность в дереве? #