緩存是在平時開發(fā)中最常用的中間件之一，尤其是在 WEB 開發(fā)中更為常見，大家最常用的肯定還是 Redis 或者 Memcached 之類的中間件。所以對于自己實現(xiàn)一個 Cache 可能并沒有那么熟悉，但是在很多場景下，我們使用一些網(wǎng)絡緩存會遇到一些瓶頸，比如說傳輸數(shù)據(jù)量比較大，或者傳輸非常頻繁，都可能會導致一些性能瓶頸，尤其是在網(wǎng)絡I/O上。所以這種場景下，很可能就需要我們自己在應用內(nèi)實現(xiàn)一個二級緩存。本文我們就來介紹下一個基于 Go 語言支持 LRU 淘汰策略緩存的實現(xiàn)思路。

簡單了解 LRU 是什么

提到 LRU，很多人第一反應會想到 Redis 的淘汰策略，沒錯，這里的 LRU 和 Redis 使用的 LRU 是相同的概念。

LRU（Least Recently Used）表示的是最近最久未使用，或者也有稱為最近最少使用，但是為了避免和 LFU 產(chǎn)生歧義，本文中我們都成為最近最久未使用。下面我們通過一個示例來快速描述下 LRU 的概念（如果已經(jīng)對 LRU 的概念了解，可以跳過這部分）：

當緩存容量未滿時，加入元素則加入到隊尾，有元素訪問時，則被訪問的元素移動到隊尾，所以在這個例子中，我們可以認為在隊尾的為最近使用的元素，相反在隊首的則為最近最久未使用的元素。所以在元素 E 加入后，緩存容量達到最大，此時最近最久未使用的元素為 A，如果再有元素加入時會淘汰掉 A，但是接下來的操作為訪問 A 元素，所以此時 A 被移動到隊尾，在隊首的元素成為了 C，那么接下在 F 元素加入后，C元素被淘汰。

LRU 機制實現(xiàn)分析

在了解 LRU 的概念之后，我們回到主題，就是實現(xiàn)一個 LRU 的緩存。這里我們以開始提到的面試為例：

實現(xiàn)基于內(nèi)存的滿足 LRU 淘汰機制的緩存，并且提供 Set 和 Get 方法

首先我們分析下這個題目，要滿足 LRU 的淘汰機制，則緩存一定是限定容量的。其次就是要對性能的分析，既然是作為緩存使用的，那么對于 Set 和 Get 的操作的時間復雜度要求一定要控制在 O(1) 級別。（這里提一個其他問題，我們在解一個問題的時候，一定優(yōu)先考慮的是最優(yōu)的實現(xiàn)方式，而不是你認為的最簡單的實現(xiàn)方式，這里如果我們使用 O(n) 甚至 O(n^2) 的解法也可以實現(xiàn)，但是這樣既不滿足實際的使用場景，更不滿足面試對你的考核要求）

再回到這個問題，從最開始我們分析的例子中可以看出，在 LRU 的實現(xiàn)中最重要的一點就是要管理緩存中每個元素的時間屬性，所以有人就會考慮，給每個元素記錄一個時間戳，然后將元素和時間戳信息存入到一個哈希表中，但是這樣雖然滿足了 O(1) 的元素訪問時間復雜度，但是在元素淘汰的時候就需要遍歷所有元素來找到最早的那個元素。

所以我們在對這個問題思考的時候，不要對時間這個概念太過于注重，因為我們并不需要知道每個元素的具體時間，而是只需要知道元素之間的先后時間順序即可。所以這里我們只需要維護每個元素的先后順序。那么這里有人就會考慮到使用數(shù)組或者鏈表，這兩者都是有順序的。但是對于數(shù)組來講，數(shù)組中的元素移動并不是 O(1) 的操作，所以可能鏈表會更加適合。但是如果使用鏈表實現(xiàn)的話，要訪問緩存中的元素就需要去遍歷鏈表來找到這個元素。

我們再梳理下這個問題實現(xiàn)的要點：

• Set 和 Get 滿足 O(1) 時間復雜度
• 元素順序調(diào)整滿足 O(1) 時間復雜度

對于要點1，我們可以使用哈希表來實現(xiàn)，對于要點2，我們可以使用鏈表來實現(xiàn)。這兩種結(jié)構(gòu)都沒有辦法同時滿足兩個點。所以我們就需要考慮把這兩種數(shù)據(jù)結(jié)構(gòu)結(jié)合起來考慮。（如果有對于Java了解的同學，可以參考LinkedHashMap），這種結(jié)構(gòu)細節(jié)可以參考下圖：

首先創(chuàng)建一個哈希表用了存儲鍵值對，然后將哈希表的 Value 進行鏈表的關(guān)聯(lián)，這樣就可以同時滿足上述條件了，而這也是 LRU 的最普遍的實現(xiàn)方式。

題目描述

設(shè)計和構(gòu)建一個“最近最少使用”緩存，該緩存會刪除最近最少使用的項目。緩存應該從鍵映射到值(允許你插入和檢索特定鍵對應的值)，并在初始化時指定最大容量。當緩存被填滿時，它應該刪除最近最少使用的項目。

它應該支持以下操作： 獲取數(shù)據(jù) get 和 寫入數(shù)據(jù) put 。

獲取數(shù)據(jù) get(key) - 如果密鑰 (key) 存在于緩存中，則獲取密鑰的值（總是正數(shù)），否則返回 -1。
寫入數(shù)據(jù) put(key, value) - 如果密鑰不存在，則寫入其數(shù)據(jù)值。當緩存容量達到上限時，它應該在寫入新數(shù)據(jù)之前刪除最近最少使用的數(shù)據(jù)值，從而為新的數(shù)據(jù)值留出空間。

詳細代碼

type LRUCache struct {
	capacity   int
	m          map[int]*Node
	head, tail *Node
}

type Node struct {
	Key       int
	Value     int
	Pre, Next *Node
}

func Constructor(capacity int) LRUCache {
	head, tail := &Node{}, &Node{}
	head.Next = tail
	tail.Pre = head
	return LRUCache{
		capacity: capacity,
		m:        map[int]*Node{},
		head:     head,
		tail:     tail,
	}
}

func (this *LRUCache) Get(key int) int {
	// 存在，放到頭
	if v, ok := this.m[key]; ok {
		this.moveToHead(v)
		return v.Value
	}
	// 不存在，返回-1
	return -1
}

func (this *LRUCache) Put(key int, value int) {
	// 已經(jīng)存在了
	if v, ok := this.m[key];ok{
		v.Value = value
		this.moveToHead(v)
		return 
	}
	if this.capacity==len(this.m){
		rmKey := this.removeTail()
		delete(this.m ,rmKey)
	}
	newNode := &Node{Key: key, Value: value}
	this.m[key] = newNode
	this.addToHead(newNode)
}

func (this *LRUCache) moveToHead(node *Node) {
	this.deleteNode(node)
	this.addToHead(node)
}

func (this *LRUCache) deleteNode(node *Node) {
	node.Pre.Next = node.Next
	node.Next.Pre = node.Pre
}

func (this *LRUCache) addToHead(node *Node) {
	// 先讓node位于現(xiàn)存第一位元素之前
	this.head.Next.Pre = node
	// 通過node的next指針讓原始第一位元素放到第二位
	node.Next = this.head.Next
	// 捆綁node和head的關(guān)系
	this.head.Next = node
	node.Pre = this.head
}

func (this *LRUCache)removeTail()int{
	node := this.tail.Pre
    this.deleteNode(node)
    return node.Key
}

/**
 * Your LRUCache object will be instantiated and called as such:
 * obj := Constructor(capacity);
 * param_1 := obj.Get(key);
 * obj.Put(key,value);
 */

到此這篇關(guān)于go語言實現(xiàn)LRU緩存的示例代碼的文章就介紹到這了,更多相關(guān)go語言 LRU緩存內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評論