Что такое LinkedHashMap?

LinkedHashMap — HashMap с сохранением порядка вставки. Каждый Node хранит ссылки before/after, формируя двусвязный список. Итерация — в порядке добавления (или access-order, если указать в конструкторе). Access-order LinkedHashMap — основа для LRU-кеша: переопределяешь removeEldestEntry() и получаешь автоматическое удаление старых записей. Чуть медленнее HashMap из-за поддержания списка, но сохранение порядка часто стоит того.