LRU算法的应用

13.LRU算法的应用

题目

关于用户信息的需求
假定在一个复杂的体系中，必要抽象出一个用户体系，提供给其他子体系使用，该怎样实现。子体系对用户信息的查询频率很高，要留意性能题目。
用户信息是存储在数据库里的，但是对于查询频率高的数据，不能每一次哀求时都去查询数据库。
思绪

哈希表

使用以用户id为key，用户信息为value的哈希表，作为缓存以提高性能。存在题目，如果只向哈希表中存储数据，而不移除数据的话，可能内存会溢出，导致服务器宕机。
LRU全称Least Recently Used，最近最少未使用，是一种内存管理算法，该算法最早应用于LinuxOS。
该算法，基于一种假设：长期不使用的数据，在未来使用的概率也不大。因此，当内存数据占内存达到肯定阈值时，要移除最近最少使用的数据。
该算法，还基于一种，特殊的数据结构，哈希链表。
哈希表是由若干个K-V键值对的Node节点构成的。在此逻辑基础上，每个节点，加一个pre前驱和一个next后驱，将这些Node连接起来，想链表一样。
假设，使用哈希链表存储用户信息，001-User1002-User2003-User3004-User4。每次，对于未缓存的用户数据，都使用尾加法，加到链表的右边，对于使用到的链表中的数据，也将该节点移动到链表的末尾。这样链表的左侧，就是最近最少未使用的数据，移除就好。
代码

1. public class LRUCache {
2.     private Node head;
3.     private Node end;
4.     private int limit;
7.     private HashMap<String, Node> hashMap;
9.     public LRUCache(int limit) {
10.         this.limit = limit;
11.         hashMap = new HashMap<>();
12.     }
14.     public String get(String key) {
15.         Node node = hashMap.get(key);
16.         if (node == null)
17.             return null;
18.         refreshNode(node);
19.         return node.value;
20.     }
22.     public void put(String key, String value) {
23.         Node node = hashMap.get(key);
24.         if (node == null) {
25.             if (hashMap.size() >= limit) {
26.                 String oldKey = removeNode(head);
27.                 hashMap.remove(oldKey);
28.             }
29.             node = new Node(key, value);
30.             addNode(node);
31.             hashMap.put(key, node);
32.         } else {
33.             //如果key存在，则刷新key-value
34.             node.value = value;
35.             refreshNode(node);
36.         }
37.     }
39.     public void remove(String key){
40.         Node node = hashMap.get(key);
41.         refreshNode(node);
42.         hashMap.remove(key);
43.     }
45.     /**
46.      * 刷新被访问节点的位置
47.      *
48.      * @param node 被访问节点
49.      */
50.     private void refreshNode(Node node) {
51.         if (node == end)
52.             return;
53.         //移除节点
54.         removeNode(node);
55.         //重新插入节点
56.         addNode(node);
57.     }
59.     /**
60.      * 删除节点
61.      *
62.      * @param node 要删除的节点
63.      * @return
64.      */
65.     private String removeNode(Node node) {
66.         if (node == head && node == end) {
67.             //移除唯一节点
68.             head = null;
69.             end = null;
70.         } else if (node == end) {
71.             //移除尾结点
72.             end = end.pre;
73.             end.next = null;
74.         } else if (node == head) {
75.             //移除头节点
76.             head = head.next;
77.             head.pre = null;
78.         } else {
79.             //移除中间节点
80.             node.pre.next = node.next;//将当前节点的下一个，赋值给上一节点的下一个
81.             node.next.pre = node.pre;//将当前节点的前一个，赋值给上一节点的前一个
82.         }
83.         return node.key;
84.     }
86.     private void addNode(Node node) {
87.         if (end != null) {
88.             end.next = node;
89.             node.pre = end;
90.             node.next = null;
91.         }
92.         end = node;
93.         if (head == null)
94.             head = node;
95.     }
97.     private static class Node {
98.         Node(String key, String value) {
99.             this.key = key;
100.             this.value = value;
101.         }
103.         public Node pre;
104.         public Node next;
105.         public String key;
106.         public String value;
107.     }
109.     public static void main(String[] args) {
110.         LRUCache lruCache = new LRUCache(5);
111.         lruCache.put("001","用户1信息");
112.         lruCache.put("002","用户2信息");
113.         lruCache.put("003","用户3信息");
114.         lruCache.put("004","用户4信息");
115.         lruCache.put("005","用户5信息");
116.         lruCache.get("002");
117.         lruCache.put("004","new用户4信息");
118.         lruCache.put("006","用户6信息");
119.         System.out.println(lruCache.get("001"));
120.         System.out.println(lruCache.get("006"));
121.     }
123. }

复制代码

留意，该代码本质照旧使用HashMap作为缓存，且如果多个线程共享一个LRUCache对象时，访问这些方法，是线程不安全的。这是可以给这些方法手动加锁，大概使用ConcurrentHashMap类占存数据。本demo中的，存储的用户使用String范例表现，只是为了演示LRU算法，实际使用中，可以使用泛型。
对于这种缓存高频访问的数据，一般都是用Redis这种NoSQL的内存数据库，其底层也实现了类似LRU的回收算法。该笔记只是展示LRU算法。而且使用缓存数据库，就肯定存在一个数据同等性的题目，就是关系型数据库中存储的数据和缓存中的数据怎样保持同等？后续有机会分享。
只是为了记录本身的学习历程，且本人水平有限，不对之处，请指正。

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。