词条信息

admin
admin
超级管理员
词条创建者 发短消息   

相关词条

热门词条

更多>>
乐播投屏和快点投屏,到底哪款好?
对于投屏软件哪款好这个问题,每个人有各自的想法和中意的软件,今天当贝市场小编要对比乐播投屏和快点投屏两款软件,...
黑客初级攻击方法-缓冲区溢出攻击
1.C++程序运行时栈分析网上关于C++程序运行时的栈解析文章有很多,在这里简单介绍一下,方便后续操作的理解与...
学好机器学习和大数据必备的6本好书!
机器学习和数据科学是复杂而相互关联的概念。要想让自己在技术紧跟趋势,你必须消耗大量的时间进行知识的更新。日复一...
3分钟看懂英国简史
说起来,大部分人都知道英国的全名是“大不列颠及北爱尔兰联合王国”。但遗憾的是,只有少部分人知道这个名字的来龙去...
华为手机怎么投屏到电视?
一直看到有很多人在问:华为手机怎么投屏到电视上,才更简单又快速?虽然像最新发布的华为Mate X、Mate 2...
解决网 >>所属分类 >> 程序开发    算法   

什么是LRU算法(漫画)?

标签: LRU算法 算法

顶[0] 发表评论(0) 编辑词条

本文转自公众号程序员小灰,本期封面作者:A17


————— 两个月前 —————


用户信息当然是存在数据库里。但是由于我们对用户系统的性能要求比较高,显然不能每一次请求都去查询数据库。

所以,小灰在内存中创建了一个哈希表作为缓存,每次查找一个用户的时候先在哈希表中查询,以此提高访问性能。


很快,用户系统上线了,小灰美美地休息了几天。

一个多月之后......

———————————————


什么是哈希链表呢?

我们都知道,哈希表是由若干个Key-Value所组成。在“逻辑”上,这些Key-Value是无所谓排列顺序的,谁先谁后都一样。



在哈希链表当中,这些Key-Value不再是彼此无关的存在,而是被一个链条串了起来。每一个Key-Value都具有它的前驱Key-Value、后继Key-Value,就像双向链表中的节点一样。



这样一来,原本无序的哈希表拥有了固定的排列顺序。



让我们以用户信息的需求为例,来演示一下LRU算法的基本思路:

1.假设我们使用哈希链表来缓存用户信息,目前缓存了4个用户,这4个用户是按照时间顺序依次从链表右端插入的。


2.此时,业务方访问用户5,由于哈希链表中没有用户5的数据,我们从数据库中读取出来,插入到缓存当中。这时候,链表中最右端是最新访问到的用户5,最左端是最近最少访问的用户1。


3.接下来,业务方访问用户2,哈希链表中存在用户2的数据,我们怎么做呢?我们把用户2从它的前驱节点和后继节点之间移除,重新插入到链表最右端。这时候,链表中最右端变成了最新访问到的用户2,最左端仍然是最近最少访问的用户1。


4.接下来,业务方请求修改用户4的信息。同样道理,我们把用户4从原来的位置移动到链表最右侧,并把用户信息的值更新。这时候,链表中最右端是最新访问到的用户4,最左端仍然是最近最少访问的用户1。

5.后来业务方换口味了,访问用户6,用户6在缓存里没有,需要插入到哈希链表。假设这时候缓存容量已经达到上限,必须先删除最近最少访问的数据,那么位于哈希链表最左端的用户1就会被删除掉,然后再把用户6插入到最右端。


以上,就是LRU算法的基本思路。


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

需要注意的是,这段不是线程安全的,要想做到线程安全,需要加上synchronized修饰符。


 

 

附件列表


按字母顺序浏览:A B C D E F G H I J K L M N O P Q R S T U V W X Y Z

→我们致力于为广大网民解决所遇到的各种电脑技术问题
 如果您认为本词条还有待完善,请 编辑词条

上一篇nginx如何配置websocket支持wss
下一篇nginx配置下载目录

0
1. 本站部分内容来自互联网,如有任何版权侵犯或其他问题请与我们联系,我们将立即删除或处理。
2. 本站内容仅供参考,如果您需要解决具体问题,建议您咨询相关领域专业人士。
3. 如果您没有找到需要的百科词条,您可以到百科问答提问或创建词条,等待高手解答。

关于本词条的提问

查看全部/我要提问>>