Как устроена внутренняя структура LinkedHashMap? Что является элементом двусвязного списка?

Внутренняя структура LinkedHashMap в Java сочетает в себе хеш-таблицу и двусвязный список для сохранения порядка вставки элементов.

• Основой является массив бакетов (хеш-таблица), где каждый бакет содержит цепочку элементов с одинаковым хешем.
• Каждый элемент (Entry или Node) содержит ключ, значение, ссылку на следующий элемент в цепочке бакета (для разрешения коллизий), а также две дополнительные ссылки — на предыдущий и следующий элементы в порядке вставки.

Таким образом, элементом двусвязного списка является объект Entry, который хранит ссылки before и after, указывающие на соседние элементы в порядке вставки. Это позволяет LinkedHashMap поддерживать итерацию в порядке добавления элементов, одновременно обеспечивая быстрый доступ по ключу через хеш-таблицу.

Пример упрощённой структуры элемента:

class Entry<K,V> {
    final K key;
    V value;
    Entry<K,V> next;      // для цепочки в бакете
    Entry<K,V> before;    // предыдущий в порядке вставки
    Entry<K,V> after;     // следующий в порядке вставки
}