Design an LRU Cache

Requirements

• Fixed capacity; get(key) and put(key, value) must both run in O(1).
• When the cache is full and a new key is inserted, evict the least recently used entry.
• Both get and put count as "using" a key (move it to most-recently-used).

Key classes to identify before you look at the reference

A hash map alone gives O(1) lookup but no ordering. A linked list alone gives ordering but O(n) lookup. What single data structure combination gives you both — O(1) lookup and O(1) reordering?