LRU Cache

Fixed-capacity cache; get/put in O(1); evict the least-recently-used key.

Approach 1: Use doubly linked list to maintain an order, and HashMap to map keys to the nodes

Approach 2 (for Python): Use an OrderedDict which has move_to_last(last: bool) and popitem(last: bool) methods allowing update recency of item and remove oldest items. Internally this is same as Approach 1.

Approach 3: Use singly linked list to maintain an order and HashMap to map keys to previous node so that deletion can be done in \(O(1)\) time. Saves memory in comparision to Approach 1.

To be thread safe, use locks with above approaches or use approximate approaches:

1. Use sharding:

   Split cache into smaller buckets to reduce lock contention.

2. Approximated LRU used in Redis:

   Randomly sample a set of keys and remove the LRU among them.

3. Second chance algorithm used in OS and Database system:

   Keep items in a circular array, and keep a single bit flag which is set to 1 on hit. To evict, move through the list until item with flag 0 is found. While moving flip 1 bit to 0 bit.