The cache is one of the greatest innovations of computer science 🔥🔥🔥. It significantly reduces work on the CPU and provides massive performance gains in terms of speed. 😃
It works by saving the result of computations that may be needed later. For example: say you had a service that, given a string, generated a hash. A cache could save time and resources by checking if the hash of the received string had already been generated. If it had, and was still in the cache, it would be returned without running through the hashing algorithm again.
Today, we’ll be building a LRU (Last Recently Used) cache that stores a fixed amount of strings and ejects the last used item once the cache is full.
This won’t be anything you would want to run in production. But it will clearly demonstrate the data structures and algorithms that make this type of cache work.
To get and run the final results:
git clone https://github.com/Lebonesco/go_lru_cache.gitgo run main.go
Let’s jump into some code!
We’ll start by defining our data structures. These will include Node, Queue, Hash, and Cache. Our Queue will be a doubly linked list of Node pointers that are mapped to from the Hash. This will allow for O(1) insertion and deletion of values. 👍
Note: We are just caching strings right now, but any data type could replace it.
Next, we’ll setup our constructor functions for the Cache and Queue. Although, Hash starts out empty it needs to be initialized or it will result in a “nil pointer error” later on. In addition, we create two empty Nodes for the Head and Tail. This will make more sense when we move onto our Add() and Remove() methods.
Onto the primary code of the cache.
The cache has three methods that are required to make it work: **Check()**(receives the string from the user and returns the result), **Add()**(adds a string to the cache), **Remove()**(ejects a string from the cache).
Inside of Check(), if the string already exists in the cache we first remove it before adding it back again so that the string gets shifted to the front of the Queue.
Both Add() and Remove() involve similar operations that reassign Left and Right Node pointers in the Queue.
Awesome, we now have a working cache! 🎉🎉🎉
The last step is to add a main() and some display methods to demonstrate our results.
To see your code in action, run:
go run main.goSTART CACHEadd: cat1 - [{cat}]add: blue2 - [{blue} <--> {cat}]add: dog3 - [{dog} <--> {blue} <--> {cat}]add: tree4 - [{tree} <--> {dog} <--> {blue} <--> {cat}]add: dragon5 - [{dragon} <--> {tree} <--> {dog} <--> {blue} <--> {cat}]add: potatoremove: cat5 - [{potato} <--> {dragon} <--> {tree} <--> {dog} <--> {blue}]add: houseremove: blue5 - [{house} <--> {potato} <--> {dragon} <--> {tree} <--> {dog}]remove: treeadd: tree5 - [{tree} <--> {house} <--> {potato} <--> {dragon} <--> {dog}]add: catremove: dog5 - [{cat} <--> {tree} <--> {house} <--> {potato} <--> {dragon}]
Thank you for taking the time to read this article.
If you found it helpful or interesting please let me know 👏👏👏.