devbox
在线问答5
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

内存替换算法：LRU和LFU超详细！！！_内存替换算法 最复杂

作者：在线问答5 | 2024-08-09 01:36:06

赞

踩

内存替换算法 最复杂

在我们内存或者cache中有两种替换算法来保证内存或者cache中都是“热点”的数据，一个是LRU和LFU。下面会先分析再给出代码！

在这里的get和set操作的时间复杂度都是O（1），因为这两种速度都是很快的，不能要求O（n）。

一、LRU

首先我们搞一个双向链表。

我们定义这个规则：如果有节点被访问（get或者set），那么直接放入到末尾，每一个队列都有一个capacity值表示容量，如果新元素加入，现在达到了容量值，就需要淘汰最近最少使用的，就是头节点。例如：现在node1被访问。

如果现在又来了一个新元素noden+1，超过了容量值。所以：剔除node2，noden+1条件到末尾

这就是最近最少使用的算法，热点数据都在队尾。删除只删除头节点。

基础数据结构Node

  1.     public static class Node<V> {
  2.         public V value;
  3.         public Node<V> pre;
  4.         public Node<V> next;
  5.  
  6.         public Node(V value) {
  7.             this.value = value;
  8.         }
  9.     }

双向队列

基本属性和构造函数

  1.     public static class DoubleLinkedList<V> {
  2.         private Node<V> head;
  3.         private Node<V> tail;
  4.  
  5.         public DoubleLinkedList() {
  6.             this.head = null;
  7.             this.tail = null;
  8.         }

下面我们来看方法：

  1.         public void addNode(Node<V> newNode) {
  2.             if (newNode == null) {
  3.                 return;
  4.             }
  5.             if (this.head == null) {
  6.                 this.head = newNode;
  7.                 this.tail = newNode;
  8.             } else {
  9.                 this.tail.next = newNode;
  10.                 newNode.pre = this.tail;
  11.                 this.tail = newNode;
  12.             }
  13.         }

添加新节点，如果当前是第一个元素，头指针和尾指针都指向它，如果不是，放在队尾

  1.         public void moveNodeToTail(Node<V> node) {
  2.             if (this.tail == null) {
  3.                 return;
  4.             }
  5.             if (this.head == node) {
  6.                 this.head = node.next;
  7.                 this.head.pre = null;
  8.             } else {
  9.                 node.pre.next = node.next;
  10.                 node.next.pre = node.pre;
  11.             }
  12.             this.tail.next = node;
  13.             node.pre = this.tail;
  14.             this.tail = node;
  15.             this.tail.next = null;
  16.         }

将一个节点移动到队尾，分为该节点是不是头节点，如果是头节点指向下一个，如果不是，就直接拿出来，然后放到队尾。

  1.         public Node<V> removeHead() {
  2.             if(this.head == null){
  3.                 return this.head;
  4.             }
  5.             Node<V> res = this.head;
  6.             if(this.head == this.tail){
  7.                 this.head = null;
  8.                 this.tail = null;
  9.             }else{
  10.                 this.head = res.next;
  11.                 res.next = null;
  12.                 this.head.pre = null;
  13.             }
  14.             return res;
  15.         }

 删除头节点并返回。

Cache数据结构

基本属性和构造方法

  1.     public static class MyCache<K,V>{
  2.         private HashMap<K,Node<V>>  keyNodeMap;
  3.         private HashMap<Node<V>,K>  nodeKeyMap;
  4.         private DoubleLinkedList<V> nodeList;
  5.         private int capacity;
  6.  
  7.         public MyCache(int capacity){
  8.             if(capacity < 1){
  9.                 throw new RuntimeException();
  10.             }
  11.             this.nodeKeyMap = new HashMap<>();
  12.             this.keyNodeMap = new HashMap<>();
  13.             this.nodeList = new DoubleLinkedList<>();
  14.             this.capacity = capacity;
  15.         }

这里面用到了两个HashMap，为啥？因为hashmap的put和get的时间复杂度都是O（1），如果不用，遍历链表，那么我们的操作就是时间复杂度O（n），所以用到它俩主要是以空间换时间的方式提升效率！！！

get方法，获取value，判断key是否在map里面，如果再然后拿出节点，再移动到末尾。

  1.         public V get(K key){
  2.             if(this.keyNodeMap.containsKey(key)){
  3.                 Node<V> res = this.keyNodeMap.get(key);
  4.                 this.nodeList.moveNodeToTail(res);
  5.                 return res.value;
  6.             }
  7.             return null;
  8.         }

set方法，判断是否有，如果有取出，移动到末尾，如果没有新建节点，加入，然后判断是否达到了容量，如果达到了容量就剔除头部节点。

  1.         public void set(K key,V value){
  2.             if(this.keyNodeMap.containsKey(key)){
  3.                 Node<V> target = keyNodeMap.get(key);
  4.                 target.value = value;
  5.                 this.nodeList.moveNodeToTail(target);
  6.             }else{
  7.                 Node<V> node = new Node<>(value);
  8.                 this.keyNodeMap.put(key,node);
  9.                 this.nodeKeyMap.put(node,key);
  10.                 this.nodeList.addNode(node);
  11.                 if(this.keyNodeMap.size() == this.capacity + 1){
  12.                     removeMostCache();
  13.                 }
  14.             }
  15.         }
  1.         private void removeMostCache(){
  2.             Node<V> node = this.nodeList.removeHead();
  3.             K removeKey = this.nodeKeyMap.get(node);
  4.             this.keyNodeMap.remove(removeKey);
  5.             this.nodeKeyMap.remove(node);
  6.         }

这样就做到了get和set方法的时间复杂度O（1）。

二、LFU

最近最少使用算法，这个算法相比于LRU就有难度了。我们来看思路：两个数据结构。

小节点类型

  1.     /**
  2.      * 小节点类型
  3.      */
  4.     public static class Node {
  5.         public Integer key;
  6.         public Integer value;
  7.         public Integer times;
  8.         public Node up;
  9.         public Node down;
  10.  
  11.         public Node(int key, int value, int times) {
  12.             this.key = key;
  13.             this.value = value;
  14.             this.times = times;
  15.         }
  16.     }

大节点类型 

  1.    /**
  2.      * 大节点类型
  3.      */
  4.     public static class NodeList {
  5.         public Node head;
  6.         public Node tail;
  7.         public NodeList pre;
  8.         public NodeList next;
  9.  
  10.         public NodeList(Node node) {
  11.             this.head = node;
  12.             this.tail = node;
  13.         }

实际上就是一个下面的结构，矩形表示NodeList，圆形表示Node。 

我们的数据是字母，上面矩形表示访问（get和set方法）的次数。先解释一下我们的规则：

（1）NodeList只有在下面有节点的时候才会被创建，如果下面的节点被移除，那么删除该NodeList。

（2）NodeList中head和tail分别指向下面圆形双向链表的头跟尾部。他本身也是一个双向链表。

（3）如果现在有一个新节点W被访问。插入到1下面的双向链表的首部

如果此时A被访问：就到2下面的双向链表的首部。

如果A再次被访问：

如果此时2被访问。2下面没有元素了，就删除2，然后c放到3上。

如果此时A再次被访问，那么创建4的NodeList，然后插入A：

如果这个时候来了一个H，但是现在达到了最大容量，就要剔除一个，我们剔除1下面双向链表的尾节点。

这个NodeList的头节点的node双向链表的尾节点就是最近最少使用的节点。以上就是整个LFU的过程，下面我们来看代码！

  1.    /**
  2.      * 大节点类型
  3.      */
  4.     public static class NodeList {
  5.         public Node head;
  6.         public Node tail;
  7.         public NodeList pre;
  8.         public NodeList next;
  9.  
  10.         public NodeList(Node node) {
  11.             this.head = node;
  12.             this.tail = node;
  13.         }
  14.  
  15.         /**
  16.          * 新到的节点放在头部位置
  17.          */
  18.         public void addNodeFromHead(Node newNode) {
  19.             newNode.down = this.head;
  20.             this.head.up = newNode;
  21.             head = newNode;
  22.         }
  23.  
  24.         public boolean isEmpty() {
  25.             return head == null;
  26.         }
  27.  
  28.         /**
  29.          * 移除节点到下一个NodeList。
  30.          */
  31.         public void deleteNode(Node node) {
  32.             if (this.head == this.tail) {
  33.                 this.head = null;
  34.                 this.tail = null;
  35.             } else {
  36.                 if (node == head) {
  37.                     head = node.down;
  38.                     head.up = null;
  39.                 } else if (node == tail) {
  40.                     tail = node.up;
  41.                     tail.down = null;
  42.                 } else {
  43.                     node.up.down = node.down;
  44.                     node.down.up = node.up;
  45.                 }
  46.             }
  47.             node.up = null;
  48.             node.down = null;
  49.         }
  50.     }

在NodeList里面我们提供了三个方法：

（1）addNodeFromHead：将新加入的节点放在头部位置，保证无论进入哪个NodeList都必须保证在头部位置。

（2）isEmpty：判断当前NodeList是否为null。

（3）deleteNode：就是将访问的节点，从该NodeList移除，这个节点可以是头尾节点或者中间节点。

  1.     public static class LFUCache {
  2.         private int capacity;
  3.         private int size;
  4.         //key => node
  5.         private HashMap<Integer, Node> records;
  6.         //存储node的nodelist节点
  7.         private HashMap<Node, NodeList> heads;
  8.         //nodelist头节点
  9.         private NodeList headList;
  10.  
  11.         public LFUCache(int capacity) {
  12.             this.capacity = capacity;
  13.             this.size = 0;
  14.             this.records = new HashMap<>();
  15.             this.heads = new HashMap<>();
  16.             this.headList = null;
  17.         }

这里面有几个属性：

（1）capacity：表示最大容量

（2）size：表示当前大小。

（3）records：表示key和node，这里的key是Integer，value是node类型

（4）heads：表示的是Node的上层NodeList节点是哪个。

（5）headList：表示所有NodeList的双向链表的头一个。

下面看方法：

判断如果有这元素，就更新数据同时times次数+1。然后执行move方法移动到下一个节点。move方法后面会有，如果没在并且达到了容量，就剔除一个节点，然后放入一个新节点

  1.         public void set(int key, int value) {
  2.             if (records.containsKey(key)) {
  3.                 Node node = records.get(key);
  4.                 node.value = value;
  5.                 node.times++;
  6.                 NodeList curNodeList = heads.get(node);
  7.                 //讲目标节点移动到下一个NodeList
  8.                 move(node, curNodeList);
  9.             } else {
  10.                 //达到容量
  11.                 if (size == capacity) {
  12.                     Node node = headList.tail;
  13.                     headList.deleteNode(node);
  14.                     //是否删除这个头
  15.                     modifyHeadList(headList);
  16.                     records.remove(node.key);
  17.                     heads.remove(node);
  18.                     size--;
  19.                 }
  20.                 Node node = new Node(key, value, 1);
  21.                 //刚开始加入第一个元素
  22.                 if (headList == null) {
  23.                     headList = new NodeList(node);
  24.                 } else {
  25.                     if (headList.head.times.equals(node.times)) {
  26.                         headList.addNodeFromHead(node);
  27.                     } else {
  28.                         NodeList newList = new NodeList(node);
  29.                         newList.next = headList;
  30.                         headList.pre = newList;
  31.                         headList = newList;
  32.                     }
  33.                 }
  34.                 records.put(key, node);
  35.                 heads.put(node, headList);
  36.                 size++;
  37.             }
  38.         }

剔除元素之后，要判断这个NodeList是不是没有node了，入股没有就删除，否则留下。

  1.         /**
  2.          * 如果当前nodelist为空，就更换headList，否则就不
  3.          */
  4.         private boolean modifyHeadList(NodeList nodeList) {
  5.             if (nodeList.isEmpty()) {
  6.                 if (headList == nodeList) {
  7.                     headList = nodeList.next;
  8.                     if (headList != null) {
  9.                         headList.pre = null;
  10.                     }
  11.                 } else {
  12.                     nodeList.pre.next = nodeList.next;
  13.                     if (nodeList.next != null) {
  14.                         nodeList.next.pre = nodeList.pre;
  15.                     }
  16.                 }
  17.                 return true;
  18.             }
  19.             return false;
  20.         }

移动节点到新的NodeList

  1.         private void move(Node node, NodeList oldNodeList) {
  2.             oldNodeList.deleteNode(node);
  3.             //拿到前一个节点的NodeList
  4.             NodeList preList = modifyHeadList(oldNodeList) ? oldNodeList.pre : oldNodeList;
  5.             NodeList nextList = oldNodeList.next;
  6.             if (nextList == null) {
  7.                 NodeList newList = new NodeList(node);
  8.                 if (preList != null) {
  9.                     preList.next = newList;
  10.                 }
  11.                 newList.pre = preList;
  12.                 if (headList == null) {
  13.                     headList = newList;
  14.                 }
  15.                 heads.put(node, newList);
  16.             } else {
  17.                 if (nextList.head.times.equals(node.times)) {
  18.                     nextList.addNodeFromHead(node);
  19.                     heads.put(node, nextList);
  20.                 } else {
  21.                     NodeList newList = new NodeList(node);
  22.                     if (preList != null) {
  23.                         preList.next = newList;
  24.                     }
  25.                     newList.pre = preList;
  26.                     newList.next = nextList;
  27.                     nextList.pre = newList;
  28.                     if (headList == nextList) {
  29.                         headList = newList;
  30.                     }
  31.                     heads.put(node, newList);
  32.  
  33.                 }
  34.             }
  35.         }

get方法：

  1.         public int get(int key) {
  2.             if (!records.containsKey(key)) {
  3.                 return -1;
  4.             }
  5.             Node node = records.get(key);
  6.             node.times++;
  7.             NodeList curNodeList = heads.get(node);
  8.             move(node, curNodeList);
  9.             return node.value;
  10.         }

完整代码：

LFU：

  1. public class LFU {
  2.  
  3.     /**
  4.      * 小节点类型
  5.      */
  6.     public static class Node {
  7.         public Integer key;
  8.         public Integer value;
  9.         public Integer times;
  10.         public Node up;
  11.         public Node down;
  12.  
  13.         public Node(int key, int value, int times) {
  14.             this.key = key;
  15.             this.value = value;
  16.             this.times = times;
  17.         }
  18.     }
  19.  
  20.     /**
  21.      * 大节点类型
  22.      */
  23.     public static class NodeList {
  24.         public Node head;
  25.         public Node tail;
  26.         public NodeList pre;
  27.         public NodeList next;
  28.  
  29.         public NodeList(Node node) {
  30.             this.head = node;
  31.             this.tail = node;
  32.         }
  33.  
  34.         /**
  35.          * 新到的节点放在头部位置
  36.          */
  37.         public void addNodeFromHead(Node newNode) {
  38.             newNode.down = this.head;
  39.             this.head.up = newNode;
  40.             head = newNode;
  41.         }
  42.  
  43.         public boolean isEmpty() {
  44.             return head == null;
  45.         }
  46.  
  47.         /**
  48.          * 移除节点到下一个NodeList。
  49.          */
  50.         public void deleteNode(Node node) {
  51.             if (this.head == this.tail) {
  52.                 this.head = null;
  53.                 this.tail = null;
  54.             } else {
  55.                 if (node == head) {
  56.                     head = node.down;
  57.                     head.up = null;
  58.                 } else if (node == tail) {
  59.                     tail = node.up;
  60.                     tail.down = null;
  61.                 } else {
  62.                     node.up.down = node.down;
  63.                     node.down.up = node.up;
  64.                 }
  65.             }
  66.             node.up = null;
  67.             node.down = null;
  68.         }
  69.     }
  70.  
  71.     public static class LFUCache {
  72.         private int capacity;
  73.         private int size;
  74.         //key => node
  75.         private HashMap<Integer, Node> records;
  76.         //存储node的nodelist节点
  77.         private HashMap<Node, NodeList> heads;
  78.         //nodelist头节点
  79.         private NodeList headList;
  80.  
  81.         public LFUCache(int capacity) {
  82.             this.capacity = capacity;
  83.             this.size = 0;
  84.             this.records = new HashMap<>();
  85.             this.heads = new HashMap<>();
  86.             this.headList = null;
  87.         }
  88.  
  89.         public void set(int key, int value) {
  90.             if (records.containsKey(key)) {
  91.                 Node node = records.get(key);
  92.                 node.value = value;
  93.                 node.times++;
  94.                 NodeList curNodeList = heads.get(node);
  95.                 //讲目标节点移动到下一个NodeList
  96.                 move(node, curNodeList);
  97.             } else {
  98.                 //达到容量
  99.                 if (size == capacity) {
  100.                     Node node = headList.tail;
  101.                     headList.deleteNode(node);
  102.                     //是否删除这个头
  103.                     modifyHeadList(headList);
  104.                     records.remove(node.key);
  105.                     heads.remove(node);
  106.                     size--;
  107.                 }
  108.                 Node node = new Node(key, value, 1);
  109.                 //刚开始加入第一个元素
  110.                 if (headList == null) {
  111.                     headList = new NodeList(node);
  112.                 } else {
  113.                     if (headList.head.times.equals(node.times)) {
  114.                         headList.addNodeFromHead(node);
  115.                     } else {
  116.                         NodeList newList = new NodeList(node);
  117.                         newList.next = headList;
  118.                         headList.pre = newList;
  119.                         headList = newList;
  120.                     }
  121.                 }
  122.                 records.put(key, node);
  123.                 heads.put(node, headList);
  124.                 size++;
  125.             }
  126.         }
  127.  
  128.         public int get(int key) {
  129.             if (!records.containsKey(key)) {
  130.                 return -1;
  131.             }
  132.             Node node = records.get(key);
  133.             node.times++;
  134.             NodeList curNodeList = heads.get(node);
  135.             move(node, curNodeList);
  136.             return node.value;
  137.         }
  138.  
  139.         /**
  140.          * 如果当前nodelist为空，就更换headList，否则就不
  141.          */
  142.         private boolean modifyHeadList(NodeList nodeList) {
  143.             if (nodeList.isEmpty()) {
  144.                 if (headList == nodeList) {
  145.                     headList = nodeList.next;
  146.                     if (headList != null) {
  147.                         headList.pre = null;
  148.                     }
  149.                 } else {
  150.                     nodeList.pre.next = nodeList.next;
  151.                     if (nodeList.next != null) {
  152.                         nodeList.next.pre = nodeList.pre;
  153.                     }
  154.                 }
  155.                 return true;
  156.             }
  157.             return false;
  158.         }
  159.  
  160.         private void move(Node node, NodeList oldNodeList) {
  161.             oldNodeList.deleteNode(node);
  162.             //拿到前一个节点的NodeList
  163.             NodeList preList = modifyHeadList(oldNodeList) ? oldNodeList.pre : oldNodeList;
  164.             NodeList nextList = oldNodeList.next;
  165.             if (nextList == null) {
  166.                 NodeList newList = new NodeList(node);
  167.                 if (preList != null) {
  168.                     preList.next = newList;
  169.                 }
  170.                 newList.pre = preList;
  171.                 if (headList == null) {
  172.                     headList = newList;
  173.                 }
  174.                 heads.put(node, newList);
  175.             } else {
  176.                 if (nextList.head.times.equals(node.times)) {
  177.                     nextList.addNodeFromHead(node);
  178.                     heads.put(node, nextList);
  179.                 } else {
  180.                     NodeList newList = new NodeList(node);
  181.                     if (preList != null) {
  182.                         preList.next = newList;
  183.                     }
  184.                     newList.pre = preList;
  185.                     newList.next = nextList;
  186.                     nextList.pre = newList;
  187.                     if (headList == nextList) {
  188.                         headList = newList;
  189.                     }
  190.                     heads.put(node, newList);
  191.  
  192.                 }
  193.             }
  194.         }
  195.     }
  196. }

LRU：

  1. package day_05;
  2.  
  3. import java.util.HashMap;
  4.  
  5. /**
  6.  * @ClassName LRU
  7.  * @Description
  8.  * @Author 戴书博
  9.  * @Date 2020/6/13 20:18
  10.  * @Version 1.0
  11.  **/
  12. public class LRU {
  13.  
  14.     public static class Node<V> {
  15.         public V value;
  16.         public Node<V> pre;
  17.         public Node<V> next;
  18.  
  19.         public Node(V value) {
  20.             this.value = value;
  21.         }
  22.     }
  23.  
  24.     public static class DoubleLinkedList<V> {
  25.         private Node<V> head;
  26.         private Node<V> tail;
  27.  
  28.         public DoubleLinkedList() {
  29.             this.head = null;
  30.             this.tail = null;
  31.         }
  32.  
  33.         public void addNode(Node<V> newNode) {
  34.             if (newNode == null) {
  35.                 return;
  36.             }
  37.             if (this.head == null) {
  38.                 this.head = newNode;
  39.                 this.tail = newNode;
  40.             } else {
  41.                 this.tail.next = newNode;
  42.                 newNode.pre = this.tail;
  43.                 this.tail = newNode;
  44.             }
  45.         }
  46.  
  47.         public void moveNodeToTail(Node<V> node) {
  48.             if (this.tail == null) {
  49.                 return;
  50.             }
  51.             if (this.head == node) {
  52.                 this.head = node.next;
  53.                 this.head.pre = null;
  54.             } else {
  55.                 node.pre.next = node.next;
  56.                 node.next.pre = node.pre;
  57.             }
  58.             this.tail.next = node;
  59.             node.pre = this.tail;
  60.             this.tail = node;
  61.             this.tail.next = null;
  62.         }
  63.  
  64.         public Node<V> removeHead() {
  65.             if(this.head == null){
  66.                 return this.head;
  67.             }
  68.             Node<V> res = this.head;
  69.             if(this.head == this.tail){
  70.                 this.head = null;
  71.                 this.tail = null;
  72.             }else{
  73.                 this.head = res.next;
  74.                 res.next = null;
  75.                 this.head.pre = null;
  76.             }
  77.             return res;
  78.         }
  79.     }
  80.  
  81.     public static class MyCache<K,V>{
  82.         private HashMap<K,Node<V>>  keyNodeMap;
  83.         private HashMap<Node<V>,K>  nodeKeyMap;
  84.         private DoubleLinkedList<V> nodeList;
  85.         private int capacity;
  86.  
  87.         public MyCache(int capacity){
  88.             if(capacity < 1){
  89.                 throw new RuntimeException();
  90.             }
  91.             this.nodeKeyMap = new HashMap<>();
  92.             this.keyNodeMap = new HashMap<>();
  93.             this.nodeList = new DoubleLinkedList<>();
  94.             this.capacity = capacity;
  95.         }
  96.  
  97.         public V get(K key){
  98.             if(this.keyNodeMap.containsKey(key)){
  99.                 Node<V> res = this.keyNodeMap.get(key);
  100.                 this.nodeList.moveNodeToTail(res);
  101.                 return res.value;
  102.             }
  103.             return null;
  104.         }
  105.  
  106.         public void set(K key,V value){
  107.             if(this.keyNodeMap.containsKey(key)){
  108.                 Node<V> target = keyNodeMap.get(key);
  109.                 target.value = value;
  110.                 this.nodeList.moveNodeToTail(target);
  111.             }else{
  112.                 Node<V> node = new Node<>(value);
  113.                 this.keyNodeMap.put(key,node);
  114.                 this.nodeKeyMap.put(node,key);
  115.                 this.nodeList.addNode(node);
  116.                 if(this.keyNodeMap.size() == this.capacity + 1){
  117.                     removeMostCache();
  118.                 }
  119.             }
  120.         }
  121.         private void removeMostCache(){
  122.             Node<V> node = this.nodeList.removeHead();
  123.             K removeKey = this.nodeKeyMap.get(node);
  124.             this.keyNodeMap.remove(removeKey);
  125.             this.nodeKeyMap.remove(node);
  126.         }
  127.  
  128.  
  129.     }
  130. }

 

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/在线问答5/article/detail/950796
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号