Какое свойство LinkedHashMap отличает его от HashMap?
- Как сохранить порядок ключей в Map?
LinkedHashMap — HashMap плюс двусвязный список записей: обход в порядке вставки (по умолчанию) или в порядке доступа (accessOrder = true).
- HashMap порядок обхода не гарантирует
- Режим доступа + removeEldestEntry = LRU-кэш
- Сложность get/put та же, O(1)
А ещё Повторный put существующего ключа порядок вставки не меняет
Подробно
HashMap раскладывает записи по корзинам хеш-таблицы; обход идёт по корзинам, поэтому порядок зависит от хешей и меняется при расширении.
LinkedHashMap наследует HashMap и связывает все записи двусвязным списком. Режимы:
- порядок вставки (по умолчанию) — обход в порядке первого добавления ключа; повторный
putтого же ключа порядок не меняет; - порядок доступа (
new LinkedHashMap<>(16, 0.75f, true)) — каждыйget,put,getOrDefaultпереносит запись в конец.
Метод removeEldestEntry(Map.Entry eldest) вызывается после вставки; если вернуть true, самая старая запись удаляется — так получается LRU-кэш в несколько строк.
Цена: две дополнительные ссылки на запись и поддержка списка при изменениях. Зато обход пропорционален числу элементов, а не ёмкости таблицы.
Типичные применения: JSON с сохранённым порядком полей, кэш LRU, реестры, где важен порядок регистрации.
Что хотят услышать
- Двусвязный список поверх хеш-таблицы.
- Два режима порядка.
- LRU через accessOrder и removeEldestEntry.
Частые ошибки
- Думать, что повторный put перемещает ключ в конец в режиме вставки.
Проверьте себя
Один верный вариант. Подумайте, потом откройте ответ.
Показать варианты и ответ
- ✓Он сохраняет порядок вставки или порядок доступа
- ✗Он всегда сортирует ключи по возрастанию, как TreeMap
- ✗Он потокобезопасен без внешней синхронизации на запись
- ✗Он запрещает null как в ключах, так и в значениях
Что спросят дальше
- Как сделать простой LRU cache?
- Чем TreeMap отличается от LinkedHashMap?
Разбор темы
- LinkedHashMap и LRU-кэш
Порядок вставки против порядка доступа, связанный список поверх HashMap и реализация LRU через removeEldestEntry.
Связанные вопросы
- Как получить LRU-кэш на базе LinkedHashMap? Middle
- Какой ценой LinkedHashMap поддерживает предсказуемый порядок обхода по сравнению с HashMap? Middle
- Что произойдёт при обходе LinkedHashMap, созданного с accessOrder = true, если во время итерации вызвать get() по существующему ключу? Middle
- Нужна структура с быстрым поиском по ключу, которая при обходе отдаёт элементы в порядке их добавления. Что выбрать? Middle
Разбор собеседования с sotto
После собеседования sotto разбирает разговор: оценка, каждый вопрос — хорошо, частично или слабо, чего не хватило в ответе и над чем поработать к следующему разу. Первые 30 минут бесплатно.