LRU

As explained in Advanced Algorithms and Data Structures

An LRU cache is a cache that evicts the entry that has been unused for the longest time when it reaches capacity.

An LRU cache stores recently accessed values and, at capacity, evicts the entry unused for the longest time. It suits systems that avoid recomputing results by reusing cached entries. section 7.0 section 7.4

The design combines a hash table with a doubly linked list. The table finds a key and points to its list node; the list keeps most-recently-used entries at the front and the least-recently-used entry at the tail. section 7.4.1 section 7.4.2

Core operations follow the same ordering invariant:

• On a cache hit, retrieve the node through the hash table and return its value. section 7.4.2
• When setting an existing key, update its node and move it to the list front. section 7.4.2
• When setting a new key at capacity, remove the tail node and its hash-table entry, then add the new node at the front. section 7.4 section 7.4.2

Adding and evicting an entry

Suppose “Acme” is absent from a full cache. Add its node at the list front, insert a hash-table pointer to that node, and remove the node formerly at the tail. The list now records Acme as most recently used. section 7.4.2

Figure 7.5 Structure of an LRU cache. You can see the tree data elements that are stored for the cache and need to be updated after every operation: (1) The hash table. (2) The head of a doubly-linked list. (3) A pointer to the last element in the list. Notice how each element in the hash table points to a node in the list where all the data is stored. To get from a list entry to the corresponding hash entry, we have to hash the name of the company stored in the node, which is the key for the table. For the sake of simplicity, collision resolution is not considered in this and the following figures.

Inspect the structure linking the hash table, list head, tail pointer, and shared list nodes. section 7.4.2

How Advanced Algorithms and Data Structures covers it

How deep it goes

Develops the hash-table and doubly-linked-list design through pseudocode, synchronized updates, and amortized constant-time analysis.

Examples

Uses company-name entries, an Acme cache miss, an EvilCorp update, and diagrams or pseudocode for insertion and eviction.

What it assumes

Assumes familiarity with lists, queues, hash tables, and linked-list operations while making their combined cache design explicit.

What you can do after

Build it from scratch with a capacity, hash table, doubly linked list, head, tail, insertion, lookup, update, and eviction operations.

How it connects

Connects caching with hash tables, linked lists, queues, caching strategies, concurrency, synchronization, and alternative MFU eviction.

liveBookmanning.com

Read Advanced Algorithms and Data Structures on liveBook Get the book at manning.com

Also explained in

• 

  liveBookmanning.com
  Designing Deep Learning Systems: A guide for software engineersThe least recently used algorithm evicts the item that has gone unused for the longest time when a cache reaches its capacity.

Compare how 2 books explain LRU →

Related concepts

• cachingconfigures · Caching is the practice of storing reusable data or computation results so later access can avoid repeating retrieval or computation.
• least frequently usedcontrasts with · Least frequently used is a cache-eviction policy that removes the entry with the lowest access frequency when capacity is exhausted.
• hash mapuses · A hash map is a key-value data structure that uses a hash function to locate entries and support efficient lookup, insertion, and removal by key.
• Redisuses · Redis is an open-source, in-memory data-structure store that provides network-accessible data operations and supports persistence.
• cache replacement policykind of · A cache replacement policy is a rule or algorithm for selecting which cached item to remove when capacity is insufficient or cached data must be discarded.

This explainer was generated by Manning's knowledge graph from the text of Advanced Algorithms and Data Structures. The section links point to the parts of the book it draws on.