Кратко о LinkedHashMap

LinkedHashMap = HashMap + двусвязный список. Хэш-таблица обеспечивает O(1) для операций, а список хранит порядок (вставки или доступа). Каждая запись имеет ссылки prev и next, что чуть увеличивает память, но даёт предсказуемый порядок итераций.