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

簡(jiǎn)單了解 LRU 是什么

提到 LRU，很多人第一反應(yīng)會(huì)想到 Redis 的淘汰策略，沒(méi)錯(cuò)，這里的 LRU 和 Redis 使用的 LRU 是相同的概念。

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

當(dāng)緩存容量未滿(mǎn)時(shí)，加入元素則加入到隊(duì)尾，有元素訪(fǎng)問(wèn)時(shí)，則被訪(fǎng)問(wèn)的元素移動(dòng)到隊(duì)尾，所以在這個(gè)例子中，我們可以認(rèn)為在隊(duì)尾的為最近使用的元素，相反在隊(duì)首的則為最近最久未使用的元素。所以在元素 E 加入后，緩存容量達(dá)到最大，此時(shí)最近最久未使用的元素為 A，如果再有元素加入時(shí)會(huì)淘汰掉 A，但是接下來(lái)的操作為訪(fǎng)問(wèn) A 元素，所以此時(shí) A 被移動(dòng)到隊(duì)尾，在隊(duì)首的元素成為了 C，那么接下在 F 元素加入后，C元素被淘汰。

LRU 機(jī)制實(shí)現(xiàn)分析

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

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

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

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

所以我們?cè)趯?duì)這個(gè)問(wèn)題思考的時(shí)候，不要對(duì)時(shí)間這個(gè)概念太過(guò)于注重，因?yàn)槲覀儾⒉恍枰烂總€(gè)元素的具體時(shí)間，而是只需要知道元素之間的先后時(shí)間順序即可。所以這里我們只需要維護(hù)每個(gè)元素的先后順序。那么這里有人就會(huì)考慮到使用數(shù)組或者鏈表，這兩者都是有順序的。但是對(duì)于數(shù)組來(lái)講，數(shù)組中的元素移動(dòng)并不是 O(1) 的操作，所以可能鏈表會(huì)更加適合。但是如果使用鏈表實(shí)現(xiàn)的話(huà)，要訪(fǎng)問(wèn)緩存中的元素就需要去遍歷鏈表來(lái)找到這個(gè)元素。

我們?cè)偈崂硐逻@個(gè)問(wèn)題實(shí)現(xiàn)的要點(diǎn)：

• Set 和 Get 滿(mǎn)足 O(1) 時(shí)間復(fù)雜度
• 元素順序調(diào)整滿(mǎn)足 O(1) 時(shí)間復(fù)雜度

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

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

題目描述

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

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

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

詳細(xì)代碼

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
	// 通過(guò)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語(yǔ)言實(shí)現(xiàn)LRU緩存的示例代碼的文章就介紹到這了,更多相關(guān)go語(yǔ)言 LRU緩存內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評(píng)論