Лист в HashMap двусвязный или односвязный

Структура списка в HashMap — двусвязный список

HashMap использует двусвязный (doubly-linked) список для разрешения коллизий. Это было изменено в Java 8 при добавлении механизма балансировки между цепочками и красно-чёрными деревьями.

Эволюция HashMap

Java 7 и ранее — просто связные списки

// До Java 8 — простой связный список для разрешения коллизий
public class HashMap<K, V> {
    static class Entry<K, V> {
        final K key;
        V value;
        Entry<K, V> next;  // Односвязный список!
        
        Entry(K key, V value, Entry<K, V> next) {
            this.key = key;
            this.value = value;
            this.next = next;
        }
    }
}

Java 8+ — двусвязный список и красно-чёрное дерево

// Начиная с Java 8
public class HashMap<K, V> {
    // Узел связного списка (двусвязный)
    static class Node<K, V> {
        final int hash;
        final K key;
        V value;
        Node<K, V> next;    // Следующий узел →
        Node<K, V> prev;    // Предыдущий узел ← (НОВОЕ в Java 8!)
        
        Node(int hash, K key, V value, Node<K, V> next) {
            this.hash = hash;
            this.key = key;
            this.value = value;
            this.next = next;
        }
    }
    
    // Расширение для связного списка с порядком вставки
    static class LinkedHashMap<K, V> extends HashMap<K, V> {
        transient LinkedHashMap.Entry<K, V> head;  // Головной элемент
        transient LinkedHashMap.Entry<K, V> tail;  // Хвостовой элемент
    }
}

Почему двусвязный список в Java 8+?

1. LinkedHashMap — отслеживание порядка вставки

// LinkedHashMap расширяет HashMap и отслеживает порядок вставки
Map<String, Integer> map = new LinkedHashMap<>();
map.put("A", 1);
map.put("B", 2);
map.put("C", 3);
map.put("A", 10);  // Обновление

// Итерация — в порядке вставки!
for (String key : map.keySet()) {
    System.out.println(key);  // A, B, C (A не перемещается при обновлении по умолчанию)
}

// LRU (Least Recently Used) cache используется двусвязный список
public class LRUCache<K, V> extends LinkedHashMap<K, V> {
    private final int capacity;
    
    public LRUCache(int capacity) {
        super(capacity, 0.75f, true);  // accessOrder=true → отслеживаем доступ
        this.capacity = capacity;
    }
    
    @Override
    protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
        return size() > capacity;  // Удаляем самый старый при overflow
    }
}

LRUCache<String, String> cache = new LRUCache<>(3);
cache.put("A", "value1");
cache.put("B", "value2");
cache.put("C", "value3");
cache.get("A");  // Переместили A в конец (самый свежий)
cache.put("D", "value4");  // B удалится как самый старый

2. Быстрое удаление из цепочки

Двусвязный список позволяет удалять элемент за O(1), зная его позицию:

// ❌ В односвязном списке нужно найти предыдущий узел
static class SingleLinkedNode<K, V> {
    Node next;
    
    void remove(Node node) {
        // Проблема: нужно найти предыдущий узел!
        // O(n) даже если знаешь node
        Node current = this;
        while (current != null && current.next != node) {
            current = current.next;  // Поиск...
        }
        if (current != null) {
            current.next = node.next;
        }
    }
}

// ✓ В двусвязном списке удаление O(1)
static class DoubleLinkedNode<K, V> {
    Node prev;  // Ссылка на предыдущий
    Node next;  // Ссылка на следующий
    
    void remove() {
        // Прямое удаление — не нужно искать предыдущий
        if (prev != null) {
            prev.next = next;
        }
        if (next != null) {
            next.prev = prev;
        }
    }
}

Практический пример — HashMap внутри

// Визуально, как HashMap с коллизиями хранит данные в Java 8+
public class HashMapInternals {
    public static void main(String[] args) {
        Map<String, Integer> map = new HashMap<>();
        
        // Добавляем элементы
        map.put("key1", 100);  // bucket[0] → Node(key1, 100) → next
        map.put("key2", 200);  // bucket[0] → Node(key2, 200) → prev/next
        map.put("key3", 300);  // bucket[0] → Node(key3, 300) → prev
        
        // Внутренняя структура (если все три попали в bucket[0]):
        //
        // bucket[0]: Node(key3) ↔ Node(key2) ↔ Node(key1)
        //           prev←—→next  prev←—→next  prev←—→next
        //
        // Двусвязная цепочка позволяет:
        // 1. Быстро удалять любой узел (O(1))
        // 2. Отслеживать порядок доступа (для LinkedHashMap)
        // 3. Итерировать в обе стороны
    }
}

Красно-чёрное дерево в больших цепочках

// Java 8 добавила оптимизацию: если цепочка вырастает слишком большая,
// она преобразуется в красно-чёрное дерево

public class HashMap<K, V> {
    // Порог для преобразования цепочки в дерево
    static final int TREEIFY_THRESHOLD = 8;  // Если 8 элементов в одной цепочке
    
    // Узел красно-чёрного дерева
    static final class TreeNode<K, V> extends LinkedHashMap.Entry<K, V> {
        TreeNode<K, V> parent;   // Родитель
        TreeNode<K, V> left;     // Левый потомок
        TreeNode<K, V> right;    // Правый потомок
        TreeNode<K, V> prev;     // Ссылка на предыдущий (двусвязная часть!)
        boolean red;             // Цвет узла (красный/чёрный)
        
        TreeNode(int hash, K key, V val, Node<K, V> next) {
            super(hash, key, val, next);
        }
    }
}

// Пример: если в одной цепочке много коллизий
Map<Integer, String> map = new HashMap<>();

// Все эти могут хешироваться в один bucket (плохое распределение)
for (int i = 0; i < 20; i++) {
    map.put(i * 16, "value" + i);  // 16 кратные могут коллизировать
}

// После добавления 8+ элементов в одну цепочку:
// Цепочка преобразуется в красно-чёрное дерево
// Поиск: O(n) → O(log n)

Сравнение: HashMap vs LinkedHashMap

// HashMap — внутри просто узлы с next/prev
Map<String, String> hashMap = new HashMap<>();
hashMap.put("B", "2");
hashMap.put("A", "1");
hashMap.put("C", "3");

// Итерация — порядок не гарантирован
for (String key : hashMap.keySet()) {
    System.out.println(key);  // Может быть: C, A, B или другой порядок
}

// LinkedHashMap — отслеживает порядок вставки
Map<String, String> linkedMap = new LinkedHashMap<>();
linkedMap.put("B", "2");
linkedMap.put("A", "1");
linkedMap.put("C", "3");

// Итерация — в порядке вставки!
for (String key : linkedMap.keySet()) {
    System.out.println(key);  // B, A, C — гарантированный порядок
}

// Внутри LinkedHashMap:
// HEAD ↔ Node(B) ↔ Node(A) ↔ Node(C) ↔ TAIL
//        (двусвязная цепь отслеживания порядка)

Почему это важно для интервью?

1. Производительность

// HashMap с большим количеством коллизий
Map<String, Integer> map = new HashMap<>();

// До Java 8: O(n) в худшем случае
// Java 8+: O(log n) если цепочка стала деревом
Integer value = map.get("someKey");

2. Сложность операций

3. Итерация в порядке

// Если нужен порядок вставки — используй LinkedHashMap
// Это более эффективно, чем Tree разные orders
Map<String, String> orderedMap = new LinkedHashMap<>();
orderedMap.put("first", "1");
orderedMap.put("second", "2");

// Гарантирован порядок вставки благодаря двусвязному списку

Вывод

HashMap в Java 8+ использует:

1. Двусвязный список (Node with prev/next) в каждой цепочке
2. Красно-чёрное дерево (TreeNode) при большом количестве коллизий (8+)
3. LinkedHashMap расширяет это для отслеживания порядка вставки

Двусвязный список позволил Java улучшить производительность LinkedHashMap и подготовить почву для балансирования деревьев при коллизиях.