LRU緩存淘汰算法
LRU是最近最少使用策略的縮寫，是根據數據的歷史訪問記錄來進行淘汰數據，其核心思想是“如果數據最近被訪問過，那么將來被訪問的幾率也更高”。
雙向鏈表實現LRU
將Cache的所有位置都用雙鏈表連接起來，當一個位置被訪問(get/put)之后，通過調整鏈表的指向，將該位置調整到鏈表頭的位置，新加入的Cache直接加到鏈表頭中。
這樣，在多次操作后，最近被訪問(get/put)的，就會被向鏈表頭方向移動，而沒有訪問的，向鏈表后方移動，鏈表尾則表示最近最少使用的Cache。
當達到緩存容量上限時，鏈表的最后位置就是最少被訪問的Cache，我們只需要刪除鏈表最后的Cache便可繼續添加新的Cache。
代碼實現
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 }}以上就是本文的全部內容，希望對大家的學習有所幫助，也希望大家多多支持VEVB武林網。
新聞熱點
疑難解答
