In your travels as a software engineer, you're likely to come across instances where every possible data structure gets a chance to shine. One in particular doesn't get quite as much spotlight as the others, but can be just as useful (if not more so) in certain situations. That data structure in question is the LRU Cache.
What is an LRU Cache?
An LRU Cache, or Least Recently Used Cache, is a data structure that stores information in the order that it has most recently been added or accessed.
A popular analogy is a clothes rack in a closet: as clothes are worn and hung back up, they go on the right side of the rack. As time goes on, one can easily tell which clothes haven't been worn in a longer period of time by looking at the left side of the rack.
Why would I want to use one?
The main advantage of using an LRU Cache versus other data structures to store information comes in the form of added functionality.
A Cache in computer science terms can be thought of as a block of recently used data stored in a quickly accessible location in memory, resulting in faster performance when that same data is repeatedly pulled up.
If we consider an LRU Cache, it could be useful in an application that has users searching through a database for information. Normally every time a user looks something up, the app would ping its database with a request, taking precious time to do so. If, however, we store the most recently (or most commonly) searched-for items in an LRU cache, we can quickly check to see if the searched-for item exists in the cache, and if so we can retrieve it in significantly less time! Super useful.
Sounds great, how do we build one?
I'm glad you asked! Traditionally LRU Caches are built by combining a Hash Map with a Doubly Linked List, in order to maintain fast lookup of items and retrieval of most-recently-used and least-recently-used items in constant O(1) time.
However, if quickly implementing an LRU Cache from scratch in a small scale project is of interest to you, then one can be built out simply using nothing more than a JavaScript Class and a Map() object, at a cost to retrieval runtime.
The Least/Most Recently Used functionality will remain the same, which in practice is the key aspect of the data structure. If you're interested in learning how to create this version of an LRU Cache, then read on!
1. Establish the Class and Constructor
We'll be building out our LRU Cache using a JavaScript ES6 class, like so:
class LRUCache {
}
Within this class, we'll set a constructor so that every instance of an LRU Cache maintains the same structure. Our cache will take in a capacity as an argument, which will set the maximum size that our cache can grow to before we remove the least recently used item from its storage in order to save space and keep the structure organized.
We'll use this constructor to also establish the cache itself, using a JavaScript Map object:
class LRUCache {
constructor(capacity) {
this.cache = new Map();
this.capacity = capacity;
}
}
The reason we're using a Map object here is that JavaScript Maps maintain the order in which keys and values have been inserted. This does most of the work for us!
2. Build out the Get and Put methods of the Cache
Now, we're going to implement our two vital functions within the class: Get and Put, which will retrieve a value and insert a key/value pair into the cache respectively.
Let's start with Get:
class LRUCache {
constructor(capacity) {
this.cache = new Map();
this.capacity = capacity;
}
// Implementing Get method
get(key) {
if (!this.cache.has(key)) return undefined;
let val = this.cache.get(key);
this.cache.delete(key);
this.cache.set(key, val);
return val;
}
}
Let's break down what we just did above.
- We check to see if the key exists in our Map. If it doesn't, we return "undefined" (this could be any return value that represents a failed retrieval, such as -1 or an error message.)
- Next we declare a variable "val", get the value associated with that key, and assign it to the variable.
- We delete that key/value pair from our cache, and then set it again. Since our map keeps the order in which we insert things, this puts our retrieved key/value pair back at the front (most recently used) spot.
- We return the value for use in our program wherever this method was called.
And that's all there is to the Get method!
Now, we'll implement our Put method:
class LRUCache {
constructor(capacity) {
this.cache = new Map();
this.capacity = capacity;
}
get(key) {
if (!this.cache.has(key)) return -1;
let val = this.cache.get(key);
this.cache.delete(key);
this.cache.set(key, val);
return val;
}
// Implementing Put method
put(key, value) {
this.cache.delete(key);
if (this.cache.size === this.capacity) {
this.cache.delete(this.cache.keys().next().value);
this.cache.set(key, value);
} else {
this.cache.set(key, value);
}
}
}
Let's break it down into steps:
- The first line checks if the key already exists in the Map and deletes it if so; calling .delete() either deletes the key/value pair if it exists OR returns undefined and continues if it doesn't.
- If our cache is currently at its maximum capacity (
cache.size === this.capacity), we delete our least recently used key/value pair by usingthis.cache.keys().next().valueto get the first key of the Map using an iterator object and passing it as an argument tothis.cache.delete(). We then set a new key/value pair in the cache using the arguments passed into the Put method. - If we're not currently at maximum capacity, we simply add the new key/value pair as normal.
And there's our Set method!
3. Implement getLeastRecent and getMostRecent methods
At this point we've created the fundamental functionality of an LRU Cache, but there's one step to go in order to have a complete data structure. We might want to retrieve the Least Recently Used (LRU) or Most Recently Used (MRU) values!
In order to do so, we're going to convert our Map into an array, then retrieve the first (LRU) and last (MRU) values of the array respectively:
class LRUCache {
constructor(capacity) {
this.cache = new Map();
this.capacity = capacity;
}
get(key) {
if (!this.cache.has(key)) return -1;
let val = this.cache.get(key);
this.cache.delete(key);
this.cache.set(key, val);
return val;
}
put(key, value) {
this.cache.delete(key);
if (this.cache.size === this.capacity) {
this.cache.delete(this.cache.keys().next().value);
this.cache.set(key, value);
} else {
this.cache.set(key, value);
}
}
// Implement LRU/MRU retrieval methods
getLeastRecent() {
return Array.from(this.cache)[0];
}
getMostRecent() {
return Array.from(this.cache)[this.cache.size - 1];
}
}
And there we go! If you wanted to, you could use this same Array-from-Map concept to find second-least-recently-used, third-most-recently-used, etc.
That's our LRU Cache!
If you've read this far, thanks so much for taking the time to check out my post!
I hope it's been helpful to those of you trying to learn and understand data structures, or those of you trying to implement them in JavaScript. 😄
Top comments (11)
when get a key and it is not there, I would return undefined or an error.
-1could also be the value. It reminds me to the time when we neededif (array.indexOf(needle)===-1)ï¼›{...}and today we havearray.includes.It is very interesting how you are using the
iteratorfromcache.keys().also, it would be interesting to add a time-to-life, but that can be a good homework 😊
Thanks for your feedback Tobias! I was wondering what the best return value would be for when a key wasn't found, you're definitely right about "undefined" or throwing an error being better than returning a string. I'll edit that part to make it a bit more clear.
Also a great suggestion to add a timed-life option, I'll start thinking about how to implement that!
Delegate the problem to the caller -- have them provide a value to return in the not-found case.
a small improve to the code, instead of:
Just do:
Wow, TIL about Map objects. Great article, thanks for sharing!
You're very welcome! Thanks so much for reading. I only recently started learning about Map and Set objects myself, and about how they differ from standard JavaScript objects. They're super useful for certain situations like this.
Is the first time I heard about this data structure, it seems very useful. Thanks for sharing! Awesome post and explanation
Thank you for posting this. This is really helpful. I liked explanations and clean code.
Thanks for posting this, but it would be great if you can also add the time complexity of get and put methods.
great post thanks
great post man, very helpful. Since recently heard about this ds, would try to implement in my project.