“This is the 11th day of my participation in the August More Text Challenge. For details, see: August More Text Challenge.”

“LRU Master’s Java Implementation”

“The Old man’s LRU is fun.”

“The Adventures of Data Caching Part II was given a lesson by the expiration key Manager.”

“A lesson for the obsolete cop in The first episode of the Data Cache Adventure.”

LRU is going to be rubbed against the ground

After the professional interpretation of the data by LRU senior brother last time, I clearly understood the bottom layer of LRU(the least recently eliminated algorithm), which requires sequence and query to insert data to support the operation, and the data should be screened more efficiently. Although LRU senior brother is very strong in martial arts, the data is still holding back one’s breath. Must let the old man to watch the bottom skills teach him, this is not, and began to test the logic of LRU bottom;

Although you can use the LinkedHashMap in Java collections to organize a container and make a qualified LRU implementation, the underlying layer encapsulates a lot. So the data feels like it’s going to take care of itself

Get to work.

LRU base implementation:

Where the HASHMAP is to guarantee the key-value pair, lookup, two-way linked list guarantees the position of the key-value pair in the queue;

For yourself to manually write an LRU algorithm, you need to determineAt two o ‘clock:

  1. Need a NODE NODE, determine the pointer before and after, ensure the order

  2. Map, as a storage collection of node data, can be queried and inserted

Why do you need a Node Node as a data carrier?

Let’s use the analogy of the underlying implementation of the collection container HashMap: Its underlying storage is the put method; In turn, is

We need to create the node data;

Create a bidirectional queue, ensuring order;

Enter delete, add the operation of table header to adjust the order, so that each time the data can be dynamically adjusted; Truly achieve the effective elimination of the order;

The last structure we did was to create a collection map in a two-sided queue

Create a Node to store data

Class node <k, v> {k keys; class node <k, v> {k keys; v values; Node<k, v> prev; Node<k, v> next; Public Node() {this.prev = null; this.next = null; Public Node(k keys, v values) {this.keys = keys; this.values = values; this.prev = this.next = null; }}Copy the code

Create a bidirectional queue

class DoubleLinkedList<k, v> { Node<k, v> head; Node<k, v> tail; Public DoubleLinkedList() {this.head = new Node<k, v>(); this.tail = new Node<k, v>(); // Next to the head node is the tail node, and before the tail node is the head node. tail.prev = head; }Copy the code

Add a header

Public void addHeader(Node<k, v> Node) {/** * Put Node in the table header * the Node before the current Node - is the current Node (after a Node enters, the new Node is the next Node after the new Node, Next = head. Next; next = head. node.prev = head; /** * The next node is the tail node, and the last node is the node */ head. Next is the current node */ head. head.next = node; }Copy the code

Delete operation

Public void removeNode(node <k, v> node) {/** * remove the current node * the next node is the tail, the previous node is the tail, Prev = node.prev; / node.next. Prev = node.prev; //head node.prev.next = node.next; node.prev = null; node.next = null; } public Node getLast() {return tail.prev; }Copy the code

Code implementation:

package com.lru; import java.util.HashMap; import java.util.Map; /** * @author Lucas * @create 2021-08-11 20:14 * @description lRU algorithm */ public class LRUCache {// create a storage node class, Class node <k, v> {k keys; v values; Node<k, v> prev; Node<k, v> next; Public Node() {this.prev = null; this.next = null; Public Node(k keys, v values) {this.keys = keys; this.values = values; this.prev = this.next = null; Class DoubleLinkedList<k, v> {node <k, v> head; Node<k, v> tail; Public DoubleLinkedList() {this.head = new Node<k, v>(); this.tail = new Node<k, v>(); // Next to the head node is the tail node, and before the tail node is the head node. tail.prev = head; } public void addHeader(Node<k, v> Node) {/** * Put Node in the table header * the Node before the current Node - is the current Node (after a Node enters, the Node next to the new Node, Next = head. Next; next = head. node.prev = head; /** * The next node is the tail node, and the last node is the node */ head. Next is the current node */ head. head.next = node; Public void removeNode(node <k, v> node) {/** * remove the current node from the node. Prev = node.prev; / node.next. Prev = node.prev; //head node.prev.next = node.next; node.prev = null; node.next = null; } public Node getLast() {return tail.prev; } } private int cacheSize; Map<Integer, Node<Integer, Integer>> dateMap; DoubleLinkedList<Integer, Integer> doubleLinkedList; Public LRUCache(int cacheSize) {this.cachesize = cacheSize; DateMap = new HashMap<>(); DoubleLinkedList = new doubleLinkedList <>(); Public int get(int key) {/** * 1. Return * 2. / */ if (! dateMap.containsKey(key)) { return -1; } Node<Integer, Integer> dataNode = dateMap.get(key); / * * * to the queue order, delete before the location of the node, added to the header. * / doubleLinkedList removeNode (dataNode); / / add the node to the header doubleLinkedList. AddHeader (dataNode); return dataNode.values; } public void put(int key, int value) {/** ** If key does not exist, update operation * 2. Add Node information * */ if (datemap.containskey (key)) {// Update Node information data Node<Integer, Integer> Node = datemap.get (key); node.values = value; dateMap.put(key, node); / / to join the queue header doubleLinkedList. RemoveNode (node); doubleLinkedList.addHeader(node); } else {// Whether the maximum capacity is reached if (datemap.size () == cacheSize) {Node lastNode = DoublelinkedList.getLast (); Remove (lastnode.keys) datemap.remove (lastnode.keys) datemap.remove (lastnode.keys); doubleLinkedList.removeNode(lastNode); DateNode = new node (key, value); /** * New node (key, value); dateMap.put(key, dateNode); / / to join the queue header doubleLinkedList. AddHeader (dateNode); }}}Copy the code

Code tests:

public static void main(String[] args) { LRUCache lruCacheDemo = new LRUCache(3); lruCacheDemo.put(1, 1); lruCacheDemo.put(2, 1); lruCacheDemo.put(3, 1); System.out.println(lruCacheDemo.dateMap.keySet()); lruCacheDemo.put(4, 1); System. The out. Println (" increase after the fourth, the list is "+ lruCacheDemo. DateMap. KeySet ()); System.out.println("--------------------------------------------"); lruCacheDemo.put(3, 1); System.out.println(lruCacheDemo.dateMap.keySet()); lruCacheDemo.put(3, 1); System.out.println(lruCacheDemo.dateMap.keySet()); lruCacheDemo.put(3, 1); System.out.println(lruCacheDemo.dateMap.keySet()); System.out.println("--------------------------------------------"); lruCacheDemo.put(5, 1); System.out.println(lruCacheDemo.dateMap.keySet()); /** * [1, 2, 3] * List is [2, 3, 4] * -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- - * [2, 3, 4] * [2, 3, 4] * [2, 3, 4] * -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- - * * /} [3, 4, 5]Copy the code

Luca concludes:

Code tested. The effect of eliminating LRU mechanism can be realized. For the insertion order, and the deletion and addition of nodes, attention should be paid to the details, and the specific implementation should be completed according to the steps;

LRU data cache adventure is over, hope this data adventure can help you to get a different cache perspective, remember to like oh, good night;