LRU算法的应用
13.LRU算法的应用题目
关于用户信息的需求
假定在一个复杂的体系中，必要抽象出一个用户体系，提供给其他子体系使用，该怎样实现。子体系对用户信息的查询频率很高，要留意性能题目。
用户信息是存储在数据库里的，但是对于查询频率高的数据，不能每一次哀求时都去查询数据库。
思绪
哈希表
使用以用户id为key，用户信息为value的哈希表，作为缓存以提高性能。存在题目，如果只向哈希表中存储数据，而不移除数据的话，可能内存会溢出，导致服务器宕机。
LRU全称Least Recently Used，最近最少未使用，是一种内存管理算法，该算法最早应用于LinuxOS。
该算法，基于一种假设：长期不使用的数据，在未来使用的概率也不大。因此，当内存数据占内存达到肯定阈值时，要移除最近最少使用的数据。
该算法，还基于一种，特殊的数据结构，哈希链表。
哈希表是由若干个K-V键值对的Node节点构成的。在此逻辑基础上，每个节点，加一个pre前驱和一个next后驱，将这些Node连接起来，想链表一样。
假设，使用哈希链表存储用户信息，001-User1002-User2003-User3004-User4。每次，对于未缓存的用户数据，都使用尾加法，加到链表的右边，对于使用到的链表中的数据，也将该节点移动到链表的末尾。这样链表的左侧，就是最近最少未使用的数据，移除就好。
代码
public 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<>();
}
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) {
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);
refreshNode(node);
hashMap.remove(key);
}
/**
* 刷新被访问节点的位置
*
* @param node 被访问节点
*/
private void refreshNode(Node node) {
if (node == end)
return;
//移除节点
removeNode(node);
//重新插入节点
addNode(node);
}
/**
* 删除节点
*
* @param node 要删除的节点
* @return
*/
private String removeNode(Node node) {
if (node == head && node == end) {
//移除唯一节点
head = null;
end = null;
} else if (node == end) {
//移除尾结点
end = end.pre;
end.next = null;
} else if (node == head) {
//移除头节点
head = head.next;
head.pre = null;
} else {
//移除中间节点
node.pre.next = node.next;//将当前节点的下一个，赋值给上一节点的下一个
node.next.pre = node.pre;//将当前节点的前一个，赋值给上一节点的前一个
}
return node.key;
}
private void addNode(Node node) {
if (end != null) {
end.next = node;
node.pre = end;
node.next = null;
}
end = node;
if (head == null)
head = node;
}
private static 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;
}
public static void main(String[] args) {
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信息");
lruCache.get("002");
lruCache.put("004","new用户4信息");
lruCache.put("006","用户6信息");
System.out.println(lruCache.get("001"));
System.out.println(lruCache.get("006"));
}
}留意，该代码本质照旧使用HashMap作为缓存，且如果多个线程共享一个LRUCache对象时，访问这些方法，是线程不安全的。这是可以给这些方法手动加锁，大概使用ConcurrentHashMap类占存数据。本demo中的，存储的用户使用String范例表现，只是为了演示LRU算法，实际使用中，可以使用泛型。
对于这种缓存高频访问的数据，一般都是用Redis这种NoSQL的内存数据库，其底层也实现了类似LRU的回收算法。该笔记只是展示LRU算法。而且使用缓存数据库，就肯定存在一个数据同等性的题目，就是关系型数据库中存储的数据和缓存中的数据怎样保持同等？后续有机会分享。
只是为了记录本身的学习历程，且本人水平有限，不对之处，请指正。
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]