How to store several million caches and then track the 20 oldest caches

I had a question that I need to store several million file caches, and then I need to save the track in the 20 oldest caches, and as soon as the cache collection threshold increases, replace the 20 oldest with the next set of oldest caches.

I replied in order to save the hash map, again the question increases that if we want to quickly access any element in the hashmap, as I said to its map, so access to it did not take time, and the interviewer was not satisfied. So what should be an easy way for such scenarios.