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. V put(K key, V value)
2. V get(Object key)
3. V remove(Object key)
4. Set<K> keySet()
5. Collection<V> values()
6. Set<Map.Entry<K, V>> entrySet()
7. boolean containsKey(Object key) – возвращает значение true, если в карте имеется указанный ключ.
8. boolean containsValue(Object value) – Возвращает значение true, если в карте имеется указанное значение.

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(счетчики).

Пример изменения типа в Map

import java.util.*;
import java.util.stream.Collectors;

public class Main {
    public static void main(String[] args) {
        Map<String, String> stringMap = new HashMap<>();
        stringMap.put("1", "100");
        stringMap.put("2", "200");

        Map<Integer, Integer> intMap = stringMap.entrySet()
            .stream()
            .collect(Collectors.toMap(
                e -> Integer.parseInt(e.getKey()),
                e -> Integer.parseInt(e.getValue())
            ));

        System.out.println(intMap); // {1=100, 2=200}
    }
}