本篇文章為大家展示了使用golang怎么實現(xiàn)一個LRU緩存淘汰算法，內(nèi)容簡明扼要并且容易理解，絕對能使你眼前一亮，通過這篇文章的詳細(xì)介紹希望你能有所收獲。

網(wǎng)站設(shè)計制作過程拒絕使用模板建站；使用PHP+MYSQL原生開發(fā)可交付網(wǎng)站源代碼;符合網(wǎng)站優(yōu)化排名的后臺管理系統(tǒng)；網(wǎng)站設(shè)計制作、做網(wǎng)站收費合理；免費進(jìn)行網(wǎng)站備案等企業(yè)網(wǎng)站建設(shè)一條龍服務(wù).我們是一家持續(xù)穩(wěn)定運(yùn)營了十余年的成都創(chuàng)新互聯(lián)網(wǎng)站建設(shè)公司。

LRU緩存淘汰算法

LRU是最近最少使用策略的縮寫，是根據(jù)數(shù)據(jù)的歷史訪問記錄來進(jìn)行淘汰數(shù)據(jù)，其核心思想是“如果數(shù)據(jù)最近被訪問過，那么將來被訪問的幾率也更高”。

雙向鏈表實現(xiàn)LRU

將Cache的所有位置都用雙鏈表連接起來，當(dāng)一個位置被訪問(get/put)之后，通過調(diào)整鏈表的指向，將該位置調(diào)整到鏈表頭的位置，新加入的Cache直接加到鏈表頭中。

這樣，在多次操作后，最近被訪問(get/put)的，就會被向鏈表頭方向移動，而沒有訪問的，向鏈表后方移動，鏈表尾則表示最近最少使用的Cache。

當(dāng)達(dá)到緩存容量上限時，鏈表的最后位置就是最少被訪問的Cache，我們只需要刪除鏈表最后的Cache便可繼續(xù)添加新的Cache。

代碼實現(xiàn)

type Node struct {
  Key int
  Value int
  pre *Node
  next *Node
}

type LRUCache struct {
  limit int
  HashMap map[int]*Node
  head *Node
  end *Node
}

func Constructor(capacity int) LRUCache{
  lruCache := LRUCache{limit:capacity}
  lruCache.HashMap = make(map[int]*Node, capacity)
  return lruCache
}

func (l *LRUCache) Get(key int) int {
  if v,ok:= l.HashMap[key];ok {
    l.refreshNode(v)
    return v.Value
  }else {
    return -1
  }
}

func (l *LRUCache) Put(key int, value int) {
  if v,ok := l.HashMap[key];!ok{
    if len(l.HashMap) >= l.limit{
      oldKey := l.removeNode(l.head)
      delete(l.HashMap, oldKey)
    }
    node := Node{Key:key, Value:value}
    l.addNode(&node)
    l.HashMap[key] = &node
  }else {
    v.Value = value
    l.refreshNode(v)
  }
}

func (l *LRUCache) refreshNode(node *Node){
  if node == l.end {
    return
  }
  l.removeNode(node)
  l.addNode(node)
}

func (l *LRUCache) removeNode(node *Node) int{
  if node == l.end {
    l.end = l.end.pre
  }else if node == l.head {
    l.head = l.head.next
  }else {
    node.pre.next = node.next
    node.next.pre = node.pre
  }
  return node.Key
}

func (l *LRUCache) addNode(node *Node){
  if l.end != nil {
    l.end.next = node
    node.pre = l.end
    node.next = nil
  }
  l.end = node
  if l.head == nil {
    l.head = node
  }
}

上述內(nèi)容就是使用golang怎么實現(xiàn)一個LRU緩存淘汰算法，你們學(xué)到知識或技能了嗎？如果還想學(xué)到更多技能或者豐富自己的知識儲備，歡迎關(guān)注創(chuàng)新互聯(lián)行業(yè)資訊頻道。

網(wǎng)頁名稱：使用golang怎么實現(xiàn)一個LRU緩存淘汰算法
網(wǎng)頁鏈接：http://aaarwkj.com/article24/gjjoce.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供標(biāo)簽優(yōu)化、App設(shè)計、網(wǎng)站排名、網(wǎng)頁設(shè)計公司、軟件開發(fā)、搜索引擎優(yōu)化

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時需注明來源： 創(chuàng)新互聯(lián)