Java之理解Redis回收算法LRU案例講解

更新時間：2021年08月09日 11:03:59 作者：mind_programmonkey

這篇文章主要介紹了Java之理解Redis回收算法LRU案例講解,本篇文章通過簡要的案例,講解了該項技術的了解與使用,以下就是詳細內容,需要的朋友可以參考下

如何通俗易懂的理解LRU算法？

1.LRU是什么？

LRU全稱Least Recently Used，也就是最近最少使用的意思，是一種內存管理算法，最早應用于Linux操作系統(tǒng)。

LRU算法基于一種假設：長期不被使用的數據，在未來被用到的幾率也不大。因此，當數據所占內存達到一定閾值時，我們要移除掉最近最少被使用的數據。

LRU算法應用：可以在內存不夠時，從哈希表移除一部分很少訪問的用戶。

LRU是什么？按照英文的直接原義就是Least Recently Used,最近最久未使用法，它是按照一個非常著名的計算機操作系統(tǒng)基礎理論得來的：最近使用的頁面數據會在未來一段時期內仍然被使用,已經很久沒有使用的頁面很有可能在未來較長的一段時間內仍然不會被使用。基于這個思想,會存在一種緩存淘汰機制，每次從內存中找到最久未使用的數據然后置換出來，從而存入新的數據！它的主要衡量指標是使用的時間，附加指標是使用的次數。在計算機中大量使用了這個機制，它的合理性在于優(yōu)先篩選熱點數據，所謂熱點數據，就是最近最多使用的數據！因為，利用LRU我們可以解決很多實際開發(fā)中的問題，并且很符合業(yè)務場景。

2.LRU的需求

首先考慮這樣的一個業(yè)務場景,小王在A公司上班，有一天產品提出了一個需求：“咱們系統(tǒng)的用戶啊，每天活躍的就那么多，有太多的僵尸用戶，根本不登錄，你能不能考慮做一個篩選機制把這些用戶刨出去，并且給活躍的用戶做一個排名，我們可以設計出一些獎勵活動，提升咱們的用戶粘性，咱們只需要關注那些活躍的用戶就行了“”。小王連忙點頭，說可以啊，然而心里犯起嘀咕來了：這簡單，按照常規(guī)思路，給用戶添加一個最近活躍時間長度和登錄次數，然后按照這兩個數據計算他們的活躍度，最后直接排序就行了。嘿嘿，簡直完美!不過！用戶表字段已經很多了，又要加兩個字段，然后還得遍歷所有的數據排序？這樣查詢效率是不是會受影響??？

3.LRU的實現方式

實現 LRUCache 類：

LRUCache(int capacity) 以正整數作為容量 capacity 初始化 LRU 緩存；
int get(int key) 如果關鍵字 key 存在于緩存中，則返回關鍵字的值，否則返回 -1 。
void put(int key, int value) 如果關鍵字已經存在，則變更其數據值；如果關鍵字不存在，則插入該組「關鍵字-值」。當緩存容量達到上限時，它應該在寫入新數據之前刪除最久未使用的數據值，從而為新的數據值留出空間。

3.1 直接繼承LinkedHashMap來實現

public class Code_LRU {
	class LRUCache extends LinkedHashMap<Integer,Integer>{
		private int capacity;
		public LRUCache(int capacity) {
			super(capacity,0.75F,true);
			this.capacity = capacity;
		}
		
		public int get(int key) {
			return super.getOrDefault(key,-1);
		}
		public void put(int key,int value) {
			super.put(key, value);
		}
		
		// 重寫淘汰策略
		protected boolean removeEldestEntry(Map.Entry<Integer, Integer> edlest) {
			return size()>capacity;
		}
	}
}

3.2 用雙向鏈表+hashMap來實現

// 解題思路：雙向鏈表+hashmap來實現
	class LRUCache_2{
		// 雙向鏈表
		class DLinkedNode{
			int key;
			int value;
			DLinkedNode prev;
			DLinkedNode next;
			public DLinkedNode() {
				
			}
			public DLinkedNode(int key,int value) {
				this.key = key;
				this.value = value;
			}
		}
		
		// hashmap
		private HashMap<Integer,DLinkedNode> cache = new HashMap<>();
		// 定義私有變量
		private int size;
		private int capacity;
		private DLinkedNode head,tail;
		
		public LRUCache_2(int capacity) {
			this.size = 0;
			this.capacity = capacity;
			// 生成偽頭部和偽尾部結點
			head = new DLinkedNode();
			tail = new DLinkedNode();
			head.next = tail;
			tail.prev = head;
		}
		
		//獲得值
		public int get(int key) {
			DLinkedNode node = cache.get(key);
			if(node==null) {
				return -1;
			}else {
				// 如果key存在，哈希表定位 結點移動到頭部
				moveToHead(node);
				return node.value;
			}
		}
		
		// 放入值的操作
		public void put(int key,int value) {
			DLinkedNode node = cache.get(key);
			// 如果key不存在
			if(node==null) {
				// 新創(chuàng)建一個結點
				DLinkedNode newNode = new DLinkedNode(key,value);
				// 添加
				cache.put(key,newNode);
				// 添加到頭部
				addToHead(newNode);
				++size;
				// 判斷容量
				if(size>capacity) {
					// 稱號出容量
					DLinkedNode tail = removeTail();
					// 刪除hash表中對應的項
					cache.remove(tail.key);
					--size;
				}
				
			}else {
				node.value = value;
				// 移動
				moveToHead(node);
			}
		}
		
		// 添加結點的操作
		private void addToHead(DLinkedNode node) {
			node.prev = head;
			node.next = head.next;
			head.next.prev = node;
			head.next = node;
		}
		
		// 刪除結點
		private void removeNode(DLinkedNode node) {
			node.prev.next = node.next;
			node.next.prev = node.prev;
		}
		
		// 移動到頭結點 刪結點 填充結點
		private void moveToHead(DLinkedNode node) {
			removeNode(node);
			addToHead(node);
		}
		// 刪除尾部結點
		private DLinkedNode removeTail() {
			DLinkedNode res = tail.prev;
			removeNode(res);
			return res;
		}
	}

到此這篇關于Java之理解Redis回收算法LRU案例講解的文章就介紹到這了,更多相關Java之理解Redis回收算法LRU內容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: