LRU algorithm
What is the LRU algorithm
LRU algorithm is also called delete the most recently unused algorithm, which is a cache elimination strategy.
The capacity of the computer is limited. If the memory is full, the old data has to be deleted to fill in the new data. The question is, what kind of data is to be deleted?
LRU cache algorithm is a common strategy. The full name is also called Least Recently Used, which means that we consider the Recently Used data to be “useful” and the data that has not been Used for a long time to be useless. When the memory is full, the data that has not been Used for a long time will be deleted first.
Usage scenarios
, for example, there is now a shoe ark, can deposit inside 6 pairs of shoes, every new a pair of shoes, you will enter a new shoe store, every time to store, you can determine whether there is a spare seat, if available seats, you can store in success, if not, you will need to be very reluctantly give up what one favours, recently not to wear the shoes (longest), Make room for new shoes and put them in storage. This is a typical LRU design idea.
I hope I can give you some idea of the LRU algorithm by taking my favorite shoes as an example. I believe you can do it.
Design idea of algorithm
The LRU caching mechanism can be implemented with a hash table and a bidirectional linked list. We maintain all the key-value pairs in the cache with a hash table and a bidirectional linked list.
-
The bidirectional list stores these key-value pairs in the order in which they are used, with the key-value pair near the head being the most recently used and the key-value pair near the tail being the oldest unused.
-
A hash table is a common HashMap that maps the cache data to its position in a bidirectional linked list by keys.
As shown in the figure, in the bidirectional linked list, the head data is always the node with the highest activity, and the tail is the node with the lowest activity. If the container is full, the tail node will be eliminated first and new data will be inserted into the head to ensure that the head is always the node with the highest activity.
The specific implementation
- Firstly, the data structure is defined to store the k value, V value, predecessor node and successor node of the node
/** Data structure */
class CacheNode {
Object key; / / key
Object value; / / value
CacheNode next; // Subsequent nodes
CacheNode pre; // Predecessor node
}
Copy the code- Define global variables: caches, capacity, head and tail nodes in containers
/** Cache container */
HashMap<K, CacheNode> caches;
/** The capacity */
private int capacity;
/** the header */
private CacheNode head;
/** last node */
private CacheNode tail;
Copy the code- Initialize the container size by using the constructor
/** instantiate */
public LRUCache(int size) {
// Container size
this.capacity = size;
// Instantiate the container
caches = new HashMap<K, CacheNode>(size);
}
Copy the code- Write the put method
/** * add k-v *@paramK key *@paramV value *@returnValue * /
public V put(K k, V v) {
// 1. Check whether the container exists
CacheNode cacheNode = caches.get(k);
// 2. If the CacheNode exists in a container, move it to the top of the container queue
// 3. If not in the container
if (cacheNode == null) {
// 3.1 Check whether the actual size of the container is greater than the maximum number of containers allowed
if (caches.size() >= capacity) {
// 3.1.1 If the actual size of the container is greater than the maximum number allowed, delete the CacheNode node (inactive node) at the end of the container
caches.remove(tail.key);
// Update the pointer of the tail node to its predecessor
removeLast();
}
3.1.2 If the actual size of the container is smaller than the maximum quantity allowed
3.1.2.1 Encapsulate it as a CacheNode node and add it to the container
cacheNode = new CacheNode();
cacheNode.key = k;
}
cacheNode.value = v;
// Move the nodes to the container header to ensure that the nodes in the container are sorted by activity
moveToFirst(cacheNode);
// Encapsulate the current node as a CacheNode to populate the container
caches.put(k ,cacheNode);
return v;
}
Copy the code- Write the get method
/** * Get the object *@param k
* @return* /
public V get(K k) {
// check whether k exists in the container
CacheNode node = caches.get(k);
if (node == null) {
return null;
}
// Move the node to the container head
moveToFirst(node);
return (V)node.value;
}
Copy the code- Custom method moveToFirst() method
/** * Move CacheNode to the container header & update the head and tail nodes to point to * 0. If the current node is equal to head, there is no need to move to return * 1. If the next node of the current node is not empty, point the successor node of the current node to the predecessor node of the current node * 2. If the pre node of the current node is not empty, point the successor node of the predecessor node of the current node to the successor node of the current node * 3. Update the tail node to the current node * 4. If both head and tail nodes are empty, the current node is directly assigned to the head and tail nodes -- the first k-v key-value pair * is added@param cacheNode
*/
private void moveToFirst(CacheNode cacheNode) {
// If the current node is equal to head, there is no need to move to direct return
if (head == cacheNode) return;
// If the next node of the current node is not empty, point the successor node of the current node to the predecessor node of the current node
if(cacheNode.next ! =null) cacheNode.next.pre = cacheNode.pre;
// If the pre node of the current node is not empty, point the successor node of the current node to the successor node of the current node
if(cacheNode.pre ! =null) cacheNode.pre.next = cacheNode.next;
// Update the tail node equal to the current node. The tail node points to the successor node of the current node
if (tail == cacheNode) tail = cacheNode.pre;
// If the head and tail nodes are empty, the current node is directly assigned to the head and tail nodes -- indicating the first addition of k-v key-value pairs
if (head == null || tail == null) {
head = tail = cacheNode;
return;
}
// Next of the current node points to the head node
cacheNode.next = head;
// The successor of the head node points to the current node
head.pre = cacheNode;
// Assign the current node to the head node
head = cacheNode;
// Empty the successor node of the current node
head.pre = null;
}
Copy the codeRemoveLast () method
/** * point the tail node to tail.pre */
private void removeLast(a) {
if(tail ! =null) {
// Update the tail node to its predecessor
tail = tail.pre;
// If the tail node is empty, head is empty
if (tail == null) head = null;
// Otherwise, empty next for tail nodes
else tail.next = null; }}Copy the codeThe toString () method
@Override
public String toString(a) {
StringBuilder sb = new StringBuilder();
CacheNode node = head;
while(node ! =null) {
sb.append(String.format("%s:%s ", node.key, node.value));
node = node.next;
}
return sb.toString();
}
Copy the code- The test codeWriting test methods
public static void main(String[] args) {
LRUCache<Integer, String> lru = new LRUCache<>(3);
lru.put(1."a");
System.out.println(lru.toString());
lru.put(2."b"); // 2:b 1:a
System.out.println(lru.toString());
lru.put(3."c"); // 3:c 2:b 1:a
System.out.println(lru.toString());
lru.put(4."d"); // 4:d 3:c 2:b
System.out.println(lru.toString());
lru.put(1."aa"); // 1:aa 4:d 3:c
System.out.println(lru.toString());
lru.put(2."bb"); // 2:bb 1:aa 4:d
System.out.println(lru.toString());
lru.put(5."e"); // 5:e 2:bb 1:aa
System.out.println(lru.toString());
lru.get(1); // 1:aa 5:e 2:bb
System.out.println(lru.toString());
}
Copy the code- The result is shown below
At this point, LRU algorithm has been completed, congratulations to you, master another algorithm, another step from Dachang. Ollie here!!
The public,
I will share technology from time to time, I hope you pay more attention to it
The code has been included in Github, if necessary, can be downloaded
Github.com/memo012/jav…