• lru：最近最少使用(内存淘汰策略)
      • 算法实现 ```java package com.itheima;

    import java.util.HashMap; import java.util.Map;

    public class LRUCache {

    1. Entry head, tail;
    2. int capacity;
    3. int size;
    4. Map<Integer, Entry> cache;
    6. public LRUCache(int capacity) {
    7.     this.capacity = capacity;
    8.     // 初始化链表
    9.     initLinkedList();
    10.     size = 0;
    11.     cache = new HashMap<>(capacity + 2);
    12. }
    14. /**
    15.  * 如果节点不存在，返回 -1.如果存在，将节点移动到头结点，并返回节点的数据。
    16.  *
    17.  * @param key
    18.  * @return
    19.  */
    20. public int get(int key) {
    21.     Entry node = cache.get(key);
    22.     if (node == null) {
    23.         return -1;
    24.     }
    25.     // 存在移动节点
    26.     moveToHead(node);
    27.     return node.value;
    28. }
    30. /**
    31.  * 将节点加入到头结点，如果容量已满，将会删除尾结点
    32.  *
    33.  * @param key
    34.  * @param value
    35.  */
    36. public void put(int key, int value) {
    37.     Entry node = cache.get(key);
    38.     if (node != null) {
    39.         node.value = value;
    40.         moveToHead(node);
    41.         return;
    42.     }
    43.     // 不存在。先加进去，再移除尾结点
    44.     // 此时容量已满 删除尾结点
    45.     if (size == capacity) {
    46.         Entry lastNode = tail.pre;
    47.         deleteNode(lastNode);
    48.         cache.remove(lastNode.key);
    49.         size--;
    50.     }
    51.     // 加入头结点
    52.     Entry newNode = new Entry();
    53.     newNode.key = key;
    54.     newNode.value = value;
    55.     addNode(newNode);
    56.     cache.put(key, newNode);
    57.     size++;
    59. }
    61. private void moveToHead(Entry node) {
    62.     // 首先删除原来节点的关系
    63.     deleteNode(node);
    64.     addNode(node);
    65. }
    67. private void addNode(Entry node) {
    68.     head.next.pre = node;
    69.     node.next = head.next;
    71.     node.pre = head;
    72.     head.next = node;
    73. }
    75. private void deleteNode(Entry node) {
    76.     node.pre.next = node.next;
    77.     node.next.pre = node.pre;
    78. }
    80. public static class Entry {
    81.     public Entry pre;
    82.     public Entry next;
    83.     public int key;
    84.     public int value;
    86.     public Entry(int key, int value) {
    87.         this.key = key;
    88.         this.value = value;
    89.     }
    91.     public Entry() {
    92.     }
    93. }
    95. private void initLinkedList() {
    96.     head = new Entry();
    97.     tail = new Entry();
    99.     head.next = tail;
    100.     tail.pre = head;
    102. }
    104. public static void main(String[] args) {
    106.     LRUCache cache = new LRUCache(2);
    108.     cache.put(1, 1);
    109.     cache.put(2, 2); // 21
    110.     System.out.println(cache.get(1)); // 12
    111.     cache.put(3, 3); // 31
    112.     System.out.println(cache.get(2));
    114. }

    }

    ```