В чем особенности LinkedHashMap?

LinkedHashMap сочетает в себе характеристики HashMap и LinkedList.

Особенности:

• Порядок хранения: В отличие от HashMap, LinkedHashMap сохраняет порядок вставки элементов (insertion order). Существует также возможность сохранения порядка доступа (access order) — порядок обращения к элементам.
• Производительность: Производительность основных операций (get, put, remove) близка к HashMap (в среднем O(1)), так как используется хэш-таблица. Дополнительные накладные расходы связаны с обслуживанием двусвязного списка.
• Внутренняя структура: Состоит из хэш-таблицы (аналогично HashMap) и двусвязного списка, соединяющего все элементы в порядке их добавления или последнего доступа. Каждый узел в хэш-таблице дополнительно хранит ссылки на предыдущий и следующий элементы в списке.
• Использование: Часто применяется, когда нужно сохранять порядок добавления элементов, например, для реализации кеша с вытеснением Least Recently Used (LRU).

Пример использования для LRU-кеша:

// Пример реализации LRU-кеша на LinkedHashMap
public class LRUCache<K, V> extends LinkedHashMap<K, V> {
    private final int cacheSize;

    public LRUCache(int cacheSize) {
        // Инициализация LinkedHashMap с accessOrder = true
        super(cacheSize, 0.75f, true); 
        this.cacheSize = cacheSize;
    }

    // Переопределение метода для удаления самого старого (наименее используемого) элемента при превышении размера
    @Override
    protected boolean removeEldestEntry(java.util.Map.Entry<K, V> eldest) {
        return size() > cacheSize;
    }
}