Почему для реализации LRU-кэша выбрана структура данных Map?

Map сохраняет порядок вставки и обеспечивает эффективный доступ по ключу, поэтому им удобно представить порядок использования LRU.

При обращении существующий ключ удаляют и вставляют снова, делая его самым свежим. При превышении capacity удаляют первый ключ итератора. Просто вызвать set для уже существующего ключа недостаточно для переноса в конец; ограничение размера проверяют явно.