Detailed explanation of steps to implement caching algorithm in JS
This time I will bring you a detailed explanation of the steps to implement the caching algorithm in JS. What are the precautions for implementing the caching algorithm in JS. The following is a practical case, let's take a look.
FIFO
The simplest caching 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 added Enter new k-v.
Using an object as a cache, an array matches the order in which records are added to the object to determine whether the upper limit is reached. If the upper limit is reached, take the first element key in the array, corresponding to Delete the key value in the object.
/**
* FIFO队列算法实现缓存
* 需要一个对象和一个数组作为辅助
* 数组记录进入顺序
*/
class FifoCache{
constructor(limit){
this.limit = limit || 10
this.map = {}
this.keys = []
}
set(key,value){
let map = this.map
let keys = this.keys
if (!Object.prototype.hasOwnProperty.call(map,key)) {
if (keys.length === this.limit) {
delete map[keys.shift()]//先进先出，删除队列第一个元素
}
keys.push(key)
}
map[key] = value//无论存在与否都对map中的key赋值
}
get(key){
return this.map[key]
}
}
module.exports = FifoCacheLRU
LRU (Least recently used, least recently used) algorithm. The point of view of this algorithm is that the data that has been accessed recently has a greater probability of being accessed in the future. When the cache is full, the least interested data will be eliminated first.
Algorithm implementation idea: Based on the data structure of a double linked list, when it is not full, the new k-v is placed at the head of the linked list, and the k-v is moved every time the k-v in the cache is obtained. When the cache is full, the ones at the end will be eliminated first.
The characteristics of a doubly linked list are head and tail pointers. Each node has prev (predecessor) and next (successor) pointers pointing to its previous and next nodes respectively.
Key point: Pay attention to the order issue during the insertion process of the double linked list. The pointer must be processed first while keeping the linked list continuous, and finally the original pointer points to the newly inserted element. In the implementation of the code Please pay attention to the order I explained in Notes!
class LruCache {
constructor(limit) {
this.limit = limit || 10
//head 指针指向表头元素，即为最常用的元素
this.head = this.tail = undefined
this.map = {}
this.size = 0
}
get(key, IfreturnNode) {
let node = this.map[key]
// 如果查找不到含有`key`这个属性的缓存对象
if (node === undefined) return
// 如果查找到的缓存对象已经是 tail (最近使用过的)
if (node === this.head) { //判断该节点是不是是第一个节点
// 是的话，皆大欢喜，不用移动元素，直接返回
return returnnode ?
node :
node.value
}
// 不是头结点，铁定要移动元素了
if (node.prev) { //首先要判断该节点是不是有前驱
if (node === this.tail) { //有前驱，若是尾节点的话多一步，让尾指针指向当前节点的前驱
this.tail = node.prev
}
//把当前节点的后继交接给当前节点的前驱去指向。
node.prev.next = node.next
}
if (node.next) { //判断该节点是不是有后继
//有后继的话直接让后继的前驱指向当前节点的前驱
node.next.prev = node.prev
//整个一个过程就是把当前节点拿出来，并且保证链表不断，下面开始移动当前节点了
}
node.prev = undefined //移动到最前面，所以没了前驱
node.next = this.head //注意！！！ 这里要先把之前的排头给接到手！！！！让当前节点的后继指向原排头
if (this.head) {
this.head.prev = node //让之前的排头的前驱指向现在的节点
}
this.head = node //完成了交接，才能执行此步！不然就找不到之前的排头啦！
return IfreturnNode ?
node :
node.value
}
set(key, value) {
// 之前的算法可以直接存k-v但是现在要把简单的 k-v 封装成一个满足双链表的节点
//1.查看是否已经有了该节点
let node = this.get(key, true)
if (!node) {
if (this.size === this.limit) { //判断缓存是否达到上限
//达到了，要删最后一个节点了。
if (this.tail) {
this.tail = this.tail.prev
this.tail.prev.next = undefined
//平滑断链之后，销毁当前节点
this.tail.prev = this.tail.next = undefined
this.map[this.tail.key] = undefined
//当前缓存内存释放一个槽位
this.size--
}
node = {
key: key
}
this.map[key] = node
if(this.head){//判断缓存里面是不是有节点
this.head.prev = node
node.next = this.head
}else{
//缓存里没有值，皆大欢喜，直接让head指向新节点就行了
this.head = node
this.tail = node
}
this.size++//减少一个缓存槽位
}
}
//节点存不存在都要给他重新赋值啊
node.value = value
}
}
module.exports = LruCacheThe specific idea is that if the node you want to get is not the head node (that is, it is already the most recently used node, and there is no need to move the node position), you must first perform a smooth link breaking operation and handle the pointer pointed to. Relationship, take out the node that needs to be moved to the front, and perform the insertion operation into the linked list.
I believe you have mastered the method after reading the case in this article. For more exciting information, please pay attention to other related articles on the php Chinese website!
Recommended reading:
How to implement dynamic parameter passing of query in vue-router
Why can’t you use IP to access webpack locally? Development environment
The above is the detailed content of Detailed explanation of steps to implement caching algorithm in JS. For more information, please follow other related articles on the PHP Chinese website!
Hot AI Tools
Undresser.AI Undress
AI-powered app for creating realistic nude photos
AI Clothes Remover
Online AI tool for removing clothes from photos.
Undress AI Tool
Undress images for free
Clothoff.io
AI clothes remover
Video Face Swap
Swap faces in any video effortlessly with our completely free AI face swap tool!
Hot Article
Hot Tools
Notepad++7.3.1
Easy-to-use and free code editor
SublimeText3 Chinese version
Chinese version, very easy to use
Zend Studio 13.0.1
Powerful PHP integrated development environment
Dreamweaver CS6
Visual web development tools
SublimeText3 Mac version
God-level code editing software (SublimeText3)
Hot Topics
How to make Google Maps the default map in iPhone
Apr 17, 2024 pm 07:34 PM
The default map on the iPhone is Maps, Apple's proprietary geolocation provider. Although the map is getting better, it doesn't work well outside the United States. It has nothing to offer compared to Google Maps. In this article, we discuss the feasible steps to use Google Maps to become the default map on your iPhone. How to Make Google Maps the Default Map in iPhone Setting Google Maps as the default map app on your phone is easier than you think. Follow the steps below – Prerequisite steps – You must have Gmail installed on your phone. Step 1 – Open the AppStore. Step 2 – Search for “Gmail”. Step 3 – Click next to Gmail app
Steps to upgrade to the latest version of WeChat (Easily master the upgrade method to the latest version of WeChat)
Jun 01, 2024 pm 10:24 PM
WeChat is one of the social media platforms in China that continuously launches new versions to provide a better user experience. Upgrading WeChat to the latest version is very important to keep in touch with family and colleagues, to stay in touch with friends, and to keep abreast of the latest developments. 1. Understand the features and improvements of the latest version. It is very important to understand the features and improvements of the latest version before upgrading WeChat. For performance improvements and bug fixes, you can learn about the various new features brought by the new version by checking the update notes on the WeChat official website or app store. 2. Check the current WeChat version We need to check the WeChat version currently installed on the mobile phone before upgrading WeChat. Click to open the WeChat application "Me" and then select the menu "About" where you can see the current WeChat version number. 3. Open the app
This Apple ID is not yet in use in the iTunes Store: Fix
Jun 10, 2024 pm 05:42 PM
When logging into iTunesStore using AppleID, this error saying "This AppleID has not been used in iTunesStore" may be thrown on the screen. There are no error messages to worry about, you can fix them by following these solution sets. Fix 1 – Change Shipping Address The main reason why this prompt appears in iTunes Store is that you don’t have the correct address in your AppleID profile. Step 1 – First, open iPhone Settings on your iPhone. Step 2 – AppleID should be on top of all other settings. So, open it. Step 3 – Once there, open the “Payment & Shipping” option. Step 4 – Verify your access using Face ID. step
Shazam app not working in iPhone: Fix
Jun 08, 2024 pm 12:36 PM
Having issues with the Shazam app on iPhone? Shazam helps you find songs by listening to them. However, if Shazam isn't working properly or doesn't recognize the song, you'll have to troubleshoot it manually. Repairing the Shazam app won't take long. So, without wasting any more time, follow the steps below to resolve issues with Shazam app. Fix 1 – Disable Bold Text Feature Bold text on iPhone may be the reason why Shazam is not working properly. Step 1 – You can only do this from your iPhone settings. So, open it. Step 2 – Next, open the “Display & Brightness” settings there. Step 3 – If you find that “Bold Text” is enabled
Detailed explanation of the steps to obtain Win11 system administrator permissions
Mar 08, 2024 pm 09:09 PM
Windows 11, as the latest operating system launched by Microsoft, is deeply loved by users. In the process of using Windows 11, sometimes we need to obtain system administrator rights in order to perform some operations that require permissions. Next, we will introduce in detail the steps to obtain system administrator rights in Windows 11. The first step is to click "Start Menu". You can see the Windows icon in the lower left corner. Click the icon to open the "Start Menu". In the second step, find and click "
iPhone screenshots not working: How to fix it
May 03, 2024 pm 09:16 PM
Screenshot feature not working on your iPhone? Taking a screenshot is very easy as you just need to hold down the Volume Up button and the Power button at the same time to grab your phone screen. However, there are other ways to capture frames on the device. Fix 1 – Using Assistive Touch Take a screenshot using the Assistive Touch feature. Step 1 – Go to your phone settings. Step 2 – Next, tap to open Accessibility settings. Step 3 – Open Touch settings. Step 4 – Next, open the Assistive Touch settings. Step 5 – Turn on Assistive Touch on your phone. Step 6 – Open “Customize Top Menu” to access it. Step 7 – Now you just need to link any of these functions to your screen capture. So click on the first
Clock app missing in iPhone: How to fix it
May 03, 2024 pm 09:19 PM
Is the clock app missing from your phone? The date and time will still appear on your iPhone's status bar. However, without the Clock app, you won’t be able to use world clock, stopwatch, alarm clock, and many other features. Therefore, fixing missing clock app should be at the top of your to-do list. These solutions can help you resolve this issue. Fix 1 – Place the Clock App If you mistakenly removed the Clock app from your home screen, you can put the Clock app back in its place. Step 1 – Unlock your iPhone and start swiping to the left until you reach the App Library page. Step 2 – Next, search for “clock” in the search box. Step 3 – When you see “Clock” below in the search results, press and hold it and
Slow Cellular Data Internet Speeds on iPhone: Fixes
May 03, 2024 pm 09:01 PM
Facing lag, slow mobile data connection on iPhone? Typically, the strength of cellular internet on your phone depends on several factors such as region, cellular network type, roaming type, etc. There are some things you can do to get a faster, more reliable cellular Internet connection. Fix 1 – Force Restart iPhone Sometimes, force restarting your device just resets a lot of things, including the cellular connection. Step 1 – Just press the volume up key once and release. Next, press the Volume Down key and release it again. Step 2 – The next part of the process is to hold the button on the right side. Let the iPhone finish restarting. Enable cellular data and check network speed. Check again Fix 2 – Change data mode While 5G offers better network speeds, it works better when the signal is weaker
