Коллекции

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

Collections framework — это единая архитектура для хранения групп объектов и работы с ними. Он связывает базовые интерфейсы — Collection, List, Set, Map, Queue — с готовыми реализациями вроде ArrayList и HashMap, плюс переиспользуемые алгоритмы в утилитном классе Collections. Это даёт единый, согласованный API и позволяет менять реализацию, не переписывая вызывающий код.

List — упорядоченная позиционная последовательность: хранит порядок вставки, даёт доступ к элементам по индексу и допускает дубликаты. Set моделирует математическое множество: отвергает повторяющиеся элементы, так что каждое значение встречается не более одного раза, и обычно неупорядочен (HashSet) — хотя TreeSet хранит элементы отсортированными, а LinkedHashSet сохраняет порядок вставки. List берут для последовательностей, Set — для уникальности.

Collection (единственное число) — корневой интерфейс иерархии, который расширяют List, Set и Queue; он объявляет операции вроде add, remove и size. Collections (множественное число) — утилитный класс, содержащий только статические методы вроде sort, reverse, shuffle, synchronizedList и unmodifiableList. То есть одно — интерфейс, который реализуют, а другое — набор инструментов, который вызывают.

Comparable задаёт единственный естественный порядок типа: класс реализует compareTo(other) у себя, так что Collections.sort знает порядок по умолчанию. Comparator — отдельный объект, задающий один из многих внешних порядков через compare(a, b), позволяя сортировать тот же тип по разным ключам, не трогая его исходник. Comparable берут для единственного очевидного порядка, Comparator — для альтернативных или сторонних.

HashMap несинхронизирован, допускает один null-ключ и любое число null-значений и работает быстрее — стандартный выбор для однопоточного кода. Hashtable — устаревший класс, чьи методы synchronized, поэтому он блокирует всю таблицу на вызов, и он запрещает null-ключи и значения, бросая NullPointerException. Для конкурентных словарей сегодня предпочитают ConcurrentHashMap, который блокирует более мелкие сегменты, а не всю структуру.

HashMap держит массив бакетов, индексируемый по хешу ключа. Сталкивающиеся ключи делят бакет как связный список. capacity — размер массива бакетов, а loadFactor (по умолчанию 0.75) — порог заполнения: когда size > capacity * loadFactor, map удваивает capacity и перехеширует. С Java 8 бакет с более чем 8 записями (в достаточно большой таблице) превращает список в красно-чёрное дерево, снижая худший случай поиска с O(n) до O(log n).

HashSet хранит элементы через хеширование, давая в среднем O(1) на add, remove и contains, но без порядка — порядок обхода не определён. TreeSet опирается на красно-чёрное дерево, хранящее элементы отсортированными по естественному порядку Comparable или заданному Comparator, что стоит O(log n) на операцию, но даёт диапазонные запросы вроде first, ceiling и headSet. HashSet берут ради скорости, TreeSet — когда нужен отсортированный порядок.

И ArrayList, и Vector — динамические массивы с одинаковым O(1) доступом по индексу, но Vector — устаревший класс, чьи методы synchronized, так что каждый вызов берёт блокировку даже в однопоточном коде, теряя производительность. ArrayList несинхронизирован и сегодня является выбором по умолчанию. Vector к тому же удваивает ёмкость при росте, а ArrayList — наполовину. Для потокобезопасности предпочитают synchronizedList или CopyOnWriteArrayList.

ArrayList даёт get по индексу за O(1) и амортизированное O(1) на добавление в конец, но contains сканирует за O(n). LinkedList даёт O(1) только на концах; get по индексу и contains — O(n). HashMap и HashSet в среднем дают O(1) на все три операции, деградируя до O(log n) в бакете-дереве и до O(n) при вырожденном hashCode. TreeMap и TreeSet — O(log n) на любую операцию в обмен на отсортированный порядок.

Fail-fast итератор бросает ConcurrentModificationException, обнаружив структурное изменение коллекции в ходе обхода — он отслеживает счётчик модификаций и сверяет его на каждом шаге. ArrayList и HashMap ведут себя так. Fail-safe итератор вместо этого работает над копией или снимком, поэтому параллельные правки не мешают и он не бросает исключение — так делают CopyOnWriteArrayList и ConcurrentHashMap, ценой того, что поздние изменения не видны.

Поверхностная копия дублирует внешний контейнер, но разделяет те же ссылки на вложенные элементы, так что копия и оригинал указывают на одни внутренние объекты — изменение элемента у одного меняет его у другого. Глубокая копия рекурсивно клонирует весь граф объектов, давая копии собственные независимые внутренние объекты, так что изменения не протекают. clone и конструкторы копирования по умолчанию поверхностны; глубокая требует явного рекурсивного дублирования.

Держите два стека. Основной хранит значения; второй стек max хранит на каждом уровне максимум всего, что было добавлено к этому моменту. В push также кладите max(value, maxStack.peek()) на стек максимумов. В pop снимайте оба. getMax возвращает maxStack.peek(). Поскольку максимум пересчитан и сохранён на каждый элемент, он остаётся корректным после pop, а все три операции — O(1).

Держите TreeMap<value,count> плюс FIFO-очередь со значениями окна в порядке вставки. В add, если окно полно, извлеките самое старое из очереди и уменьшите (или удалите) его счётчик в map; затем увеличьте счётчик нового значения и поставьте его в очередь. getMin возвращает map.firstKey(). Каждая операция O(log w); монотонный deque даёт амортизированную O(1).