FIFO
The simplest cache algorithm is to set the cache upper limit. When the cache upper limit is reached, it will be eliminated according to the first-in-first-out strategy, and then a new k-v is added.
An object is used as a cache, and an array is used to coordinate the order when the object is added to the object, to determine whether the upper limit is reached. If the upper limit is reached, the first element key in the array will be taken, and the key value in the object will be deleted.
/**
* FIFO queue algorithm implements cache
* Requires an object and an array as aid
* Array records enter order
*/
class FifoCache{
constructor(limit){
= limit || 10
= {}
= []
}
set(key,value){
let map =
let keys =
if (!(map,key)) {
if ( === ) {
delete map[()]//First in, first out, delete the first element of the queue }
(key)
}
map[key] = value//Assign the key in the map regardless of whether it exists or not }
get(key){
return [key]
}
}
= FifoCache
LRU
LRU (Least recently used, least recently used) algorithm. The view of this algorithm is that the data that has been accessed recently will have a high probability of accessing in the future. When the cache is full, the most unattended person will be given priority.
Algorithm implementation idea: Based on the data structure of a double-linked list, if there is no full, the new k-v is placed at the head of the linked list. In the future, the k-v is moved to the front every time the k-v in the cache is obtained, and the last one is eliminated first when the cache is full.
The characteristics of a bidirectional linked list are: head and tail pointers, and each node has prev (predecessor) and next (successor) pointers pointing to its previous and next nodes respectively.
Key points: During the insertion of double-linked lists, you must pay attention to the order issue. You must first process the pointer while keeping the linked lists continuously, and finally point the original pointer to the newly inserted element. In the implementation of the code, please pay attention to the order I explained in the comments!
class LruCache {
constructor(limit) {
= limit || 10
//The head pointer points to the header element, which is the most commonly used element = = undefined
= {}
= 0
}
get(key, IfreturnNode) {
let node = [key]
// If the cache object with the `key` property cannot be found if (node === undefined) return
// If the cache object found is already tail (recently used) if (node === ) { //Distinguish whether the node is the first node // If so, everyone will be happy, don't move the elements, just return directly return returnnode ?
node :
}
// It's not a head node, so the element must be moved if () { //First of all, we need to determine whether the node has a front driver if (node === ) { //There is a front-driver. If it is a tail node, one more step, let the tail pointer point to the front-driver of the current node =
}
//Transfer the successor of the current node to the predecessor of the current node to point to the direction. =
}
if () { //Discern whether the node has successor //If there is a successor, let the successor forward drive point to the current node's front drive =
//The whole process is to take out the current node and ensure that the linked list is continuous. The current node is moved below. }
= undefined //Move to the front, so there is no front drive = //Notice! ! ! Here we have to take over the previous line first! ! ! ! Let the successor of the current node point to the original row if () {
= node //Let the front driver of the previous head point to the current node }
= node //This step can be performed after the handover is completed! Otherwise, you won’t be able to find the previous lineup! return IfreturnNode ?
node :
}
set(key, value) {
// The previous algorithm could directly store k-v, but now it is necessary to encapsulate simple k-v into a node that satisfies double-linked list //1. Check whether the node already has it let node = (key, true)
if (!node) {
if ( === ) { //Judge whether the cache reaches the upper limit //It has been reached, and the last node needs to be deleted. if () {
=
= undefined
//After smoothing the link break, destroy the current node = = undefined
[] = undefined
//The current cache memory releases a slot --
}
node = {
key: key
}
[key] = node
if(){//Discern whether there are nodes in the cache = node
=
}else{
//There is no value in the cache, everyone is happy, just let the head point to the new node = node
= node
}
++//Reduce one cache slot }
}
//If the node exists or not, you must reassign it to it. = value
}
}
= LruCache
The specific idea is that if the node you want to get is not a header node (that is, it is already the node you have used recently and does not need to move the node position), you must first perform a smooth link break operation, handle the relationship pointed by the pointer, take out the node that needs to be moved to the front, and perform the linked list insertion operation.
The above is all the content of this article. I hope it will be helpful to everyone's study and I hope everyone will support me more.