Map

Основные разделы

• HashMap
• TreeMap
• LinkedHashMap - это упорядоченная реализация хэш-таблицы. В порядке добавления.
• HashTable - HashMap с синхронизацией.
• ConcurrentHashMap
• ConcurrentSkipListMap - потокобезопасная и отсортированная версия TreeMap.

HashMap

Bucket(array) -> Односвязный list Node<K, V>(ключ - значение) или TreeNode

Node содержит: hashCode, key, value, next.

Ключ действует так же как и в HashSet.

Позволяет добавить (null, null), null будет первым ключом в коллекции.

HashMap bucket будет трансформирован из односвязного списка(Node) в дерево(TreeNode) при размере > 8. И произойдёт обратное при > 6.

default initial capacity = 16 - размер массива bucket.

load_factor = 0.75 - процент на который должен быть заполнен capacity(non-empty buckets) для умножения capacity на 2.

Сложность алгоритмов

1. Получение - от O(1)(при отсутствии коллизий), O(n) - до 8 элементов в бакете, O(log(n)) - больше 8.
2. Вставить - от O(1)(при отсутствии коллизий), O(n) - до 8 элементов в бакете, O(log(n)) - больше 8.
3. Удаление - от O(1)(при отсутствии коллизий), O(n) - до 8 элементов в бакете, O(log(n)) - больше 8.

Методы

1. put(K, V)
2. get(K)
3. remove(K)
4. keySet(): Set<K>
5. values: Collection<V>
6. entrySet(): Set<Map.Entry<K,V>>

TreeMap

Сложность алгоритмов

1. Получение - если перый эленент - O(1), если не первый O(log(n))
2. Вставить - O(log(n))
3. Удаление - O(log(n))

Плюсы

1. Высокая скорость поиска.
2. Сортировка данных.

Что реализует

На основе бинарного(каждый узел имеет только два потомка) красно-чёрного(сбалансированного) дерева. Гарантирует сложность log(n).

Бинарное дерево состоит из

1. Корень - верхний узел.
2. Узлы.
3. Листья - нижние узлы не имеющие потомков.

Красно-чёрное дерево состоит из

Красно-чёрное дерево - добавляет балансировку. Во время добавления до 2-х поворотов. При удалении до 3-х.

1. Узел либо красный, либо черный.
2. Корень черный.
3. Все листья чёрные.
4. Оба потомка красного узла - черные.
5. Каждый простой пусть от данного узла до любого листового узла, являющегося его потомком, содержит одинаковое число черных узлов.

Как создать

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

Условия для key

1. Immutable
2. Переопределить equals и hashcode

ConcurrentHashMap

ConcurrentHashMap - потокобезопасный HashMap. С эффективной блокировкой.

• Имеет locks каждого для bucket. При блокировке одного bucket, остальное не блокируются.
• Имеет схожий интерфейс HashMap.
• Операции чтения не требуют блокировок и выполняются параллельно.
• Операции записи зачастую также могут выполняться параллельно без блокировок.
• При создании указывается требуемый concurrencyLevel, определяемый по статистике чтения и записи.
• Value - объявленное как volatile

Hashtable при обращении блокировалась полностью.

HashTable и Collection.synchronized(HashMap) - Очень похожи. Но HashTable имеет функционал Enumerators(счетчики).