LRU算法实现, 参考LinkedHashMap

直接上代码

  1. package LRUCache;
  3. import java.util.HashMap;
  4. import java.util.Map;
  6. /**
  7.  * @author RYH
  8.  * @description lru算法, 参考linkedHashmap
  9.  * @date 2022/2/21
  10.  **/
  11. public class LRUCacheDemo<K, V> {
  12.     /**
  13.      * 容量
  14.      */
  15.     private final int capacity;
  16.     /**
  17.      * 用来存放key和节点, 方便快速查找
  18.      */
  19.     Map<Integer, Node<Integer, Integer>> map;
  20.     /**
  21.      * 用来存放各个数据节点
  22.      */
  23.     Node.DoubleLinkedList<Integer, Integer> doubleLinkedList;
  26.     public LRUCacheDemo(int capacity) {
  27.         this.capacity = capacity;
  28.         map = new HashMap<>();
  29.         doubleLinkedList = new Node.DoubleLinkedList<>();
  30.     }
  32.     /**
  33.      * 获取数据
  34.      * <p>
  35.      * 如果数据被使用, 则需要更新数据位置
  36.      *
  37.      * @param key 数据key
  38.      * @return 存放的value
  39.      */
  40.     public int get(int key) {
  41.         if (!map.containsKey(key)) {
  42.             return -1;
  43.         }
  44.         Node<Integer, Integer> node = map.get(key);
  45.         doubleLinkedList.removeNode(node);
  46.         doubleLinkedList.addHead(node);
  47.         return node.value;
  48.     }
  50.     /**
  51.      * 数据新增
  52.      * <p>
  53.      * 如果存在数据key,则更新相应的值(类似hashmap),并且更新数据位置,
  54.      * 如果不存在则新增,
  55.      *
  56.      * @param key   数据key
  57.      * @param value 数据值
  58.      */
  59.     public void put(int key, int value) {
  60.         if (map.containsKey(key)) {
  61.             Node<Integer, Integer> node = map.get(key);
  62.             node.value = value;
  63.             map.put(key, node);
  64.             doubleLinkedList.removeNode(node);
  65.             doubleLinkedList.addHead(node);
  66.         } else {
  67.             if (map.size() == this.capacity) {
  68.                 Node<Integer, Integer> last = doubleLinkedList.getLast();
  69.                 map.remove(last.key);
  70.                 doubleLinkedList.removeNode(last);
  71.             }
  72.             Node<Integer, Integer> node = new Node<>(key, value);
  73.             map.put(key, node);
  74.             doubleLinkedList.addHead(node);
  75.         }
  76.     }
  78.     /**
  79.      * 内部节点类 用于存放数据节点
  80.      *
  81.      * @param <K> key
  82.      * @param <V> value
  83.      */
  84.     static class Node<K, V> {
  85.         K key;
  86.         V value;
  87.         Node<K, V> prev;
  88.         Node<K, V> next;
  90.         Node() {
  91.             this.prev = this.next = null;
  92.         }
  94.         Node(K key, V value) {
  95.             this.key = key;
  96.             this.value = value;
  97.             this.prev = this.next = null;
  98.         }
  100.         /**
  101.          * 内部双向链表
  102.          * 记录数据书否被更新, 数据被操作, 则数据移到队列头部
  103.          *
  104.          * @param <K>
  105.          * @param <V>
  106.          */
  107.         static class DoubleLinkedList<K, V> {
  108.             Node<K, V> head;
  109.             Node<K, V> tail;
  111.             public DoubleLinkedList() {
  112.                 head = new Node<>();
  113.                 tail = new Node<>();
  114.                 head.next = tail;
  115.                 tail.prev = head;
  116.             }
  118.             /**
  119.              * 向链表头部插入数据
  120.              *
  121.              * @param node 数据节点
  122.              */
  123.             public void addHead(Node<K, V> node) {
  124.                 node.next = head.next;
  125.                 node.prev = head;
  126.                 head.next.prev = node;
  127.                 head.next = node;
  129.             }
  131.             /**
  132.              * 移除链表数据
  133.              *
  134.              * @param node 数据节点
  135.              */
  136.             public void removeNode(Node<K, V> node) {
  137.                 node.prev.next = node.next;
  138.                 node.next.prev = node.prev;
  139.                 node.prev = null;
  140.                 node.next = null;
  141.             }
  143.             /**
  144.              * 获取数据最后一个节点
  145.              *
  146.              * @return 最后一个数据节点
  147.              */
  148.             public Node<K, V> getLast() {
  149.                 return tail.prev;
  150.             }
  151.         }
  152.     }
  154. }