ℹ️ Как устроен под капотом LinkedHashMap?

LinkedHashMap — это реализация интерфейса Map, которая сохраняет порядок добавления элементов. В отличие от обычного HashMap, где элементы могут быть расположены случайным образом, LinkedHashMap поддерживает последовательность вставки или порядок доступа. Это достигается благодаря использованию двусвязного списка, который связывает все элементы карты.

🔹 Структура LinkedHashMap

Основой LinkedHashMap является та же хэш-таблица, что и в HashMap, но с дополнительной структурой двусвязного списка для сохранения порядка элементов:

▪️ Каждая запись (entry) в LinkedHashMap содержит ссылки на предыдущий и следующий элементы. Это позволяет поддерживать порядок добавления или порядок последнего доступа.
▪️ Сначала выполняется хэширование ключей для быстрой вставки и поиска, как в HashMap, а уже потом запись связывается в список.

🔹 Производительность

▪️ Вставка: Добавление новых элементов выполняется за O(1), поскольку элементы добавляются в конец двусвязного списка, а хэш-таблица используется для поиска свободной позиции.
▪️ Удаление: Удаление элемента требует корректировки ссылок в двусвязном списке, что увеличивает накладные расходы, но также выполняется за O(1).
▪️ Поиск: Операция поиска по ключу происходит с использованием хэш-таблицы и выполняется за O(1), как и в HashMap.
▪️ Множественные коллизии: в худшем случае все операции будут выполняться с O(n), если допустить множественные коллизии.

🔹 Использование памяти

Каждая запись LinkedHashMap содержит дополнительные ссылки на предыдущий и следующий элементы, что увеличивает потребление памяти по сравнению с HashMap. Однако это оправдано, если важен порядок элементов.

🔹 Преимущества и недостатки

▪️ Преимущества:

- Сохранение порядка вставки: LinkedHashMap гарантирует, что элементы будут извлекаться в том порядке, в котором они были добавлены.
- Порядок доступа: Можно настроить LinkedHashMap на удаление самых старых элементов, что полезно для кэшей, где используется политика LRU (Least Recently Used).
- Предсказуемость итераций: В отличие от HashMap, где порядок элементов может изменяться, LinkedHashMap всегда сохраняет стабильный порядок.

▪️ Недостатки:

- Более высокое потребление памяти: Дополнительные ссылки на предыдущие и следующие элементы увеличивают память на каждую запись.
- Скорость: LinkedHashMap немного медленнее HashMap из-за поддержания порядка элементов.