That can be done using a combination of dictionary (for quickly finding the cache entry in normal operation) and doubly-linked list (for ordering the entries for eviction), where you always rewire the last-accessed node to the front of the list. When the cache gets too large, it's easy to just remove the head of the list (and the corresponding dictionary key).