Коллекции Flashcards
(17 cards)
Расскажи как выглядит иерархия коллекций
Iterable -> Collection -> Set, List, Queue | Map -> HashMap, TreeMap
Будет ли работать HashMap, если все добавляемые ключи будут иметь одинаковый hash code
Да, будет, но в этом случае HashMap вырождается в связный список и теряет свои преимущества
ArrayList vs LinkedList
ArrayList следует использовать, когда в приоритете доступ по индексу, так как эти операции выполняются за константное время. Добавление в конец списка в среднем тоже выполняется за константное время.
LinkedList удобен, когда важнее быстродействие операций вставки/удаления, которые в LinkedList выполняются за константное времени.
Одним словом - если часто вставляете/удаляете - выбирайте в пользу LinkedList, в противном случае ArrayList
Внутренне устройство HashMap
В HashMap бакет — это элемент массива, в котором хранятся записи (ключ-значение). Если у нескольких ключей совпадает хеш, их записи попадают в один бакет, где организуются в виде связного списка или сбалансированного дерева (в зависимости от Java версии). По умолчанию 16 бакетов. Количество бакетов увеличивается, если массив бакетов заполнен на 75 процентов - создается х2 от начального размера
Процесс добавления объекта в HashMap
- Вычисляем хеш-код ключа и бакет, в который будет добавлен новый элемент.
- Если бакет пустой — просто добавляем элемент, если нет:
- идем по ключам элементов связного списка (или TreeMap) и сравниваем с ключом добавляемого элемента по хеш-коду и equals()
- если ключи равны — перезаписываем значение по этому ключу, если нет — переходим к следующему элементу
- если не нашли ключ добавляемого элемента (равный и по хеш-коду, и по equals()) — добавляем этот элемент в конец связного списка (или в TreeMap)
Что такое HashMap
Ассоциативный массив, хранит пары “ключ-значение”. Ключ-уникальный, значение-может повторяться. Каждая ячейка массива - бакет (корзина), хранящий в себе односвязный список узлов. Если у односвязного списка node больше 8 элементов (коллизии), он превращается в красно-чёрное дерево, обратно - если количество элементов в бакете уменьшилось до 6. Может содержать один ключ null и любое количество значений null. Не отсортирован и не упорядочен.
HashMap - сложность операций
Добавление - O(1), Удаление - O(1), Поиск - O(1)
Реализация интерфейса Map. Почему интерфейс Map выделен отдельно?
Интерфейс Map выделен отдельно, так как он не является коллекцией в привычном смысле. Его предназначение — хранить пары “ключ-значение”, а не просто элементы.
Ключи в HashMap
Предпочтительно использовать в качестве ключа immutable объект. Потому что, если изменить объект, на котором основан ключ, то у него поменяется хеш-код и найти элемент в HashMap-е не получится. Именно поэтому предпочтительно использовать immutable объекты (например String).
ArrayList. Что происходит под капотом при добавлении/удалении элемента в начало/середину/конец списка?
Добавление в конец списка:
- Проверяется, достаточно ли места для добавления нового элемента. Если достаточно, то переходим к п. 2, если нет:
- Создается новый массив размером в 1.5 раза больше
- Копируются все элементы из старого массива
- Новый элемент добавляется в конец
Добавление в начало/середину списка:
- Проверяется, достаточно ли места для добавления нового элемента. Если достаточно, переходим к п. 2, если нет:
- Создается новый массив размером в 1.5 раза больше
- Копируются все элементы из старого массива
- Все элементы, начиная с нужного индекса, сдвигаются на один вправо
- Элемент с нужным индексом перезаписывается новым значением
Что такое ArrayList?
Это список, реализованный на основе динамически расширяемого массива. То есть под капотом буквально создается массив.
Что такое HashSet?
HashSet — коллекция, не содержащая в себе дубликатов.
LinkedList. Что происходит под капотом при добавлении/удалении элемента в начало/середину/конец списка?
При создании LinkedList-а, у нас создается псевдо-элемент Header, в котором хранятся next и prev, которые пока указывают сами на себя. После добавления элемента, ссылки next и prev у каждого объекта будут указывать на предыдущий и следующий.
Что такое TreeMap?
Класс в Java, который реализует интерфейс NavigableMap, который в свою очередь наследуется от SortedMap. Представляет собой ассоциативный массив, где ключи отсортированы в естественном порядке (или по заданному компаратору). Единственная коллекция, которая не использует equals() и hashCode(). Основана на красно-черных деревьях.
Что такое LinkedList?
Классический двусвязный список, основанный на объектах с ссылками между ними. Реализует интерфейсы List и Deque. Данные хранятся в объектах типа Node.
Какая коллекция реализует дисциплину обслуживания LIFO? FIFO?
ArrayDeque
Как связаны iterable и for each
for each можно использовать только на методах, реализующих Iterable.
