Какой ценой LinkedHashMap поддерживает предсказуемый порядок обхода по сравнению с HashMap?
Цена — две дополнительные ссылки на запись и поддержка списка при вставке и удалении. get и put остаются O(1); обход даже быстрее — по списку, а не по всем корзинам.
- Память — главная плата
- Обход пропорционален размеру, а не ёмкости
А ещё Для огромных карт разница в памяти заметна
Подробно
Внутри это та же хеш-таблица с теми же бакетами, поэтому get и put сохраняют константную сложность в среднем. Добавлен лишь двусвязный список, прошивающий все записи, — отсюда две дополнительные ссылки в каждой записи и необходимость поддерживать список при вставке и удалении. Интересно, что обход при этом может оказаться даже быстрее: HashMap при итерации вынужден проходить весь массив бакетов, включая пустые, а LinkedHashMap идёт строго по цепочке живых записей, что заметно на разреженной карте.
Что хотят услышать
- Память и стоимость изменений.
- Сохранение сложности.
Частые ошибки
- Думать, что порядок обеспечивается сортировкой.
- Считать, что за порядок платят сложностью поиска.
Проверьте себя
Один верный вариант. Подумайте, потом откройте ответ.
Показать варианты и ответ
- ✗Записи хранятся отсортированными по ключу, поэтому вставка стоит O(n)
- ✓Две лишние ссылки на запись: больше памяти, чуть дороже вставка
- ✗Поиск по ключу становится O(log n) вместо O(1) из-за обхода списка
- ✗Никакой цены нет: LinkedHashMap во всём не хуже HashMap
Что спросят дальше
- Почему обход LinkedHashMap может быть быстрее, чем у HashMap?
- Когда предсказуемый порядок обхода реально нужен?
Разбор темы
- LinkedHashMap и LRU-кэш
Порядок вставки против порядка доступа, связанный список поверх HashMap и реализация LRU через removeEldestEntry.
Связанные вопросы
Разбор собеседования с sotto
После собеседования sotto разбирает разговор: оценка, каждый вопрос — хорошо, частично или слабо, чего не хватило в ответе и над чем поработать к следующему разу. Первые 30 минут бесплатно.