Collections

Интерфейс у класса Collection. Для перебора элементов коллекции.

• hasNext - в итерируемом объекте вернет true если остались значения или false если кончились.

• next - возвращает следующий элемент коллекции. Если элемента нет - NoSuchElementException.

• remove - удалит элемент который был в последний раз получен методом next. UnsupportedOperationException если read-only коллекция. IllegalStateException - если next не был вызван.

Базовый интерфейс для всех коллекций. Коллекции/контейнеры - классы, хранящие набор элементов. Коллекции могут хранить любые ссылочные типы данных. Преимущества коллекций перед массивами - массивы имеют конечный размер (необходимость следить за ним) и индексную адресацию, ограничивающую добавление и удаление объектов.

Упорядоченный список. Объекты хранятся в порядке их добавления. Доступ к элементам осуществляется по индексу. Наследуется от Collection.

List<String> list = List.of(); // только для чтения
List<String> list = new ArrayList<>();

Реализован внутри в виде обычного массива. Поэтому при вставке элемента в середину, приходится сначала сдвигать на один все элементы после него, а уже затем в освободившееся место вставлять новый элемент. Минусы в скорости вставки/удаления элементов находящихся не в конце списка, так как при этой операции все элементы правее добавляемого/удаляемого сдвигаются. Размер по умолчанию - 10

• начальный размер (capacity) равен 10, при добавлении размер увеличивается в среднем в 1.5 раз и элементы копируются, старый удаляется gc

• при удалении элемента размер массива не уменьшается, capacity не меняется (есть метод trimToSize())

• если известно примерное количество элементов, указать capacity, чтобы не тратить ресурсы на расширение списка.

ArrayList<String> list = new ArrayList<>();
List<String> unmodifiableList = Collections.unmodifiableList(list); // только для чтения

Реализован в виде связного списка: набора отдельных элементов, каждый из которых хранит ссылку на следующий и предыдущий элементы. Чтобы вставить элемент в середину списка, достаточно поменять ссылки его будущих соседей. А вот чтобы получить элемент с номером 130, нужно пройтись последовательно по всем объектам от 0 до 130. Другими словами операции set и get очень медленные. Если необходимо вставлять (или удалять) в середину коллекции много элементов и гарантировать время этих операций, то лучше использовать LinkedList, в остальных случаях – ArrayList. LinkedList требует больше памяти для хранения такого же количества элементов, потому что кроме самого элемента хранятся еще указатели на соседей, тогда как в ArrayList элементы просто идут по порядку. LinkedList - вагоны поезда, сцепленные последовательно. Операции доступа по индексу производятся перебором с начала или конца (смотря что ближе) до нужного элемента. Как в LinkedList вставить новый элемент в середину списка: сначала проверяем наш capacity сдвигаем все что справа элементы и вставляем туда новый. если места не хватает выделяется память в 2 раза больше нынешнего capacity создается новый массив и все элементы копируются. чтобы оптимизировать память нужно задавать размер списка capacity изначально

• LinkedList не синхронизирован

• позволяет хранить любые объекты, в том числе null и повторяющиеся

LinkedList<String> list = new LinkedList<>();

Множество неповторяющихся уникальных объектов. В коллекции этого типа разрешено наличие только одной ссылки типа null. Наследуется от Collection.

Set set = new HashSet();

Реализован на основе хэш-таблицы. Набор объектов или хеш-множество, где каждый элемент имеет ключ - уникальный хеш-код. Название Hash происходит от понятия хэш-функция. Хэш-функция — это функция, сужающая множество значений объекта до некоторого подмножества целых чисел. Класс Object имеет метод hashCode(), который используется классом HashSet для эффективного размещения объектов, заносимых в коллекцию. В классах объектов, заносимых в HashSet, этот метод должен быть переопределен. HashSet гораздо быстрее чем TreeSet (константное время против логарифмического для большинства операций, таких как add, remove, contains). Предоставляет константное время для add(), remove(), contains() и size(). Производительность итерации по контейнеру зависит от емкости и «коэффициента загрузки»

• у элементов hashset должны быть переопределены equals и hashcode

• если переопределить equals без hashCode или оба метода неправильно, то есть вероятность, что два объекта попадут в одно пдмножество в HashSet

• если переопределен hashcode без equals возвращаемое значение equals является критерием равенства в неупорядоченных коллекциях, – два равных по содержимому объекта гарантированно не будут признаны равными ни в HashSet, ни при поиске по ключу в HashMap. А, следовательно, ошибку найти проще

• порядок элементов в контейнере может меняться

HashSet<String> set = new HashSet<>();
LinkedHashSet<String> set = new LinkedHashSet<>();

Реализован на основе бинарного дерева (красно-черное). Гарантирует упорядоченночть объектов. Время для базовых операций add, remove contains — log(n). Не предоставляет каких-либо параметров для настройки производительности. Предоставляет дополнительные методы для упорядоченного списка: first last headSet tailSet и т.д.

• гарантирует порядок элементов

• подход как в hashmap с разницей что ключом служит сам элемент.

TreeSet<String> set = new TreeSet<>();

Реализации этого интерфейса, помимо того что следят за уникальностью хранимых объектов, поддерживают их в порядке возрастания. Отношение порядка между объектами может быть определено, как с помощью метода compareTo. Наследуется от Set.

SortedSet<String> set = new TreeSet<>();

Коллекция, предназначенная для хранения элементов в порядке, нужном для их обработки. Наследуется от Collection. Очереди обычно, но не обязательно, упорядочивают элементы в FIFO (first-in-first-out, «первым вошел — первым вышел») порядке. Deque - двунаправленные очереди.

Queue<String> queue = new ArrayDeque<>();
ArrayDeque<String> array = new ArrayDeque<>();
PriorityQueue<String> queue = new PriorityQueue<>();

peekFirst() - извлекает первый элемент
pollFirst() - извлекает и удаляет первый элемент из очереди. Возвращает NULL, если очередь пуста
pop() - удаляет элемент из очереди
peek() - получает элемент из очереди

Функциональность ассоциативных массивов. Предназначен для созданий структур данных в виде словаря, где каждый элемент имеет определенный ключ и значение. Для поиска объекта по ключу их необходимо сравнивать. • не наследуется от Collection - это отдельная структура данных

• каждому ключу сопоставлено значение, а, следовательно, ключи должны быть уникальны.

Структура данных в виде дерева, где каждый элемент имеет уникальный ключ и некоторое значение. Полностью реализует SortedMap.

TreeMap<Integer, String> map = new TreeMap<>();

Хеш-таблица пары ключ-значение.

• в качестве ключа/значения объекты not null

1. Какие коллекции есть в Java?

   List Set Map ArrayList LinkedList HashMap

2. Расскажи про паттерн Iterator?

   Паттерн Iterator предоставляет способ последовательного доступа к элементам коллекции без раскрытия ее внутренней структуры. В этом паттерне используется объект-итератор, который реализует методы для перебора элементов (например, hasNext() и next()) и отделяет логику обхода от структуры данных, позволяя абстрагироваться от конкретного типа коллекции.

3. На чем основана реализация ArrayList и LinkedList?

   ArrayList - на массиве. LinkedList - на связном списке.

4. В чем разница между ArrayList и LinkedList?

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

   LinkedList реализован как двусвязный список, где каждый элемент содержит ссылку на следующий и предыдущий. Это позволяет эффективно вставлять и удалять элементы (O(1)), но доступ к элементам по индексу медленный (O(n)), так как нужно последовательно проходить список.

5. Где доступ к элементу быстрее в ArrayList или в LinkedList?

   Быстрее в ArrayList, так как он реализован на основе массива, и доступ к элементам осуществляется за O(1). В LinkedList доступ (кроме first и last) требует обхода списка и выполняется за O(n), так как это двусвязный список.

6. Как устроен Map?

   Это коллекция пар “ключ-значение”, где каждому ключу соответствует одно значение. Наиболее распространённая реализация — это HashMap. Она устроена как массив, где каждый элемент хранит список (цепочку) пар “ключ-значение”

7. Как устроен HashSet?

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

8. Как реализована TreeMap?

   Реализован на основе красно-черного дерева.

9. Разница между HashMap и Hashtable?

   Hashtable потокобезопасен, не допускает null, наследуется от Dictionary, синхронизирован.