Преимущества ArrayList: в возможности доступа к произвольному элементу по индексу за постоянное время (так как это массив), минимум накладных расходов при хранении такого списка, вставка в конец списка в среднем производится так же за постоянное время. В среднем потому, что массив имеет определенный начальный размер n (в коде это параметр capacity), по умолчанию n = 10, при записи n+1 элемента, будет создан новый массив размером (n * 3) / 2 + 1, в него будут помещены все элементы из старого массива + новый, добавляемый элемент. В итоге получаем, что при добавлении элемента при необходимости расширения массива, время добавления будет значительно больше, нежели при записи элемента в готовую пустую ячейку. Тем не менее, в среднем время вставки элемента в конец списка является постоянным. Удаление последнего элемента происходит за константное время. Недостатки ArrayList проявляются при вставке/удалении элемента в середине списка — это взывает перезапись всех элементов размещенных «правее» в списке на одну позицию влево, кроме того, при удалении элементов размер массива не уменьшается, до явного вызова метода trimToSize().

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

Чаще всего это действительно так, но не всегда. Внутри ArrayList находится массив. И когда пустые элементы в этом массиве заканчиваются, реализация ArrayList расширяет его - происходит создание нового массива, большего размера, куда происходит копирование старого, и уже в новый добавляется элемент. Таким образом, иногда вставка в ArrayList может занимать линейное время O(n)

Тот же вопрос применяется к emptyMap() и emptySet().

Оба метода возвращают пустой список, но Collections.emptyList() непреложный (immutable) список. Это означает, что вы не можете добавлять новые элементы к "пустому" списку. На фоне, каждый вызов метода Collections.emptyList() фактически не создает новый экземпляр пустого списка. Вместо этого, оно будет использовать снова уже существующий пустой экземпляр. Если Вы знакомы с синглтоном как с паттерном проектирования, Вы должны понять что имеется в виду. Это должно Вам дать большую производительность, если вызывается часто.

16. Но при создании HashMap в конструкторе можно задать другое значение (поле capacity)

Если вы возьмете хеш-функцию, которая постоянно будет возвращать одно и то же значение, то HashMap превратится в связный список, с отвратной производительностью. Затем даже, если вы будете использовать хеш-функцию с равномерным распределением, в предельном случае гарантироваться будет только временная сложность lg N. Так что, ответ на вопрос — нет, не гарантируется.

Здесь все довольно просто, достаточно вспомнить сигнатуру метода: int hashCode(). То есть число значений равно диапазону типа int — 2^32

List:

• ArrayList
• LinkedList
• Vector
• Stack

Set:

• HashSet
• TreeSet
• SortedSet

Map:

• HashMap
• TreeMap
• SortedMap
• Hashtable

• Мы можем использовать Iterator для обхода коллекций Set и List, тогда как ListIterator можно использовать только со списками.
• Итератор может перемещаться только в прямом направлении, тогда как ListIterator может использоваться для перемещения в обоих направлениях.
• ListIterator наследуется от интерфейса Iterator и поставляется с дополнительными функциями, такими как добавление элемента, замена элемента, получение позиции индекса для предыдущего и следующего элементов.

Java предоставляет Comparable интерфейс, который должен быть реализован любым пользовательским классом, если мы хотим использовать методы сортировки Arrays или Collections. Сопоставимый интерфейс имеет метод CompareTo (T obj), который используется методами сортировки. Мы должны переопределить этот метод таким образом, чтобы он возвращал отрицательное целое число, ноль или положительное целое число, если объект «this» меньше, равен или больше объекта, переданного в качестве аргумента. Но в большинстве сценариев реальной жизни Мы хотим сортировать по разным параметрам. Например, как генеральный директор, я хотел бы сортировать сотрудников по зарплате, а HR хотел бы сортировать их по возрасту. Это ситуация, когда нам нужно использовать интерфейс Comparator потому что реализация метода Comparable.compareTo(Object o) может сортировать только по одному полю, и мы не можем выбрать поле, по которому хотим отсортировать интерфейс Object.Comparator. compare(Object o1, Object o2) должен быть реализован метод, который принимает два аргумента Object, он должен быть реализован таким образом, чтобы он возвращал отрицательное значение int, если первый аргумент меньше второго, и возвращает ноль, если они равны, и положительное значение int, если первое. аргумент больше, чем второй.

• Concurrent Collections — набор коллекций, более эффективно работающие в многопоточной среде нежели стандартные универсальные коллекции из java.util пакета. Вместо базового враппера Collections.synchronizedList с блокированием доступа ко всей коллекции используются блокировки по сегментам данных или же оптимизируется работа для параллельного чтения данных по wait-free алгоритмам.
• Queues — неблокирующие и блокирующие очереди с поддержкой многопоточности. Неблокирующие очереди заточены на скорость и работу без блокирования потоков. Блокирующие очереди используются, когда нужно «притормозить» потоки «Producer» или «Consumer», если не выполнены какие-либо условия, например, очередь пуста или перепонена, или же нет свободного «Consumer»'a.
• Synchronizers — вспомогательные утилиты для синхронизации потоков. Представляют собой мощное оружие в «параллельных» вычислениях.
• Executors — содержит в себе отличные фрейморки для создания пулов потоков, планирования работы асинхронных задач с получением результатов.
• Locks — представляет собой альтернативные и более гибкие механизмы синхронизации потоков по сравнению с базовыми synchronized, wait, notify, notifyAll.
• Atomics — классы с поддержкой атомарных операций над примитивами и ссылками.

Название говорит само за себя. Все операции по изменению коллекции (add, set, remove) приводят к созданию новой копии внутреннего массива. Тем самым гарантируется, что при проходе итератором по коллекции не кинется ConcurrentModificationException. Следует помнить, что при копировании массива копируются только референсы (ссылки) на объекты (shallow copy), т.ч. доступ к полям элементов не thread-safe. CopyOnWrite коллекции удобно использовать, когда write операции довольно редки, например при реализации механизма подписки listeners и прохода по ним.

После добавления элемента в HashMap у объекта, который выступает в качестве ключа, изменяют одно поле, которое участвует в вычислении хеш-кода. В результате при попытке найти данный элемент по исходному ключу, будет происходить обращение к правильной корзине, а вот equals (ведь equals и hashCode должны работать с одним и тем же набором полей) уже не найдет указанный ключ в списке элементов. Тем не менее, даже если equals реализован таким образом, что изменение данного поля объекта не влияет на результат, то после увеличения размера корзин и пересчета хеш-кодов элементов, указанный элемент, с измененным значением поля, с большой долей вероятности попадет совсем в другую корзину и тогда он уже совсем потеряется.

Можно использовать Collections.synchronizedCollection(Collection c) чтобы получить синхронизированную (потокобезопасную) коллекцию, подкрепленную указанной коллекцией.

Класс HashMap по функционалу очень похож на Hashtable. Главное отличие в том, что методы класса Hashtable синхронизированы, а HashMap - нет. Кроме этого класс HashMap в отличии от Hashtable разрешает использование null в качестве ключей и значений.

Наличие синхронизации в Hashtable уменьшает производительность кода, использующего данный класс. Поэтому классы JCF (Java Collections Framework, появившийся в Java 2), в том числе и HashMap, несинхронизированы. Если синхронизация все же нужна, можно использовать методы класса Collections:

• Collections.synchronizedMap(map)
• Collections.synchronizedList(list)
• Collections.synchronizedSet(set) Данные методы возвращают синхронизированный декоратор переданной коллекции. При этом все равно в случае итерирования по коллекции требуется ручная синхронизация.

• Карта имеет схожий с hashmap интерфейс взаимодействия
• Потокобезопасность
• Операции чтения не требуют блокировок и выполняются параллельно
• Операции записи зачастую также могут выполняться параллельно без блокировок
• Элементы карты имеют значение value, объявленное как volatile

HashMap имеет концепцию повторного хеширования, когда достигает своего верхнего предела. Это процесс создания новой области памяти и копирования туда существующих элементов. Допустим Поток A положил пару key-value в Map и повторное хеширование началось, в то же время поток Б начал манипулировать с областью памяти используя операцию put(положить). Во время повторного хеширования существует возможность для создания циклической зависимости где элемент находящийся в ссылочном листе [в любой области памяти] может указывать на любой предыдущий узел в ту же область памяти. Это приведет к бесконечному циклу так как код повторного хеширования содержит в себе while(TRUE) {//получаем следующий узел} который будет работать бесконечно.

public Object get(Object key) {
    Object k = maskNull(key);
    int hash = hash(k);
    int i = indexFor(hash, table.length);
    Entry e = table[i];

    
//While true is always a bad practice and cause infinite loops


    while (true) {
        if (e == null)
            return e;
        if (e.hash == hash && eq(k, e.key))
            return e.value;
        e = e.next;
    }
}

Всё очень просто, эти структуры не совместимы. Для создания и для операция всех реализаций Map используется пара ключ-значение

Хеш-код массива не зависит от хранимых в нем элементов, а присваивается при создании массива (метод вычисления хеш-кода массива не переопределен и вычисляется по стандартному Object.hashCode() на основании адреса массива). Так же у массивов не переопределен equals и выполняет сравнение указателей. Это приводит к тому, что обратиться к сохраненному с ключом-массивом элементу не получится при использовании другого массива такого же размера и с такими же элементами, доступ можно осуществить лишь в одном случае — при использовании той же самой ссылки на массив, что использовалась для сохранения элемента.

Красно-чёрное

Интерфейс итератора объявляет методы для итерации коллекции, но за ее реализацию отвечают классы реализации коллекции. Каждый класс коллекции, который возвращает итератор для обхода, имеет свой собственный вложенный класс реализации итератора. Это позволяет классам коллекции выбирать, является ли итератор отказоустойчивым или отказоустойчивым. Например, итератор ArrayList является отказоустойчивым, тогда как итератор CopyOnWriteArrayList является отказоустойчивым.