Структуры данных Java #неОпятьАСнова #javaJunior

Эта статья, как и все последующие и предыдущие – моя попытка структурировать полученные знания в процессе изучения Java. Здесь тезисно собрана вся основная информация по теме и те формулировки, которые показались мне наиболее удачными и понятными. Это мой конспект, если хотите.

Статья будет полезна тем, кто изучает или повторяет основы Java Core.
И тем, кто готовится к техническому интервью.

На источники, откуда черпалась информация, предоставлены ссылки в конце статьи.

Оглавление

• Основные понятия

• Массивы

• Класс Arrays

• Оценка сложности алгоритмов Big O

• Java Collections Framework (JCF). Коллекции

  • Иерархия коллекций JCF

• Интерфейс Iterable. Iterator. ListIterator

  • Fail-fast и Fail-safe итераторы

• Интерфейс Collection

• Интерфейс List

  • Класс ArrayList

  • Класс LinkedList

  • Классы Vector и Stack

• Интерфейс Queue

  • Класс PriorityQueue

  • Интерфейс Deque

    • Класс ArrayDeque

• Интерфейс Set

  • Класс HashSet

  • Класс LinkedHashSet

  • Интерфейс SortedSet

    • Интерфейс NavigableSet

      • Класс TreeSet

• Интерфейс Map

  • Интерфейс Map.Entry

  • Класс HashMap

  • Класс LinkedHashMap

  • Класс Hashtable

  • Класс WeakHashMap

  • Интерфейс SortedMap

    • Интерфейс NavigableMap

      • Класс TreeMap

• Класс Collections

• Red-Black Tree. Красно-черное дерево

• Потокобезопасные Concurrent коллекции

  • Блокирующие очереди пакета сoncurrent

• Сортировка коллекций

  • Интерфейс Comparable

  • Интерфейс Comparator

• Список ссылок на источники информации

Основные понятия

Структура данных (англ. Data Structure) — программная единица, позволяющая хранить и обрабатывать однотипные и/или логически связанные данные.
Для добавления, поиска, изменения и удаления данных структура данных предоставляет некоторый набор функций, составляющих её интерфейс.

Структура данных – это контейнер, который хранит данные в организованной форме.

Массив – самая простая и наиболее широко используемая структура.
Коллекции Java Сollections Framework являются производными от массивов.

Java Collections Framework — это набор связанных классов и интерфейсов, реализующих широко используемые структуры данных — Коллекции.
Он был спроектирован и разработан, в первую очередь, Джошуа Блохом.

Массивы

Массив – это структура данных, состоящая из упорядоченных ячеек, расположенных друг за другом в памяти, которые могут хранить в себе элементы только одного, заранее заданного типа.

Может хранить данные примитивных типов, строки (String) и ссылки на объекты класса.

Размер массива задается при его создании.
Тип данных и длину массива в дальнейшем изменить нельзя.

int[] numbers = new int[100];         // массив чисел на 100 ячеек

String[] strings = new String[10];    // массив строк на 10 ячеек

Person[] people = new Person[5];      // массив объектов класса Person   

Элементы массива доступны по индексу ячейки.
Значение по умолчанию для ячеек – null, 0 или false
Отсчет индексов ведется от 0

В памяти элементы массива размещаются в едином блоке.
Это сделано для более эффективного и быстрого доступа к ним.

String[] strings = new String[10];

strings[0] = "Hello";                 // присвоить значение первой ячейке
strings[1] = " world!";               // присвоить значение второй ячейке

System.out.println(strings[0] + strings[1]);    // получить значения по индексу

Быстрая инициализация массива
При быстрой инициализации размер массива не задается – размер будет определен автоматически в соответствии с количеством переданных в массив элементов.

int[] numbers = new int[]{1, 2, 3, 4, 5};

int[] numbers = {1, 2, 3, 4, 5};      // без ключевого слова new

String[] strings = {"Hello", " world!"};

Копирование массива System.arraycopy()
Этот статический метод класса System создан специально для копирования массива.
Копирует массив из указанного исходного массива, начиная с указанной позиции, в указанную позицию целевого массива.

System.arraycopy(array1, 0, array2, 0, array1.length);

Массивы бывают двух типов:

• Одномерные
  Массив хранит однотипные элементы

• Многомерные
  Массив хранит ссылки на другие массивы

int[][] numbers = new int[3][];                    // двумерный массив

String[][][] threeDimArray = new String[3][][];    // трехмерный массив

String[][] strings = new String[3][5];	           // таблица 3 столбца 5 строк

Инициализация двумерного массива
Обязательно задать размер только первого массива.
Каждый из внутренних массивов может быть своей длины – указывается при добавлении.

int[][] numbers = new int[3][];

numbers[0] = new int[2];
numbers[1] = new int[4];
numbers[2] = new int[3];

Быстрая инициализация двухмерного массива

int[][] numbers = {{1, 2}, {1, 2, 3}, {1, 2, 3, 4, 5}};

Добавить элемент в двухмерный массив
Сначала указывается индекс ячейки многомерного массива int[][] numbers, а затем индекс ячейки внутреннего массива

int[][] numbers = new int[3][3];

numbers[0][0] = 1;
numbers[1][0] = 2;
numbers[2][0] = 3;

Класс Arrays

Класс Arrays содержит различные статические методы для работы с Массивами (например, сортировка и поиск).

public final class Array extends Object

Сортировка массива Arrays.sort()
Отсортировать можно как весь массив, так его отдельную часть – диапазон индексов.

int[] numbers = {3, 2, 5, 1, 4};

Arrays.sort(numbers);          // [1, 2, 3, 4, 5]

Arrays.sort(numbers, 0, 4);    // [1, 2, 3, 5, 4]

Привести содержимое массива к строке Arrays.toString()
Для строкового представления многомерного массива создан отдельный метод Arrays.deepToString()

String str = Arrays.toString(strings);

String str = Arrays.deepToString(numbers);    // для многомерных массивов

Сравнить два массива между собой Arrays.equals()
Для сравнения содержимого массивов, а не ссылок, класс Arrays содержит переопределенный метод equals()
Для сравнения многомерных массивов используем метод Arrays.deepEquals()

Arrays.equals(numbers, numbers2);

Arrays.deepEquals(numbers, numbers2)          // для многомерных массивов

Заполнить массив одинаковыми значениями Arrays.fill()
Заполнить можно как весь массив, так и его часть – диапазон индексов.
Последний индекс не входит в диапазон.
Работает только с одномерными массивами.

Arrays.fill(numbers, 777);           // присвоить всем ячейкам значение 777

Arrays.fill(numbers, 3, 10, 777);    // заполнить ячейки с 3 по 9 индекс

Перевести Массив в List Arrays.asList()

List<Integer> listNumbers = Arrays.asList(arrayNumbers);

List<Integer> listNumbers = Arrays.asList(1, 2, 3);

Копирование массива Arrays.copyOf(), Arrays.copyOfRange()
Если элементы не поместились в новый массив – лишние значения игнорируются.
Если длина нового массива больше – ячейки заполняются значениями по умолчанию.
Под капотом используется метод System.arraycopy()

int[] numbersCopy = Arrays.copyOf(numbers, numbers.length);

int[] numbersCopy = Arrays.copyOf(numbers, 4);          // начать с индекса 4

int[] numbersCopy = Arrays.copyOfRange(numbers, 2, 7);  // индекс 7 НЕ входит

Бинарный поиск Arrays.binarySearch()
Для этого массив предварительного нужно отсортировать Arrays.sort()

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

Возвращает индекс искомого элемента в массиве либо отрицательное число – точку вставки (-(insertion point) - 1)
Точка вставки определяется как точка, в которую ключ будет вставлен в массив.

int[] numbers = {3, 2, 5, 1, 4};

Arrays.sort(numbers);                 // [1, 2, 3, 4, 5]

Arrays.binarySearch(numbers, 4);      // вернет индекс ячейки 3

Arrays.binarySearch(numbers, 6);      // вернет точку вставки -5 - 1 = -6

Оценка сложности алгоритмов Big O

Сложность алгоритмов оценивают по времени выполнения задачи или по используемой памяти.
Сложность зависит от размеров входных данных: массив из 100 элементов будет обработан быстрее, чем аналогичный из 1000.

Big O показывает верхнюю границу (худший вариант) того, как сложность алгоритма растёт с увеличением входных данных.

Сложность алгоритма может быть:

О(1) – константная сложность
Например: получить элемент массива по индексу

O(log n) – логарифмическая сложность
Сложность алгоритма растёт логарифмически с увеличением входных данных.
Например: на каждой итерации берется половина элементов – бинарный поиск

О(n) – линейная сложность
Сложность алгоритма растёт линейно с увеличением входных данных.
Например: цикл по всем элементам массива, рекурсивная функция

O(n²) – квадратичная сложность
Например: вложенный цикл

При оценке сложности константы не играют роли – отбрасываем константы и берем только наибольшую сложность.
Неважная сложность и отбрасывание констант:

O(n² + n²) = O(n²)

O(n² + n) = O(n²)

O(n + log n) = O(n)
Сложность log n меньше чем n

O(2 * 2ⁿ + 22 * n²) = O(2ⁿ)
Отбрасываем константы 2 и 22, оставляем наибольшую сложность: 2ⁿ гораздо больше n²

O(n² + m) = O(n² + m)
Выражение не может быть упрощено т.к. мы ничего не знаем про m

Java Collections Framework (JCF). Коллекции

Главным ограничением массива является его фиксированная длина.
Эту проблему решают Коллекции – набор интерфейсов и классов для работы с группой однотипных объектов – элементов коллекции.

Коллекция – это объект (контейнер), управляющий группой объектов (элементов).

В основе любой коллекции лежит использование того или иного интерфейса, который определяет ее базовый функционал.

• Примитивные типы нельзя хранить в коллекции

• Хранимые объекты называются элементами

• Коллекции хранят только ссылки на объекты

• Классы коллекций находятся в пакете java. util

Иерархия коллекций JCF

Два главных интерфейса коллекций – Collection и Map
От них наследуют все другие интерфейсы и классы Collection Framework.

Интерфейс Collection наследует интерфейс Iterable, который имеет один метод Iterator<T> iterator() , позволяет последовательно обходить элементы.

public interface Collection<E> extends Iterable<E>

Map не наследует интерфейс Collection, но входит в состав Java Collections Framework.
Map хранит данные в виде пары ключ – значение.

public interface Map<K,V>

Интерфейс Iterable. Iterator. ListIterator

Интерфейс Iterable – корневой интерфейс для всех классов коллекций Collection.

Метод этого интерфейса iterator() возвращает Итератор – объект, абстрагирующий за единым интерфейсом доступ к элементам коллекции.

List<String> list = new ArrayList();

Iterator<String> iterator = list.iterator();

Интерфейс Iterator – это поведенческий шаблон проектирования.
Дает возможность последовательно обходить элементы коллекций  при сокрытии внутренней структуры данных от пользователя.

Это свойство позволяет работать с любой структурой данных как с простой последовательностью или списком.

Итератор позволяет перемещаться по коллекции, получать или удалять элементы.
Одну и ту же коллекцию могут одновременно обходить различные итераторы.

Методы Iterator

Чтобы удалить элемент - его сначала нужно получить.

while (iterator.hasNext()) {
  
    Integer next = iterator.next();
  
    iterator.remove();
  
    iterator.forEachRemaining(System.out::println);
}

Интерфейс ListIterator
Расширяет Iterator, позволяет обойти List в обоих направлениях – двунаправленный обход и изменить элементы списка.

Доступен только для коллекций, которые реализуют List – получаем его с помощью метода интерфейса List listIterator()

List<String> list = Arrays.asList("A", "B", "C", "D", "E");

ListIterator<String> listIterator = list.listIterator();

Методы ListIterator

Изначально курсор итератора находится в начале списка и для того, чтобы сделать итерацию назад – нужно сделать хоть одну итерацию вперед.
Без этого вызов метода hasPrevious() будет возвращать false

while (listIterator.hasNext()) {
    String element = listIterator.next();
    listIterator.set(element + ",");
}

while (listIterator.hasPrevious()) {
    String element = listIterator.previous();
    System.out.print(element + " ");
}

Работа с итераторами может пригодится только в одном случае – удаление элементов. В остальных случаях используем цикл for-each.

Fail-fast и Fail-safe итераторы

Это характеристики разных реализаций интерфейса Iterator
Они определяют, как поведет себя итератор при изменении перебираемой последовательности элементов.

Fail-fast – быстрый итератор
Это итераторы коллекций пакета java.util
Если после его создания коллекция изменилась – он бросит исключение ConcurrentModificationException

Коллекции поддерживают внутренний счетчик под названием modCount.
Каждый раз, когда элемент добавляется или удаляется из коллекции, этот счетчик увеличивается. При итерации при каждом вызове next() текущее значение modCount сравнивается с начальным значением.

Если во время итерации по коллекции элемент удаляется с помощью метода итератора remove() – это полностью безопасно и не вызывает исключения.

Fail-safe – умный итератор
Это итераторы коллекций пакета java.util.concurrent
Итератор работает с копией данных – он не бросит исключение при изменении коллекции, но и не увидит обновленных данных.

Другим недостатком являются накладные расходы на создание копии коллекции, как в отношении времени, так и в отношении памяти.

Интерфейс Collection

Интерфейс Collection расширяет интерфейс Iterable – благодаря этому все классы наследники Collection могут получить Итератор.

public interface Collection<E> extends Iterable<E>

Этот интерфейс содержит основные методы, для работы с коллекциями.
Поэтому общие принципы работы с коллекциями будут общие для всех его классов наследников.

Основные методы Collection:

Интерфейс List

Интерфейс List расширяет интерфейс Collection.
Используется для создания простых списков.

• Сохраняет последовательность элементов

• Элементы могут быть доступны по индексу

• Может содержать повторяющиеся элементы

public interface List<E> extends Collection<E>

Помимо Iterator списки также могут вернуть ListIterator, который позволяет вставку и замену элементов, а также двунаправленный доступ.

Основные методы List:

Класс ArrayList

ArrayList поддерживает динамические массивы.
По мере добавления элементов в список, емкость внутреннего массива автоматически увеличивается.

• Использует под капотом обычный массив elementData

• Быстрый доступ к элементам по индексу за константное время O(1)

• Быстрая вставка и удаление элементов с конца за константное время O(1)

• Доступ к элементам по значению за линейное время O(n)

• Медленная вставка и удаление элементов из середины

• Хранит любые значения в том числе и null

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

• Автоматически увеличивается, но не уменьшается

public class ArrayList<E>
extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, Serializable

ArrayList создается с начальной емкостью capacity 10 ячеек
Переменная size хранит количество добавленных элементов и изначально равна 0. Это не емкость внутреннего массива – емкость массива недоступна.

Если добавить в ArrayList больше элементов, чем его capacity – неявно для пользователя произойдет вызов метода grow() и пересоздание внутреннего массива.

Алгоритм расширения внутреннего массива:

• Создается новый массив по формуле (capacity * 3) / 2 + 1

• Все элементы старого массива котируются в новый методом System.arraycopy()

• Новый массив присваивается внутренней переменной elementData
  Старый массив объявляется мусором – на него больше нет ссылки

Конструкторы ArrayList

ArrayList();

ArrayList(100);                             // задаем емкость capacity

ArrayList<>(collection);

list.add(" world!");			            // добавить в конец списка
list.add(0, "Hello");				        // добавить по индексу

list.size();				                // количество элементов

list.remove("Hello");				        // удалить по значению
list.remove(1);					            // удалить по индексу

Автоматически внутренний массив не уменьшается.
Чтобы обрезать емкость списка до реального количества элементов в нем – используем метод trimToSize(). Этот метод есть только у ArrayList и отсутсвует у List.

List<String> list = new ArrayList();

list.add("Hello");
list.add(" world!");
        
list.trimToSize();

Вставка элемента в середину, когда ArrayList полон:

• Создается новый массив размером по формуле (capacity * 3) / 2 + 1

• Все элементы из старого массива копируются в новый массив

• Новый массив сохраняется во внутренней переменной объекта ArrayList, старый массив объявляется мусором.

Класс LinkedList

LinkedList использует для хранения двусвязный список.
Поэтому Итератор поддерживает обход в обе стороны.

Помимо интерфейса List  реализует интерфейсы Dequeue и Queue.
Соединяет функциональность работы со списком и фукциональность очереди.

• Каждый элемент содержит ссылки на предыдущий и следующий элементы

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

• Быстрая вставка и удаление первого, последнего и элемента из середины списка за константное время O(1)

• Долгое время поиска позиции элемента за линейное время O(n)

• Операции поиска элемента по значению выполняются за линейное время O(n)

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

public class LinkedList<E>
extends AbstractSequentialList<E>
implements List<E>, Deque<E>, Cloneable, Serializable

Используется когда необходимо часто добавлять или удалять элементы, особенно в начало списка. Либо когда нужна вставка элемента в конец за гарантированное время.

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

list.add(" world!");			            // добавить в конец списка
list.add(0, "Hello");				        // добавить по индексу

list.size();				                // количество элементов в списке

list.remove("Hello");				        // удалить по значению
list.remove(1);					            // удалить по индексу

Для установки ссылок на предыдущий и следующий элементы LinkedList использует ноды – объекты своего вложенного класса Node.

Если предыдущий или следующий элемент отсутствует – значение ссылки null

private static class Node<E> {
    E item;
    Node<E> next;
    Node<E> prev;

    Node(Node<E> prev, E element, Node<E> next) {
        this.item = element;
        this.next = next;
        this.prev = prev;
    }
}

У LinkedList есть методы для работы с началом и концом списка, которых нет в ArrayList:

Выгода использования LinkedList в работе с серединой и началом списка.
Вставка и удаление в LinkedList устроены гораздо проще, чем в ArrayList – просто переопределятся ссылки на соседние элементы.

НО! Все элементы массива ArrayList находятся в одном блоке памяти, и операция по сдвигу элементов массива выполняются быстрым низкоуровневым методом System.arraycopy()
Обычно весь внутренний массив попадает в кэш процессора, поэтому элементы массива сдвигаются даже не в памяти, а в кэше.
Все это делает использование LinkedList не частым случаем.

Классы Vector и Stack

Класс Vector является реализацией динамического массива – похож на ArrayList.
Но в отличие от ArrayList, класс Vector синхронизирован, а размер его внутреннего массива увеличивается в 2 раза.

• Синхронизирован

• Deprecated. Устаревший класс
  На смену Vector пришел класс пакета java.util.concurrent СopyOnWriteArrayList

public class Vector<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, Serializable

Класс Stack является подклассом Vector.
Представляет собой стек объектов last-in-first-out (LIFO).

Расширяет класс Vector пятью методами, которые позволяют рассматривать вектор как стек. Предусмотрены обычные операции push() и pop(), а также метод просмотра верхнего элемент в стеке, метод проверки пуст ли стек, и метод поиска элемента в стеке и определения того, как далеко он находится сверху.

public class Stack<E> extends Vector<E>

Методы Stack:

Интерфейс Queue

Интерфейс Queue расширяет Collection.
Определяет поведение класса в качестве однонаправленной очереди.
Работает по принципу first-in-first-out (FIFO).

• Не может хранить значение null

public interface Queue<E> extends Collection<E>

Определяет основные методы для работы с однонаправленными очередями:

Класс PriorityQueue

Класс PriorityQueue – очередь с приоритетами.
По умолчанию размещает элементы согласно естественному порядку сортировки используя Comparable: элементу с наименьшим значением присваивается наибольший приоритет.

• Не хранит значение null

• Не хранит non-comparable объекты

• Не потокобезопасен

public class PriorityQueue<E> extends AbstractQueue<E>
implements Serializable

Если несколько элементов имеют одинаковый приоритет – связь определяется произвольно.

Можно указать порядок размещения, используя Comparator.

Интерфейс Deque

Интерфейс Deque расширяет интерфейс Queue – появился в Java 6.
Определяет поведение двунаправленной очереди.

Двунаправленная очередь может функционировать как стандартная очередь FIFO либо как стек LIFO.

public interface Deque<E> extends Queue<E>

Определяет основные методы для работы с двунаправленными очередями:

Класс ArrayDeque

Класс ArrayDeque представляет обобщенную двунаправленную очередь, наследуя функционал от класса AbstractCollection и реализуя интерфейс Deque.

• Не имеет ограничений по емкости.
  Растет по мере необходимости для поддержки использования.

• Не может хранить элемент null

• Не потокобезопасен

public class ArrayDeque<E> extends AbstractCollection<E>
implements Deque<E>, Cloneable, Serializable

Интерфейс Set

Set – это множество однотипных элементов.
Добавляет ограничение, которое запрещает повторяющиеся элементы.

• Хранит только уникальные элементы

• Уникальность определяется за счет контракта hashcode() equals()

• Нет индексов

public interface Set<E> extends Collection<E>

Можно делать три типа операций:
добавлять, удалять и проверять, есть ли во множестве элемент.
Методов get() и set() нет.

Класс HashSet

Класс HashSet реализует интерфейс Set.

• Основан на хэш таблице

• Элементы не упорядочены, порядок элементов может меняться

• Операции add(), remove(), contains() и size() за константное время O(1)

• Под капотом HashMap с заглушками значений

public class HashSet<E> extends AbstractSet<E>
implements Set<E>, Cloneable, Serializable

Название Hash происходит от понятия хэш-функции.
Хэш-функция сужает множество значений объекта до некоторого подмножества целых чисел.

Класс Object имеет метод hashCode(), который используется классом HashSet для эффективного размещения объектов, заносимых в коллекцию.
В классах объектов, заносимых в HashSet, этот метод должен быть переопределен.

Не имеет собственной реализации – под капотом использует HashMap.
В качестве значения value HashMap используется заглушка.
Значения HashSet – это ключи внутренней HashMap.

Класс LinkedHashSet

LinkedHashSet поддерживает связанный список элементов множества, в том порядке, в котором они были добавлены.
Это позволяет выполнять упорядоченную итерацию по множеству.

• Элементы в порядке добавления

• За счет этой особенности - работает дольше чем HashSet

public class LinkedHashSet<E> extends HashSet<E>
implements Set<E>, Cloneable, Serializable

Интерфейс SortedSet

Интерфейс SortedSet расширяет интерфейс Set
Описывает упорядоченное множество, отсортированное в возрастающем порядке или по порядку, заданному реализацией интерфейса Comparator.

• Обеспечивает отсортированный порядок элементов

• Элементы упорядочены с использованием их естественного порядка или с помощью компаратора

public interface SortedSet<E> extends Set<E>

Методы SortedSet:

Интерфейс NavigableSet

Интерфейс NavigableSet появился в Java 6.
Расширяет SortedSet и добавляет методы для более удобного поиска по коллекции.

public interface NavigableSet<E> extends SortedSet<E>

Методы NavigableSet:

Класс TreeSet

Класс TreeSet реализует интерфейс NavigableSet, который поддерживает элементы в отсортированном по возрастанию порядке.

• Элементы хранятся в отсортированном порядке по возрастанию

• Под капотом использует TreeMap

• Для хранения объектов использует бинарное красно-черное дерево

• Сортировка происходит благодаря тому, что все добавляемые элементы реализуют интерфейсы Comparator и Comparable

• Временная сложность базовых операций add(), remove(), contains() медленнее, чем в хэш-множествах, но быстрее, чем в списках: O(log(n))

public class TreeSet<E> extends AbstractSet<E>
implements NavigableSet<E>, Cloneable, Serializable

Если TreeSet пустой – можно положить единственное значение null
При этом все операции кроме size() и clear() перестанут работать.
В непустой TreeSet положить null уже нельзя из-за вызова compareTo()

Интерфейс Map

Интерфейс Map не имеет отношения к интерфейсу Collection, но тоже является частью Collections Framework.

Это объект, который сопоставляет ключи со значениями.
Каждый ключ может сопоставляться не более одного значения.

• Хранит данные парами: key – value

• Ключ всегда является уникальным
  Уникальность определяется за счет контракта hashcode() equals()

• Значения могут дублироваться

• Доступ к значениям осуществляется по ключу
  Ключ по значению получить нельзя

public interface Map<K,V>

По умолчанию под капотом Map массив на 16 buckets (корзин)
Внутри каждого бакета данные хранятся в LinkedList
Массив автоматически расширяется: 16 – 32 – 64

Худший результат работы Map – Коллизия:
Когда все элементы попадают в один bucket и их приходится перебирать итерацией по внутреннему LinkedList.

В таком случае происходит оптимизация хранения данных в этом бакете:
Если размер внутреннего LinkedList бакета становится равен 8 элементам и размер внутреннего массива Map равен 64 бакетам – происходит преобразование структуры данных внутри этого бакета в RB-дерево(red-black tree).

Для объектов-ключей важно переопределить методы equals() и hashCode()
Допускается добавление объектов без переопределения этих методов, но найти их в Map будет невозможно.

Основные методы Map:

Интерфейс Map.Entry

Вложенный nested интерфейс Map.
Это структура внутри Map, которая хранит все пары ключ-значение.
Возвращает множество Set пар, которое можно перебрать Итератором.

public static interface Map.Entry<K,V>

Объекты Map.Entry действительны только во время итерации.

Map<String, String> map = new HashMap<>();

Set set = map.entrySet();    // множество сопосталений ключ-значение

Класс HashMap

HashMap использует хэш - таблицу, в которой ключи отсортированы относительно значений их хэш-кодов.

Bucket – это элемент (ячейка) внутреннего массива HashMap.
В нем хранятся узлы Nodes.

• Хранит значения в произвольном порядке

• Структура хранения данных: bucket (корзина)

• Ключ и значение могут быть null

• Объекты с null ключами всегда записываются в нулевую ячейку массива.

public class HashMap<K,V> extends AbstractMap<K,V>
implements Map<K,V>, Cloneable, Serializable

Хеш-таблица – структура данных, реализующая интерфейс ассоциативного массива (сопоставления ключ–значение или entry), которая обеспечивает быструю вставку и поиск элементов.

Хеш-функция получает ключ, а на выходе возвращает целое число – хеш-код.
По полученному хэш-коду ключ помещается по определенному индексу хеш-таблицы.
За хеш-функцию отвечает метод hashCode()

По этой причине важно, чтобы хеш-функция вела себя последовательно и выводила один и тот же хэш-код для одинаковых входных данных. Поэтому в качестве ключей рекомендуется использовать только неизменяемые immutable типы, например класс String или Integer.

Хеш-отображение не гарантирует порядок расположения своих элементов.
Порядок, в котором элементы вводятся в хеш-отображение, не обязательно соответствует тому порядку, в котором они извлекаются итератором.

HashMap содержит следующие свойства:

• table – внутренний массив типа Entry

• size — размер, количество добавленных элементов

• capacity – емкость, количество бакетов в хэш-таблице

• loadFactor – коэффициент загрузки, по умолчанию равен 0.75
  Показатель насколько хэш-таблица может быть заполнена до того, как ее capacity будет автоматически увеличена

• threshold – количество элементов, при достижении которого, размер хэш-таблицы увеличится в два раза. Рассчитывается по формуле (capacity * loadFactor)

Алгоритм добавления элемента в HashMap:

• Высчитывается hashCode() ключа

• Определяется бакет (ячейка массива) в которую будет добавлен новый элемент. Номер определяется по остатку от деления хэшкода на кол-во ячеек.
  В более новых версиях Java с помощью бинарного сдвига.

• Если бакет пустой - элемент просто добавляется.

• Если бакет не пустой – элемент добавляется в LinkedList внутри бакета:

  • Ключ добавляемого элемента сравнивается с ключами в LinkedList по хэшкодам.

  • Если хэшкоды неравны – переход к следующему элементу

  • Если хэшкоды равны – ключи дополнительно сравниваются по equals() 

  • Если ключи равны по equals() – перезаписывается value найденного ключа

  • Если ключи не равны по equals() – переход к следующему элементу

• Если ключ не найден в LinkedList – элемент добавляется в конец списка

Класс LinkedHashMap

LinkedHashMap расширяет HashMap.
Поддерживает связанный список записей в том порядке, в котором они добавлены.
Это позволяет организовать итерацию по карте в порядке вставки.

• Элементы хранятся в порядке добавления

public class LinkedHashMap<K,V> extends HashMap<K,V>
implements Map<K,V>

Класс Hashtable

Hashtable – это синхронизированный аналог HashMap

• Синхронизирован

• Deprecated. На смену пришел ConcurrentHashMap

• Не хранит null

Класс WeakHashMap

Реализация интерфейса Map со слабыми ключами.
Запись в WeakHashMap будет автоматически удалена GK по ключу, ссылка на который вышла из области видимости приложения (ключ со слабой ссылкой).

• Записи автоматически удаляются GK

public class WeakHashMap<K,V> extends AbstractMap<K,V>
implements Map<K,V>

Интерфейс SortedMap

Интерфейс SortedМap расширяет интерфейс Мар

• Элементы размещаются в возрастающем порядке значений ключей

Методы SortedMap:

Интерфейс NavigableMap

Интерфейс NavigableMap был добавлен в Java 6.
Расширяет SortedМap и определяет поведение Map, поддерживающей извлечение элементов на основе ближайшего соответствия заданному ключу или ключам.

SortedMap расширена методами навигации, возвращающими ближайшие совпадения для заданных целей поиска:

• lowerEntry(K), floorEntry(K), ceilingEntry(K) и higherEntry(K) возвращают объекты Map.Entry, связанные с ключами соответственно меньше, меньше или равны, больше или равно и больше, чем данный ключ, возвращая null, если такого ключа нет.

• lowerKey(K), floorKey(K), ceilingKey(K) и higherKey(K) возвращают ключ соответственно меньше, меньше или равно, больше или равно и больше, чем данный ключ, возвращая null, если такого ключа нет.

• descendingMap() возвращает NavigableMap в обратном порядке

• subMap(K, boolean, K, boolean), headMap(K, boolean) и tailMap(K, boolean) отличаются от аналогичных методов SortedMap принятием дополнительных аргументов, описывающих, являются ли нижняя и верхняя границы инклюзивными по сравнению с эксклюзивными

• firstEntry(), pollFirstEntry(), lastEntry() и pollLastEntry() возвращают и/или удаляют наименьшие и наибольшие отображения, если таковые имеются, в противном случае возвращая null

• subMap(K, K), headMap(K) и tailMap(K) предназначены для возврата части NavigableMap

Класс TreeMap

Структура хранения данных красно-черное сбалансированное дерево.
По-умолчанию TreeMap сортируется по ключам с использованием принципа натуральной сортировки, но это поведение может быть настроено под конкретную задачу при помощи объекта класса Comparator.

• Красно-черное сбалансированное дерево

• Все элементы отсортированы в порядке возрастания ключа

• Порядок сортировки может быть задан Comparator и Comparable

public class TreeMap<K,V>
extends AbstractMap<K,V>
implements NavigableMap<K,V>, Cloneable, Serializable

Если TreeMap пустой – можно положить единственный ключ null
При этом все операции кроме size() и clear() перестанут работать
В непустой TreeMap положить null ключ уже нельзя из-за вызова compareTo()

Класс Collections

Класс Collections содержит различные статические методы для работы с Коллекциями.

Основные методы Collections:

Red-Black Tree

Красно-черное дерево – самобалансирующаяся версия двоичного поиска.
Обеспечивает логарифмическую сложность О(log(n)) операций добавления, удаления и поиска.

Верхний элемент – это корень дерева (чёрный цвет).
Все остальные элементы распределяются налево или направо в зависимости от значения хешей:

• Все левые потомки должны быть меньше корневого узла (или равны ему)

• Все правые потомки должны быть больше

• Оба потомка каждого красного узла — черные

• Все листья дерева (нижние элементы не содержащие данных) – черные

• Любой простой путь от узла-предка до листового узла-потомка содержит одинаковое число чёрных узлов.
  Простой путь – это тот в котором каждый узел входит ровно по одному разу.

Потокобезопасные Concurrent коллекции

Concurrent Collections – это набор коллекций, более эффективно работающих в многопоточной среде чем стандартные коллекции из пакета java.util

Вместо базового враппера (обертки) Collections.synchronizedCollection с блокированием доступа ко всей коллекции используются блокировки по сегментам данных или же оптимизируется работа для параллельного чтения данных по wait-free алгоритмам.

Пакет java.util.concurrent предоставляет реализации Конкурентных коллекций:

• ConcurrentHashMap – вместо HashMap

• ConcurrentSkipListMap – вместо TreeMap

• ConcurrentSkipListSet

• CopyOnWriteArrayList – вместо ArrayList

• CopyOnWriteArraySet

Блокирующие очереди пакета сoncurrent

Блокирующие очереди реализуют интерфейсы
BlockingQueue, BlockingDeque, TransferQueue

• ArrayBlockingQueue — очередь, реализующая классический кольцевой буфер;

• LinkedBlockingQueue — односторонняя очередь на связанных узлах;

• LinkedBlockingDeque — двунаправленная очередь на связанных узлах;

• SynchronousQueue — блокирующую очередь без емкости (операция добавления одного потока находится в ожидании соответствующей операции удаления в другом потоке);

• LinkedTransferQueue — реализация очереди на основе интерфейса TransferQueue;

• DelayQueue — неограниченная блокирующая очередь, реализующая интерфейс Delayed;

• PriorityBlockingQueue — реализация очереди на основе интерфейса PriorityQueue.

Сортировка коллекций

Чтобы сортировать объекты в коллекции – нужно прописать правила их сравнения.
Для этого в классе, чьи объекты будут сортированы, должен быть интерфейс Comparable или Comparator.

• Comparable – естественная сортировка класса

• Comparator – используется, когда в классе не реализован Comparable, либо реализован, но с неподходящей нам логикой сравнения объектов.

Три важных свойства сравнивающей функции
Если сравнивающая функция не удовлетворяет этим свойствам, алгоритм может выдать совершенно непредсказуемый результат.

1. Рефлексивность – сравнение элемента с самим собой всегда возвращает 0

2. Антисимметричность – сравнение A с B, и B с A должны дать разный знак.

3. Транзитивность – если сравнение A с B, и B с C выдает одинаковый знак, то и сравнение A с C должно выдать такой же знак.

Интерфейс Comparable

Интерфейс Comparable накладывает полный порядок на объекты каждого класса, который его реализует.
Этот порядок называется естественный порядок класса, а метод compareTo() класса называется его естественным методом сравнения.

public interface Comparable<T>

Списки и массивы объектов, реализующих этот интерфейс, могут быть автоматически отсортированы методами Collections.sort() и Arrays.sort().

Объекты, реализующие этот интерфейс, могут использоваться в качестве ключей в SortedMap или как элементы в SortedSet без необходимости указания Компаратора.

Чтобы задать свой способ сравнения объектов, нужно переопределить метод compareTo(), где прописать логику сравнения.

class Person implements Comparable<Person> {
	private String fullName;
	private Integer uuid;  
  
    @Override
    public int compareTo(Person person) {
        return uuid - person.uuid;
    }
}

Метод compareTo(Object o) сравнивает этот объект с указанным объектом. Возвращает отрицательное целое число, ноль или положительное целое число, если этот объект меньше, равен или больше указанного объекта.
В предопределенном методе вместо выражения можно использовать его:

    @Override
    public int compareTo(Person person) {     
        return uuid.compareTo(person.uuid);
    }

Рекомендуется чтобы (x.compareTo(y)==0) был равен (x.equals(y))

Можно сравнивать по нескольким полям класса.
Например, если fullName совпадают – тогда сравнить по uuid

    @Override
    public int compareTo(Person person) {
        int fullNameComparator = fullName.compareTo(person.fullName);
        int uuidComparator = uuid.compareTo(person.uuid);
      
        return (fullNameComparator != 0 ? fullNameComparator : uuidComparator);
    }

Интерфейс Comparator

Comparator используется, когда в классе не реализован, либо реализован с неподходящей логикой интерфейс Comparable, от чего нельзя сравнить объекты нужным образом.

@FunctionalInterface
public interface Comparator<T>

Можно создать отдельный класс компаратор, реализовав в нем Comparator.
Такой класс будет содержать нужную логику сравнения и его можно будет использовать в аргументах методов, которые требуют Компаратор.

Cравнение чисел делаем через Integer.compare
Или метод Comparator.comparingInt

public class PersonUuidComparator implements Comparator<Person> {

    @Override
    public int compare(Person p1, Person p2) {
        return Integer.compare(p1.uuid - p2.uuid);
    }
}

Можно создать несколько Компараторов для класса и использовать нужный.

public class PersonNameComparator implements Comparator<Person> {

    @Override
    public int compare(Person p1, Person p2) {
        return p1.name.compareTo(p2.uuid);
    }
}

Можно применять сразу несколько компараторов по принципу приоритета thenComparing()

var comparator = Comparator.comparing(Person::getName)
        .thenComparingInt(Person::getUuid);

Comparator<Person> personComparator = new PersonNameComparator()
        .thenComparing(new PersonUuidComparator());

Comparator – функциональный интерфейс, его можно задать лямбда выражением.
Статический метод Comparator.comparing принимает функцию ключа сортировки и возвращает компаратор для типа, содержащего ключ сортировки.

Comparator<Person> personUuidComparator = Comparator.comparing(Person::getUuid);

List<Person> people = new ArrayList<Person>();

people.sort((person1, person2) -> person1.uuid - person2.uuid());

people.sort((person1, person2) -> person1.uuid.compareTo(person2.uuid()));

Для сортировки в обратном порядке reversed()

Comparator<Person> uuidComparator = 
  (person1, person2) -> person1.getUuid().compareTo(person2.getUuid());

people.sort(uuidComparator.reversed());

Список ссылок на источники информации

• Массив

• Сортировки в гифках: 8 самых популярных алгоритмов

• Сложность алгоритмов. Big O. Основы.

• Что такое Java Collection Framework?

• 6 способов инициализировать коллекцию списков в Java!

• Очереди и класс ArrayDeque

• Подробный разбор класса HashMap

• Разрешение коллизий

• Балансировка красно-чёрных деревьев — Три случая

• Потокобезопасные concurrent коллекции

• Блокирующие очереди пакета concurrent

• Интерфейсы Comparable и Comparator в Java

• Java 8 Lambda : Comparator example

• Топ-50 Java Core вопросов и ответов на собеседовании.

• Вопросы и ответы на собеседовании по теме Java Collection Framework.