HashMap для доступа по ключу + двусвязный список по порядку использования. При доступе - переместить в голову; при переполнении - удалить хвост. Операции O(1). Альтернатива: LinkedHashMap в Java.