1. 云图网首页
  2. 技术专区
  3. 编程笔记

LRU算法详解编程语言

• 编程笔记

LRU

目的：创建了一个哈希表作为缓存，每次查找一个用户的时候先在哈希表中查询，以此提高访问性能

LRU 全称 Least Recently Used,也就 是最近最少使用的意思，是一种内存菅理算法，最早应用于Linux操作系统

LRU算法基于一种假设：长期不被使用的数据，在未来被用到的几率也不大。

因此.当数据所占内存达到一定阈值吋, 我们要移除掉最近最少被使用的数据。

代码：

import java.io.*; 
import java.util.*; 
class test   
{ 
public static void main (String[] args) throws java.lang.Exception 
{ 
LRUCache lruCache = new LRUCache(5); 
lruCache.put("001", "用户1信息"); 
lruCache.put("002", "用户2信息"); 
lruCache.put("003", "用户3信息"); 
lruCache.put("004", "用户4信息"); 
lruCache.put("005", "用户5信息"); 
System.out.println("原始序列 : "); 
lruCache.viewAllNode();//原始序列 
         
lruCache.get("002");//更新002之后,002位置提前了 
         
System.out.println("更新002之后 : "); 
lruCache.viewAllNode(); 
lruCache.put("004", "用户4信息更新");//更新004之后,004位置提前了 
System.out.println("更新004之后 : "); 
lruCache.viewAllNode(); 
System.out.println("插入006之后 : "); 
lruCache.put("006", "用户6信息");//插入新的值,001被挤掉了 
        lruCache.viewAllNode(); 
} 
} 
class LRUCache{ 
private Node head; 
private Node end; 
//缓存存储上限 
private int limit; 
private HashMap<String, Node> hashMap; 
public LRUCache(int limit) { 
this.limit = limit; 
hashMap = new HashMap<String, Node>(); 
} 
public String getFirstNode(){ 
if(head != null){ 
return head.value; 
}else{ 
return null; 
} 
} 
public String getEndNode(){ 
if(end != null){ 
return end.value; 
}else{ 
return null; 
} 
} 
public void viewAllNode(){ 
if(head != null){ 
System.out.print(head.value); 
Node temp = head.next; 
while(temp != null){ 
System.out.print(" - " + temp.value); 
temp = temp.next; 
} 
System.out.println(""); 
} 
} 
public String get(String key) { 
Node node = hashMap.get(key); 
if (node == null){ 
return null; 
} 
refreshNode(node); 
return node.value; 
} 
public void put(String key, String value) { 
Node node = hashMap.get(key); 
if (node == null) { 
//如果key不存在，插入key-value 
if (hashMap.size() >= limit) { 
String oldKey = removeNode(head); 
hashMap.remove(oldKey); 
} 
node = new Node(key, value); 
addNode(node); 
hashMap.put(key, node); 
}else { 
//如果key存在，刷新key-value 
node.value = value; 
refreshNode(node); 
} 
} 
public void remove(String key) { 
Node node = hashMap.get(key); 
removeNode(node); 
hashMap.remove(key); 
} 
/**  
* 刷新被访问的节点位置  
* @param  node 被访问的节点  
*/ 
private void refreshNode(Node node) { 
//如果访问的是尾节点，无需移动节点 
if (node == end) { 
return; 
} 
//移除节点 
        removeNode(node); 
//重新插入节点 
        addNode(node); 
} 
/** 
* 删除节点  
* @param  node 要删除的节点  
*/ 
private String removeNode(Node node) { 
if (node == end) { 
//移除尾节点 
end = end.pre; 
}else if(node == head){ 
//移除头节点 
head = head.next; 
} else { 
//移除中间节点 
node.pre.next = node.next; 
node.next.pre = node.pre; 
} 
return node.key; 
} 
/** 
* 尾部插入节点 
* @param  node 要插入的节点  
*/ 
private void addNode(Node node) { 
if(end != null) { 
end.next = node; 
node.pre = end; 
node.next = null; 
} 
end = node; 
if(head == null){ 
head = node; 
} 
} 
} 
class Node { 
Node(String key, String value){ 
this.key = key; 
this.value = value; 
} 
public Node pre; 
public Node next; 
public String key; 
public String value; 
}

下面加上 synchronized 解决进程安全问题

import java.io.*; 
import java.util.*; 
class test   
{ 
public static void main (String[] args) throws java.lang.Exception 
{ 
LRUCache lruCache = new LRUCache(5); 
lruCache.put("001", "用户1信息"); 
lruCache.put("002", "用户2信息"); 
lruCache.put("003", "用户3信息"); 
lruCache.put("004", "用户4信息"); 
lruCache.put("005", "用户5信息"); 
System.out.println("原始序列 : "); 
lruCache.viewAllNode();//原始序列 
         
lruCache.get("002");//更新002之后,002位置提前了 
         
System.out.println("更新002之后 : "); 
lruCache.viewAllNode(); 
lruCache.put("004", "用户4信息更新");//更新004之后,004位置提前了 
System.out.println("更新004之后 : "); 
lruCache.viewAllNode(); 
System.out.println("插入006之后 : "); 
lruCache.put("006", "用户6信息");//插入新的值,001被挤掉了 
        lruCache.viewAllNode(); 
} 
} 
class LRUCache{ 
private Node head; 
private Node end; 
//缓存存储上限 
private int limit; 
private HashMap<String, Node> hashMap; 
public LRUCache(int limit) { 
this.limit = limit; 
hashMap = new HashMap<String, Node>(); 
} 
public String getFirstNode(){ 
if(head != null){ 
return head.value; 
}else{ 
return null; 
} 
} 
public String getEndNode(){ 
if(end != null){ 
return end.value; 
}else{ 
return null; 
} 
} 
public void viewAllNode(){ 
if(head != null){ 
System.out.print(head.value); 
Node temp = head.next; 
while(temp != null){ 
System.out.print(" - " + temp.value); 
temp = temp.next; 
} 
System.out.println(""); 
} 
} 
public synchronized String get(String key) { 
try { 
Node node = hashMap.get(key); 
if (node == null){ 
return null; 
} 
refreshNode(node); 
return node.value; 
} catch (Exception e) { 
e.printStackTrace(); 
} 
return ""; 
} 
public synchronized void put(String key, String value) { 
try { 
Node node = hashMap.get(key); 
if (node == null) { 
//如果key不存在，插入key-value 
if (hashMap.size() >= limit) { 
String oldKey = removeNode(head); 
hashMap.remove(oldKey); 
} 
node = new Node(key, value); 
addNode(node); 
hashMap.put(key, node); 
}else { 
//如果key存在，刷新key-value 
node.value = value; 
refreshNode(node); 
} 
} catch (Exception e) { 
e.printStackTrace(); 
} 
} 
public void remove(String key) { 
Node node = hashMap.get(key); 
removeNode(node); 
hashMap.remove(key); 
} 
/**  
* 刷新被访问的节点位置  
* @param  node 被访问的节点  
*/ 
private void refreshNode(Node node) { 
//如果访问的是尾节点，无需移动节点 
if (node == end) { 
return; 
} 
//移除节点 
        removeNode(node); 
//重新插入节点 
        addNode(node); 
} 
/** 
* 删除节点  
* @param  node 要删除的节点  
*/ 
private String removeNode(Node node) { 
if (node == end) { 
//移除尾节点 
end = end.pre; 
}else if(node == head){ 
//移除头节点 
head = head.next; 
} else { 
//移除中间节点 
node.pre.next = node.next; 
node.next.pre = node.pre; 
} 
return node.key; 
} 
/** 
* 尾部插入节点 
* @param  node 要插入的节点  
*/ 
private void addNode(Node node) { 
if(end != null) { 
end.next = node; 
node.pre = end; 
node.next = null; 
} 
end = node; 
if(head == null){ 
head = node; 
} 
} 
} 
class Node { 
Node(String key, String value){ 
this.key = key; 
this.value = value; 
} 
public Node pre; 
public Node next; 
public String key; 
public String value; 
}

输出：

原始序列 :  
用户1信息 - 用户2信息 - 用户3信息 - 用户4信息 - 用户5信息 
更新002之后 :  
用户1信息 - 用户3信息 - 用户4信息 - 用户5信息 - 用户2信息 
更新004之后 :  
用户1信息 - 用户3信息 - 用户5信息 - 用户2信息 - 用户4信息更新 
插入006之后 :  
用户3信息 - 用户5信息 - 用户2信息 - 用户4信息更新 - 用户6信息

原创文章，作者：Maggie-Hunter，如若转载，请注明出处：https://blog.ytso.com/20729.html

赞 (0)
0
上一篇 2021年7月19日
下一篇 2021年7月19日

相关推荐

发表回复

登录后才能评论