The LRU Cache Cache

Quickly understand

Move the original address interviewcake

Least-recently used (LRU) caching enables you to quickly determine which data has not been used for the longest time. Imagine clothes hangers that hang on one side. To find the least recently used clothes, look on the other side of the hanger. At the bottom, LRU caching is typically implemented by pairing double-linked lists with hash maps.

Advantages:

Ultra-fast access: The LRU cache stores items in the most recently used to least used order. This means that both are available at time O(1). Super fast update: It takes O(1) time to update the cache each time an item is accessed.Copy the code

disadvantages

Space is cumbersome. The LRU cache tracking n entries requires a linked list of length N, as well as a hash graph that holds n entries. Requires two O(n) space data structures (instead of one).

Why cache?

Suppose you manage a cooking establishment with many cake recipes. As with any web site, you want pages available as soon as possible.

When a user requests a recipe, you can open the corresponding file on disk, read the HTML, and send it over the network. This works, but it’s slow because it takes a while to access the disk.

Ideally, if many users ask for the same recipe, you want to read it from disk only once, leaving the page in memory so you can quickly send it out again if you need it. Good, you just added a cache.

Caching is just quick storage. It takes less time to read data from the cache than from other sources, such as hard disk.

But the available cache space is small. You can’t fit everything into the cache, and often you still need larger, slower storage.

If you can’t fit everything into the cache, how do you determine what the cache should store?

LRU deportation

This is an idea: if the cache can store space for n items, n elements have been accessed recently.

For the sake of specificity, suppose we have the following four recipes on disk:

The ICONS that describe the data are represented by different cake recipes: chocolate cake, vanilla cake, strawberry shortcake, pound cake. Let’s say our cache holds a maximum of three recipes (a little small, but it will make the example easier to understand).

Let’s walk through what caching looks like.

First, the user requests a chocolate cake recipe. We will read it from disk, save it to the cache, and then return it to the user.

Next, someone requested the vanilla cake recipe:

Note that the chocolate cake recipe is now at a lower level in the cache and is no longer recently used.

Here are the requirements for the strawberry cake recipe:

And one for chocolate:

We have saved these three recipes in cache so we can skip disk reading. We also restored it to its most recently used position and lowered the other positions.

Here are the pound cake recipes:

Since our cache only holds three recipes, we had to kick out one to make room. We kicked out the vanilla cake recipe because it was the least used of all the recipes in the cache. This is called the least-recently used (LRU) expulsion strategy.

There are a number of strategies we can use to choose the recipe to get rid of. We will focus on LRU because LRU is a common one in coding interviews.

An LRU cache can be used to find out what we should expel when the cache is full of an efficient cache data structure. The goal is to always put the least recently used items on O(1) time.

LRU cache implementation

The LRU cache is built by combining two data structures: a double-linked list and a hash graph.

We’ll create a list of links, using the most recent item at the top of the list and the most recent item at the end of the list:

This gives us O(1) access to the end of the list.

How do I access specific items in the cache (for example, chocolate cake)?

In general, it takes O(n) time to find items in a linked list because we need to traverse the entire list. But the whole point of caching is fast lookups. How do we speed things up?

We will add a hash map that will map to the linked list node:

So we can find an element in the cached list that is O(1) time, not O(n) time.

Access and expulsion

Here are the steps we perform each time we visit the project:

• Look for the entry in our hash map.

• If the item is in the hash table, it is already in our cache – this is called a “cache hit”

1. Hash table can be used to quickly find the corresponding linked list node. 2. Move the item's list node to the head of the list because it is recently used (and therefore should not be expelled soon).Copy the code

• If the item is not in the hash table, we have a “cache void”. We need to load this entry into the cache:

1. Is our cache full? If so, we need to make some room: find the least recently used cache item, which will be at the end of the list of links. You can eject the item from the cache by removing it from the linked list and from the hash diagram. 2. Create a new linked list node for the project. Insert it at the beginning of the list of links. 3. Add the item to our hash diagram and store the newly created linked list node as a value.Copy the code

Keeping all the Pointers straight when moving around a linked list node is tricky! Try it yourself! See if you can see why it’s important for our list to be bidirectional.

All of these steps are O(1), so taken together it takes O(1) to update the cache each time an element is accessed. Cool!