Use js to complete an LRU cache

1. What is? LRU cache  

LRU  The full English name is  Least Recently Used, English translation ” Recently at least use “ It means .  It is one of the page replacement algorithms . 

Baidu Encyclopedia  

LRU  Is a common page replacement algorithm , Select the most recent unused page to weed out . The algorithm gives each page an access field , Used to record the time of a page since it was last visited  t, When a page has to be eliminated , Select one of the existing pages  t  The most valuable , That is, the most recently used pages are eliminated . 

Popular explanation means

Suppose we have a piece of memory , It is specially used to cache the web pages we recently visited , Visit a new web page , We will add a web page address to the memory , With the increasing number of web pages , The memory is full , At this time, we need to consider deleting some web pages . At this time, we find the address of the web page we first visited in memory , Then delete it .
This whole process can be called  LRU  Algorithm . 

Two points need attention ： 

① When we visit a web address that already exists in memory , Then the URL needs to update the storage order in memory . 

② When we have no data in memory , There is no need to delete .

2. Realization LRU Train of thought  

• We need a limited storage space , Because infinity doesn't have to be used LRU The data has been deleted .
• The data stored in our storage space needs to be orderly , Because we have to delete data in order , So think about it Array、Map Data structures to store , Out of commission Object, Because it's disordered .
• We can delete or add and obtain the specified data in this storage space .
• When the storage space is full , When adding data , The oldest piece of data will be automatically deleted .

Implementation is that we implement a LRUCache Class , Used as storage space , use es6 Medium Map Data structures store data , Because its time complexity is  O(1)  And orderly , Realization get,set Method is used to get and add data , The storage space is limited in length , There is no need to provide a deletion method , When our memory length is full , Automatically delete the most recently unused data , When using get When getting data , Update the order to the top

3. Code  

js 

class LRUCache {
  constructor(length) {
    this.length = length  //  Storage length 
    this.map = new Map()  //  Store the data 
  }

  //  Store the data , By means of key value pairs 
  set(key, value) {
    if(this.map.has(key)) {
      this.map.delete(key)
    }
    this.map.set(key, value)

    //  If the capacity is exceeded , Delete the longest data （map Middle is the first ）
    if(this.map.size > this.length) {
      this.map.delete(this.map.keys().next().value)
    }
  }

  //  get data 
  get(key) {
    if(!this.map.has(key)) {
      return null
    }

    const val = this.map.get(key)  //  Get elements 
    this.map.delete(key)  //  Remove elements 
    this.map.set(key, val) //  Reinsert elements , Update storage order 
  }
}

const lruCache = new LRUCache(3)

lruCache.set('name', 'wft')
lruCache.set('age', 18)
lruCache.set('sex', ' male ')
lruCache.set('len', ' Out of length ')

console.log(lruCache, '----->>>')

ts 

interface ILRUCache {
  length: number
  map: Map<unknown, unknown>
  set(key: unknown, value: unknown): void
  get(key: unknown): void
}


class LRUCache implements ILRUCache {
  length: number
  map: Map<unknown, unknown>

  constructor(length: number) {
    this.length = length
    this.map = new Map()
  }

  set(key: unknown, value: unknown) {
    if(this.map.has(key)) {
      this.map.delete(key)
    }
    this.map.set(key, value)

    if(this.map.size > this.length) {
      this.map.delete(this.map.keys().next().value)
    }
  }

  get(key: unknown) {
    if(!this.map.has(key)) {
      return null
    }

    const val = this.map.get(key)
    this.map.delete(key)
    this.map.set(key, val)
  }
}

const lruCache = new LRUCache(3)

lruCache.set('name', 'wft')
lruCache.set('age', 18)
lruCache.set('sex', ' male ')
lruCache.set('len', ' Out of length ')

console.log(lruCache, '----->>>')

Learn from ：https://juejin.cn/post/7105654083347808263