致我们单纯的小美好,漫画:什么是 LRU 算法?-优德88下载

admin 优德88手机客户端 2019-05-16 328 0

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

用户信息当然是存在数据库里。可是因为咱们对用户体系的功能要求比较高,明显不能每一次恳求都去查询数据库。

所以,小灰在内存中创建了一个哈希表作为缓存,每次查找一个用户的时分先在哈希表中查询,以此进步拜访功能。

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

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

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

什么是哈希链表呢?

咱们都知道,哈希表是由若干个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 hashMap;



  6. public LRUCache(int limit) {

  7. this.limit = limit;

  8. hashMap = new HashMap;

  9. }



  10. public String get(String key) {

  11. Node node = hashMap.get(key);

  12. if (node == ){

  13. return ;

  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 == ) {

  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 != ) {

  78. end.next = node;

  79. node.pre = end;

  80. node.next = ;

  81. }

  82. end = node;

  83. if(head == ){

  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修饰符。

通知我们一个好消息,小灰的《漫画算法》全面上架啦,在短短的两周里,本书一度霸占着各大热销榜第一!

扫码检查概况

小灰把两年多以来堆集的漫画作品进行了挑选和优化,并加上了一些更为根底和体系的入门章节,终究完成了本书的六大华章:

第一章 算法概述

介绍了算法和数据结构的相关概念,通知我们算法是什么,数据结构又是什么,它们有哪些用处,怎么剖析时刻复杂度,怎么剖析空间复杂度。

第二章 数据结构根底

介绍了最基本的数据结构,包含数组、链表、栈、行列、哈希表的概念和读写操作。

第三章 树

介绍了树和二叉树的概念、二叉树的各种遍历方法、二叉堆和优先行列的运用。

第四章 排序算法

介绍了几种典型的排序算法,包含冒泡排序、快速排序、堆排序、计数排序、桶排序。

第五章 面试中的算法

介绍了10余道职场上盛行的算法面试题及具体的解题思路。例如怎样判别链表有环、怎样核算大整数相加等。

第六章 算法的实践运用

介绍了算法在职场上的一些运用,例如运用LRU算法来筛选冷数据,运用Bitmap算法来计算用户特征等。

本书是全彩印制,书中的每一章、每一节、每一句话、每一幅图、每一行代码,都经过了小灰和修改们的精心打磨,力求用最为直白的方法把常识讲理解、讲透彻。

前期的漫画中存在一些叙说过错和表达不明晰的当地,小灰在本书中做了修正和弥补;一起书中增加了许多全新的华章,使得本书的内容愈加体系和全面。

关于巴望学习算法的小伙伴,不管你是正在学习核算机专业的学生,仍是现已进入职场的新人,亦或是具有多年工作经验却不拿手算法的内行,这本《漫画算法》都能协助你告别对算法的惊骇,知道算法、把握算法。

扫码购买

新品8折优惠中

版权声明

本文仅代表作者观点,不代表本站立场。
本文系作者授权发表,未经许可,不得转载。

优德88中文官网_优德888官方直营_优德888

  • 乐教乐学,江龙船艇8月14日快速上涨-优德88下载

    乐教乐学,江龙船艇8月14日快速上涨-优德88下载

  • 中小学教师资格考试网,组织正告:年末前英镑还要再跌9% 无协议脱欧概率高升-优德88下载

    中小学教师资格考试网,组织正告:年末前英镑还要再跌9% 无协议脱欧概率高升-优德88下载

  • 优德88客服电话_优德88手机中文版下载_w88官方网站手机版

    优德88客服电话_优德88手机中文版下载_w88官方网站手机版

  • 优德88com_w88Win优德_w88优德手机客户端

    优德88com_w88Win优德_w88优德手机客户端

  • 最近发表

      优德88下载_优德888官网手机版_优德88手机版

      http://www.ipomemo.net/

      |

      Powered By

      使用手机软件扫描微信二维码

      关注我们可获取更多热点资讯

      w88出品