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

159 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

A Guide to LinkedHashMap in Java | Baeldung

A quick and practical guide to LinkedHashMap in Java

159 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

183 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

163 viewsДен, 14:28

About

Blog

Apps

Platform