Что LinkedHashMap добавляет к обычной HashMap?

LinkedHashMap наследует HashMap и дополнительно связывает все записи двусвязным списком. Поэтому:

• доступ по ключу — те же O(1) в среднем;
• обход идёт в предсказуемом порядке — по умолчанию в порядке вставки (повторный put существующего ключа порядок не меняет);
• цена — две дополнительные ссылки на запись.

Режим порядка доступа. Конструктор LinkedHashMap(capacity, loadFactor, true) включает порядок по обращению: каждый get или put перемещает запись в конец. Если переопределить removeEldestEntry, получится кэш, вытесняющий давно не использованные записи (LRU), — частая задача на собеседовании.

Когда что выбирать: только быстрый доступ — HashMap; нужен порядок вставки (например, сохранить порядок полей JSON) — LinkedHashMap; нужна сортировка по ключу и диапазоны — TreeMap.

class LruCache<K, V> extends LinkedHashMap<K, V> {
    private final int capacity;
    LruCache(int capacity) {
        super(16, 0.75f, true);          // порядок по обращению
        this.capacity = capacity;
    }
    @Override
    protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
        return size() > capacity;
    }
}