Java for Beginner

LinkedHashMap

LinkedHashMap — это класс из пакета java.util, который является расширением HashMap и сохраняет порядок вставки или порядок доступа к элементам. Это достигается за счет использования связанного списка, который поддерживает порядок элементов.

Основные характеристики LinkedHashMap

Порядок элементов: LinkedHashMap поддерживает порядок элементов, либо порядок вставки, либо порядок последнего доступа, в зависимости от конфигурации.
Производительность: Поиск, вставка и удаление элементов имеют сложность O(1), аналогично HashMap.
Связанный список: Внутренне LinkedHashMap использует связанный список для поддержания порядка элементов.

Структура LinkedHashMap

Бакеты (Buckets):

LinkedHashMap использует массив бакетов, аналогично HashMap. Каждый бакет представлен связным списком элементов, у которых произошла коллизия по хеш-коду.

Связанный список:

В дополнение к бакетам, LinkedHashMap использует связанный список, который соединяет все элементы в порядке их вставки или доступа. Каждый элемент содержит ссылки на предыдущий и следующий элемент, что позволяет поддерживать порядок.

Два порядка:

Порядок вставки (Insertion Order): Элементы хранятся в порядке их добавления в карту.
Порядок доступа (Access Order): Элементы перемещаются в конец списка при их доступе, что полезно для реализации LRU-кэшей (Least Recently Used).

Создание и использование LinkedHashMap

import java.util.LinkedHashMap;
import java.util.Map;

public class LinkedHashMapExample {
    public static void main(String[] args) {
        // Создание LinkedHashMap с порядком вставки
        LinkedHashMap<String, Integer> insertionOrderMap = new LinkedHashMap<>();
        
        // Добавление элементов
        insertionOrderMap.put("Apple", 50);
        insertionOrderMap.put("Banana", 30);
        insertionOrderMap.put("Orange", 20);

        // Перебор элементов в порядке вставки
        System.out.println("Insertion Order:");
        for (Map.Entry<String, Integer> entry : insertionOrderMap.entrySet()) {
            System.out.println(entry.getKey() + ": " + entry.getValue());
        }

        // Создание LinkedHashMap с порядком доступа
        LinkedHashMap<String, Integer> accessOrderMap = new LinkedHashMap<>(16, 0.75f, true);
        
        // Добавление элементов
        accessOrderMap.put("Apple", 50);
        accessOrderMap.put("Banana", 30);
        accessOrderMap.put("Orange", 20);

        // Доступ к элементу, что изменит его порядок
        accessOrderMap.get("Banana");

        // Перебор элементов в порядке доступа
        System.out.println("\nAccess Order:");
        for (Map.Entry<String, Integer> entry : accessOrderMap.entrySet()) {
            System.out.println(entry.getKey() + ": " + entry.getValue());
        }
    }
}

Внутреннее устройство LinkedHashMap

LinkedHashMap расширяет HashMap и добавляет дополнительную функциональность для поддержания порядка элементов.

Класс Entry:

Внутренний класс Entry наследуется от HashMap.Entry и добавляет ссылки на предыдущий и следующий элементы, что образует двусвязный список.

static class Entry<K, V> extends HashMap.Node<K, V> {
    Entry<K, V> before, after;

    Entry(int hash, K key, V value, HashMap.Node<K, V> next) {
        super(hash, key, value, next);
    }
}

Указатели на первый и последний элементы:

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

transient LinkedHashMap.Entry<K, V> head;
transient LinkedHashMap.Entry<K, V> tail;

#Java #Training #Medium #LinkedHashMap

168 viewsДен, 05:07

Java for Beginner

Методы для управления порядком:

LinkedHashMap переопределяет методы newNode и afterNodeAccess, чтобы управлять порядком элементов.

Node<K, V> newNode(int hash, K key, V value, Node<K, V> e) {
    LinkedHashMap.Entry<K, V> p = new LinkedHashMap.Entry<>(hash, key, value, e);
    linkNodeLast(p);
    return p;
}

void afterNodeAccess(Node<K, V> e) {
    LinkedHashMap.Entry<K, V> last;
    if (accessOrder && (last = tail) != e) {
        LinkedHashMap.Entry<K, V> p = (LinkedHashMap.Entry<K, V>) e, b = p.before, a = p.after;
        p.after = null;
        if (b == null)
            head = a;
        else
            b.after = a;
        if (a != null)
            a.before = b;
        else
            last = b;
        if (last == null)
            head = p;
        else {
            p.before = last;
            last.after = p;
        }
        tail = p;
        ++modCount;
    }
}

Порядок вставки (Insertion Order)

import java.util.LinkedHashMap;
import java.util.Map;

public class InsertionOrderExample {
    public static void main(String[] args) {
        // Создание LinkedHashMap с порядком вставки
        LinkedHashMap<String, Integer> map = new LinkedHashMap<>();

        // Добавление элементов
        map.put("Apple", 50);
        map.put("Banana", 30);
        map.put("Orange", 20);
        map.put("Grapes", 40);

        // Перебор элементов в порядке вставки
        System.out.println("Insertion Order:");
        for (Map.Entry<String, Integer> entry : map.entrySet()) {
            System.out.println(entry.getKey() + ": " + entry.getValue());
        }
    }
}

В этом примере элементы добавляются в порядке "Apple", "Banana", "Orange", "Grapes", и при переборе они выводятся в том же порядке.

Порядок доступа (Access Order)

import java.util.LinkedHashMap;
import java.util.Map;

public class AccessOrderExample {
    public static void main(String[] args) {
        // Создание LinkedHashMap с порядком доступа
        LinkedHashMap<String, Integer> map = new LinkedHashMap<>(16, 0.75f, true);

        // Добавление элементов
        map.put("Apple", 50);
        map.put("Banana", 30);
        map.put("Orange", 20);
        map.put("Grapes", 40);

        // Доступ к элементу, что изменит его порядок
        map.get("Banana");
        map.get("Apple");

        // Перебор элементов в порядке доступа
        System.out.println("Access Order:");
        for (Map.Entry<String, Integer> entry : map.entrySet()) {
            System.out.println(entry.getKey() + ": " + entry.getValue());
        }
    }
}

В этом примере элементы добавляются в порядке "Apple", "Banana", "Orange", "Grapes". После доступа к "Banana" и "Apple" они перемещаются в конец списка, и при переборе порядок будет "Orange", "Grapes", "Banana", "Apple".

Ссылки на полезные статьи (спасибо авторам за проделанную работу) :
https://habr.com/ru/articles/129037/
https://www.baeldung.com/java-linked-hashmap

#Java #Training #Medium #LinkedHashMap

Baeldung on Kotlin

A Guide to LinkedHashMap in Java | Baeldung

A quick and practical guide to LinkedHashMap in Java

166 viewsДен, 05:07

Java for Beginner

Внутреннее устройство LinkedHashMap

1. Связанный список для порядка элементов

LinkedHashMap расширяет HashMap, добавляя поддержку связанного списка для поддержания порядка элементов. Каждый элемент хранится в виде узла двусвязного списка, что позволяет поддерживать порядок вставки или порядок доступа.

static class Entry<K, V> extends HashMap.Node<K, V> {
    Entry<K, V> before, after;

    Entry(int hash, K key, V value, HashMap.Node<K, V> next) {
        super(hash, key, value, next);
    }
}

2. Поля для управления порядком

LinkedHashMap добавляет два новых поля для управления порядком элементов:

transient LinkedHashMap.Entry<K, V> head;
transient LinkedHashMap.Entry<K, V> tail;

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

3. Механизм управления порядком элементов

Для управления порядком элементов LinkedHashMap переопределяет методы newNode, afterNodeAccess и afterNodeInsertion:

newNode: Создает новый узел и добавляет его в конец связанного списка.

Node<K, V> newNode(int hash, K key, V value, Node<K, V> e) {
    LinkedHashMap.Entry<K, V> p = new LinkedHashMap.Entry<>(hash, key, value, e);
    linkNodeLast(p);
    return p;
}

private void linkNodeLast(LinkedHashMap.Entry<K, V> p) {
    LinkedHashMap.Entry<K, V> last = tail;
    tail = p;
    if (last == null)
        head = p;
    else {
        p.before = last;
        last.after = p;
    }
}

afterNodeAccess: Обновляет порядок элементов при доступе, если карта настроена на порядок доступа.

void afterNodeAccess(Node<K, V> e) {
    LinkedHashMap.Entry<K, V> last;
    if (accessOrder && (last = tail) != e) {
        LinkedHashMap.Entry<K, V> p = (LinkedHashMap.Entry<K, V>) e, b = p.before, a = p.after;
        p.after = null;
        if (b == null)
            head = a;
        else
            b.after = a;
        if (a != null)
            a.before = b;
        else
            last = b;
        if (last == null)
            head = p;
        else {
            p.before = last;
            last.after = p;
        }
        tail = p;
        ++modCount;
    }
}

afterNodeInsertion: Удаляет самый старый элемент, если карта настроена на удаление старейших элементов.

void afterNodeInsertion(boolean evict) {
    LinkedHashMap.Entry<K, V> first;
    if (evict && (first = head) != null && removeEldestEntry(first)) {
        K key = first.key;
        removeNode(hash(key), key, null, false, true);
    }
}

Основные методы LinkedHashMap

1. Конструкторы

LinkedHashMap предоставляет несколько конструкторов для создания карты с различными настройками:

public LinkedHashMap() {
    super();
}

public LinkedHashMap(int initialCapacity) {
    super(initialCapacity);
}

public LinkedHashMap(int initialCapacity, float loadFactor) {
    super(initialCapacity, loadFactor);
}

public LinkedHashMap(int initialCapacity, float loadFactor, boolean accessOrder) {
    super(initialCapacity, loadFactor);
    this.accessOrder = accessOrder;
}

2. Метод put
Метод put добавляет пару ключ-значение в карту. Если ключ уже существует, его значение обновляется.

public V put(K key, V value) {
    return super.put(key, value);
}

3. Метод get

Метод get возвращает значение, связанное с указанным ключом. Если ключ не найден, возвращается null. При этом порядок элементов обновляется, если карта настроена на порядок доступа.

public V get(Object key) {
    Node<K, V> e;
    if ((e = getNode(hash(key), key)) == null)
        return null;
    if (accessOrder)
        afterNodeAccess(e);
    return e.value;
}

4. Метод remove
Метод remove удаляет пару ключ-значение по указанному ключу и возвращает удаленное значение.

public V remove(Object key) {
    Node<K, V> e;
    return (e = removeNode(hash(key), key, null, false, true)) == null ? null : e.value;
}

5. Метод containsKey

Метод containsKey проверяет, содержит ли карта указанный ключ.

public boolean containsKey(Object key) {
    return getNode(hash(key), key) != null;
}

#Java #Training #Medium #LinkedHashMap

189 viewsДен, 14:28

Java for Beginner

6. Метод containsValue

Метод containsValue проверяет, содержит ли карта указанное значение.

public boolean containsValue(Object value) {
    for (Node<K, V> e = head; e != null; e = e.after) {
        if (value.equals(e.value))
            return true;
    }
    return false;
}

7. Метод clear

Метод clear очищает карту, удаляя все элементы.

public void clear() {
    super.clear();
    head = tail = null;
}

8. Метод entrySet

Метод entrySet возвращает набор всех пар ключ-значение в карте.

public Set<Map.Entry<K, V>> entrySet() {
    return new LinkedEntrySet();
}

#Java #Training #Medium #LinkedHashMap

168 viewsДен, 14:28

Java for Beginner

Раздел 6. Коллекции в Java

Глава 5. Map — отображения (словари)

Реализации: HashMap, LinkedHashMap, TreeMap и остальные

JCF предоставляет богатый набор реализаций Map, каждая оптимизирована под конкретные нужды.

Все они реализуют Map<K, V>, но различаются по:
Хранению: Хэш-таблица (HashMap), связный список + хэш (LinkedHashMap), красно-черное дерево (TreeMap).
Порядку: Нет (HashMap), вставки (LinkedHashMap), сортировка по ключам (TreeMap).
Производительности: O(1) для хэш, O(log n) для дерево.
Дополнительно: Специальные для enum, слабых ссылок и т.д.

1. HashMap<K, V>: Основная реализация

Описание: HashMap — сердце Map в Java, основанная на хэш-таблице. Хранит пары в массиве "бакетов" (buckets), где каждый бакет — список узлов (node) с ключом, значением и хэш-кодом.

Внутренняя структура:
Массив Node<K,V>[] table (initial capacity 16, load factor 0.75).
При put: Вычисляет hash = key.hashCode() ^ (hash >>> 16) для равномерности.
Индекс бакета: hash & (table.length - 1).
Коллизия: LinkedList или Tree (с Java 8, если > 8 узлов — дерево для O(log n)).
Ресайз: При >75% заполнения — удваивает размер, перехэширует все элементы.

Big O:
put/get/remove/containsKey: O(1) средний, O(n) worst (плохие хэши).
Итерация: O(capacity).

Особенности:
Порядок: Нет (iteration order не гарантирован).
Null: Один null-ключ, несколько null-значений.
Thread-safe: Нет (ConcurrentModificationException при параллельном доступе).
Initial capacity/load factor: new HashMap<>(16, 0.75f) для оптимизации.

Нюансы и ловушки:
hashCode/equals: Критичны! Плохой hashCode — деградация до O(n). Изменение ключа после put — потеря элемента.
Ресайз: O(n) время, но редко.
Java 8+: Tree nodes для коллизий (>8 узлов).
Remove: Если null-ключ — специальная обработка.
Итерация: entrySet(), keySet(), values() — O(capacity), не size().

Пример кода:

javaimport java.util.HashMap;
import java.util.Map;

public class Main {
    public static void main(String[] args) {
        Map<String, Integer> ages = new HashMap<>();
        ages.put("Алексей", 35);
        ages.put("Мария", 28);
        ages.put("Алексей", 36);  // Перезапись

        System.out.println(ages.get("Алексей"));  // 36
        ages.put(null, 0);  // Null-ключ
        System.out.println(ages.size());  // 3

        // Итерация
        for (Map.Entry<String, Integer> entry : ages.entrySet()) {
            System.out.println(entry.getKey() + ": " + entry.getValue());
        }
    }
}
Когда использовать: 99% случаев — быстрый поиск/кэш (userId -> User).

2. LinkedHashMap<K, V>: HashMap с порядком

Описание: Расширение HashMap с двусвязным списком для сохранения порядка вставки (insertion-order) или доступа (access-order для LRU-кэша).

Внутренняя структура: HashMap + Entry с prev/next ссылками. Два режима: INSERTION_ORDER (default) или ACCESS_ORDER (constructor flag).

Big O: O(1) для put/get/remove, как HashMap.

Особенности:
Порядок: Вставки (по умолчанию) или доступа (get/put обновляет позицию).
Null: Да.
Thread-safe: Нет.

Нюансы:
LRU кэш: new LinkedHashMap<>(16, 0.75f, true) — access-order, removeEldestEntry для eviction.
Итерация: В порядке вставки/доступа.
Ресайз: Как HashMap, но сохраняет порядок.

Пример:

javaimport java.util.LinkedHashMap;
import java.util.Map;

public class Main {
    public static void main(String[] args) {
        Map<String, Integer> map = new LinkedHashMap<>();
        map.put("A", 1);
        map.put("B", 2);
        map.put("A", 3);  // Обновляет, но порядок сохраняется

        for (String key : map.keySet()) {
            System.out.println(key);  // A, B — порядок вставки
        }

        // Access-order
        Map<String, Integer> lru = new LinkedHashMap<>(16, 0.75f, true);
        lru.put("A", 1);
        lru.get("A");  // "A" перемещается в конец
    }
}
Когда использовать: Кэш с порядком (LRU), когда нужен predictable iteration.

#Java #для_новичков #beginner #Map #HashMap #LinkedHashMap #TreeMap #Hashtable #IdentityHashMap #EnumMap #WeakHashMap

👍1

45 views08:58

Java for Beginner

3. TreeMap<K, V>: Отсортированная Map

Описание: Реализация SortedMap<K, V> на красно-черном дереве (red-black tree). Ключи всегда отсортированы.

Внутренняя структура: Дерево узлов с left/right/child ссылками, цветом для баланса.

Big O: O(log n) для put/get/remove/containsKey.

Особенности:
Порядок: Сортировка по ключам (Comparable или Comparator).
Null-ключ: Нет (NPE).
Null-значение: Да.
Thread-safe: Нет.

Нюансы:
Comparator: new TreeMap<>(comparator) для custom сортировки.
Дополнительные методы: firstKey(), lastKey(), headMap(K to), tailMap(K from), subMap.
Custom ключи: Comparable<K> или Comparator.
Баланс: Автоматический, O(log n) гарантировано.

Пример:

javaimport java.util.TreeMap;
import java.util.Map;

public class Main {
    public static void main(String[] args) {
        Map<Integer, String> map = new TreeMap<>();
        map.put(3, "Три");
        map.put(1, "Один");
        map.put(2, "Два");

        for (Integer key : map.keySet()) {
            System.out.println(key + ": " + map.get(key));  // 1: Один, 2: Два, 3: Три
        }

        System.out.println(map.firstKey());  // 1
    }
}
Когда использовать: Отсортированные ключи (диапазонные запросы, алфавитный словарь).

Остальные реализации: Hashtable, IdentityHashMap, EnumMap, WeakHashMap

Hashtable<K, V> (устаревшая)

Описание: Первая Map в Java (1.0), synchronized версия HashMap.
Особенности: Thread-safe (synchronized методы), нет null, порядок нет.
Big O: O(1).
Нюансы: Медленнее HashMap (locks на каждый метод), legacy — используйте ConcurrentHashMap.
Когда: Только legacy код.

IdentityHashMap<K, V>

Описание: HashMap с == вместо equals/hashCode (по ссылке).
Особенности: Для объектов, где важна идентичность (graph algorithms).
Big O: O(1).
Нюансы: Load factor 0.5, double hash для коллизий.
Когда: Редко, для identity сравнения.

EnumMap<K extends Enum<K>, V>

Описание: Оптимизированная Map для enum ключей (массив вместо хэш).
Особенности: O(1), порядок enum, нет null-ключа.
Нюансы: Ключи — enum, values any.
Когда: State machines, enum configs.

WeakHashMap<K, V>

Описание: HashMap с weak keys (GC может удалить entry, если ключ недостижим).
Особенности: Для кэшей, где память критична.
Big O: O(1).
Нюансы: Values strong, cleanup не мгновенный.
Когда: Canonicalizing mappings (interning).

Полезные советы для новичков

HashMap 95% случаев: Начните с неё.
LinkedHashMap для кэша: removeEldestEntry для LRU.
TreeMap для сортировки: Comparator для reverse.
Custom ключи: IDE генерирует equals/hashCode.
Initial capacity: new HashMap<>(expectedSize) для избежания ресайза.
Ошибки: NPE в TreeMap с null-ключом; ClassCast в TreeMap без Comparable.

#Java #для_новичков #beginner #Map #HashMap #LinkedHashMap #TreeMap #Hashtable #IdentityHashMap #EnumMap #WeakHashMap

👍2

45 views08:58

About

Blog

Apps

Platform