preface
This would work as long as you dare to write your resume in Redis, the interviewer will dare to call you a consortium handwritten LRU, but for handwritten LFU is relatively rare, but, if you can finish the LRU told the interviewer you also master LFU algorithm, then even if you don’t write only speak about, then in the interviewer is also big points!!!!!!
So, today let me help you to master this high-frequency test point!!
Tips: The main understanding of the idea in the comments, comments a little shallow, you can copy to their compiler to have a good look
Hand LRU
LRU is relatively simple in general, as long as you master the concept, even if you haven’t written for a long time you can still remember it!
LRU overall idea: the most recently used one is placed in the nearest position (far left), so the least used one is guaranteed to be naturally far away (to the right).
So we use a bidirectional list, but that’s not enough. We also need to use a Map to Map keys to the corresponding nodes
In a bidirectional linked list, virtual head and tail nodes are used as nodes so that there is no need to check the existence of adjacent nodes when adding and removing nodes.
public class Main {
// Define a bidirectional list
class DoubleLinkedList {
private int key;
private int value;
private DoubleLinkedList next;
private DoubleLinkedList prev;
public DoubleLinkedList() {
}
public DoubleLinkedList(int key, int value) {
this.key = key;
this.value = value; }}// Virtual head node, tail node
private DoubleLinkedList head,tail;
// Store the HashMap of the mapping
private Map<Integer,DoubleLinkedList> map = new HashMap<>();
/ / capacity
private int capacity;
// The actual number of elements
private int size;
// Data initialization
public Main(int capacity) {
this.capacity = capacity;
head = new DoubleLinkedList();
tail = new DoubleLinkedList();
head.next = tail;
tail.prev = head;
this.map = new HashMap<>();
}
// The exposed get method
public int get(int key) {
// If no key exists, -1 is returned
if(! map.containsKey(key)) {return -1;
}
// There is a key, so put it out
DoubleLinkedList node = map.get(key);
// Since this node is already used, it needs to be moved to the head node
moveToHead(node);
// Return value
return node.value;
}
// The exposed put method
public void put(int key,int value) {
// If the key exists
if (map.containsKey(key)) {
// Then get out, replace value, because used, move the head node
DoubleLinkedList node = map.get(key);
node.value = value;
moveToHead(node);
}else {
// The key does not exist
// Create a new node
DoubleLinkedList newNode = new DoubleLinkedList(key, value);
// Add a node to the map and add it to the first node, adding 1 to the total number of elements
map.put(key,newNode);
addHead(newNode);
size++;
// If the total number of elements is greater than the maximum capacity
if (size > capacity) {
// Delete the last node, which is the least used noderemoveLastNode(); }}}// Delete the last node
private void removeLastNode() {
//tail is the virtual tail node, so the node before it is the last node
DoubleLinkedList lastNode = tail.prev;
// Delete a node
removeNode(lastNode);
map.remove(lastNode.key);
size--;
}
// Move the node to the head node
private void moveToHead(DoubleLinkedList node) {
removeNode(node);
addHead(node);
}
// Add a node to the first node
private void addHead(DoubleLinkedList node) {
node.prev = head;
node.next = head.next;
head.next.prev = node;
head.next = node;
}
// Delete a node
private void removeNode(DoubleLinkedList node) {
node.next.prev = node.prev;
node.prev.next = node.next;
node.prev = null;
node.next = null; }}Copy the codeForce button: LFU address
Hand LFU
Unlike LFU, LFU is arranged according to the frequency of use. In simple terms, LFU is arranged according to the frequency of use (if the number of use is guaranteed, it is arranged according to the recent use). Therefore, for linked list nodes, one more count of use should be defined
public class Main {
// Define the linked list
class Node {
private int key;
private int value;
private int count;
private Node next;
private Node prev;
public Node() {
}
public Node(int key, int value,int count) {
this.key = key;
this.value = value;
this.count = count; }}// Key is mapped to the corresponding Node
private Map<Integer,Node> keyMap;
// The frequency is mapped to the first node of the corresponding region
private Map<Integer,Node> cntMap;
// Virtual head node and tail node
private Node head,tail;
// Maximum capacity
private int capacity;
// Actual number of elements
private int size;
/ / initialization
public Main(int capacity) {
this.capacity = capacity;
this.head = new Node();
this.tail = new Node();
head.next = tail;
tail.prev = head;
keyMap = new HashMap<>();
cntMap = new HashMap<>();
}
// Expose the get method
public int get(int key) {
// If the capacity is 0, or there is no key, -1 is returned
if (capacity == 0| |! keyMap.containsKey(key)) {return -1;
}
// Remove the node corresponding to the key
Node node = keyMap.get(key);
// Update the usage frequency
updateNode_fre(node);
/ / return a value
return node.value;
}
// Update the node usage frequency
private void updateNode_fre(Node node) {
// The old usage frequency
int oldCnt = node.count;
// New usage frequency
int newCnt = node.count + 1;
// Which node should be saved before insertion
// Because the insertion position may or may not be the first node of the region
Node next = null;
// If the current node is the first node of the usage frequency
if (cntMap.get(oldCnt) == node) {
// If the current region has a next node, then the first node of the current region is set to the next node
if (node.next.count == node.count) {
cntMap.put(oldCnt,node.next);
}else {
// If there is no next node, delete this region. Because the node frequency is about to be updated
cntMap.remove(oldCnt);
}
// If no new region exists
if (cntMap.get(newCnt) == null) {
// Then create a new region and set this node as the first node
cntMap.put(newCnt,node);
// The frequency should be updated
node.count++;
// No further operations are required
return;
}else {
// If so, delete the node and set next as the first node of the new zoneremoveNode(node); next = cntMap.get(newCnt); }}else {
// If not, delete the node
removeNode(node);
// Next equals the first node of the frequency of the new used region if there is a new used region
// If not, insert before the current usage frequency is ok
if (cntMap.get(newCnt) == null) {
next = cntMap.get(oldCnt);
}else{ next = cntMap.get(newCnt); }}// All nodes that can come here are not updated, so update frequency
node.count++;
// Update frequency mapping
cntMap.put(newCnt,node);
// Insert before the specified node
addNode(node,next);
}
// Expose the put method externally
public void put(int key,int value) {
// If capacity is 0, key-value pairs cannot be put
if (capacity == 0) return;
// If key exists
if (keyMap.containsKey(key)) {
// Fetch node, replace value, update
Node node = keyMap.get(key);
node.value = value;
updateNode_fre(node);
}else {
// If the number of elements equals the maximum capacity
if (size == capacity) {
// Then we need to delete the motail node
deleteLastNode();
}
// Create a new node. The default number of times is 1
Node newNode = new Node(key, value,1);
// Since it is a new node, insert it at the head of the field count=1
Node next = cntMap.get(1);
// If there is no such area, insert it directly to
if (next == null) {
next = tail;
}
// Insert, update
addNode(newNode,next);
keyMap.put(key,newNode);
cntMap.put(1,newNode); size++; }}// Add a node
private void addNode(Node node, Node next) {
node.next = next;
node.prev = next.prev;
next.prev.next = node;
next.prev = node;
}
// Delete the last node
private void deleteLastNode() {
Node lastNode = tail.prev;
// If this node is the only node in this region, then this region needs to be removed
if (cntMap.get(lastNode.count) == lastNode) {
cntMap.remove(lastNode.count);
}
removeNode(lastNode);
keyMap.remove(lastNode.key);
size--;
}
// Delete a node
private void removeNode(Node node) {
node.next.prev = node.prev;
node.prev.next = node.next;
node.next = null;
node.prev = null; }}Copy the codeForce button: LFU address
Stern said
I am a Java architect, a Java programmer who loves to share knowledge. In the future, I will update my blog constantly, looking forward to your attention!!
Creation is not easy, if this blog is helpful to you, I hope you can like and follow me oh, thank you for your support, we will see you next time ~~~