Design an LRU Cache with a Constant-Time Average

Lock-Striped Concurrent LRU Cache with a Running Average The classic constant-time LRU recipe is to keep two structures in perfect agreement: a hash map from key to a linked-list node, and a doubly linked list whose order expresses recency. The head of the list is the most recently used entry; the tail is the least recently used entry. The hash map gives expected constant-time lookup, while the linked list allows us to move a node to the head or unlink the tail in constant…