Combine a HashMap (`key -> Node`) for O(1) lookup with an insertion/recency doubly-linked list (with dummy `head`/`tail` sentinels) so promotion to MRU and eviction from LRU both run in O(1).