风也温柔

计算机科学知识库

java lru算法 Java实现LRU算法(哈希表加双向链表)

  LRU

  LRU 全称 Least Used,意为最近最少使用java lru算法,是最常见的页面置换算法java lru算法,也常用于实现缓存淘汰策略。

  实现

  哈希表 + 双向链表。链表头节点代表最近使用过的数据。

  对于 get 操作,首先判断 key 是否存在:

  对于 put 操作java lru算法 Java实现LRU算法(哈希表加双向链表),首先判断 key 是否存在:

   class LRUCache {

        // 双向链表节点
        static class MyLinkedNode {
            private int key;
            private int value;
            MyLinkedNode prev;
            MyLinkedNode next;
            MyLinkedNode() {}
            MyLinkedNode(int key, int value){
                this.key = key;
                this.value = value;
            }
        }
        // Map,用于定位指定key的节点在链表中的位置
    <p>![lru算法题_java lru算法_lru算法原理][1]

        private Map cache;
        // 头、尾节点
        private MyLinkedNode head, tail;
        // 实际元素个数
        private int size;
        // 容量
        private int capacity;
        public LRUCache(int capacity) {
            this.size = 0;
            this.capacity = capacity;
            cache = new HashMap(capacity);
            head = new MyLinkedNode();
            tail = new MyLinkedNode();
            head.next = tail;
            tail.prev = head;
        }
        
        public int get(int key) {
            // 先获取到对应节点
    &emsp;&emsp;![lru算法原理_lru算法题_java lru算法][2]

            MyLinkedNode node = cache.get(key);
            // 不存在
            if(node == null) {
                return -1;
            }
            // 先删除链表中的该节点
            node.prev.next = node.next;
            node.next.prev = node.prev;
            // 将其放到链表头部,表示最近使用的元素
            move2head(node);
            return node.value;
        }
        
        public void put(int key, int value) {
            // 先获取对应节点
            MyLinkedNode node = cache.get(key);
            // 不存在
            if(node == null) {
                // 新建节点
                MyLinkedNode newNode = new MyLinkedNode(key, value);
    &emsp;&emsp;![lru算法题_lru算法原理_java lru算法][3]

                // 放入Map
                cache.put(key, newNode);
                size++;
                // 判断是否到达上限
                if(size > capacity) {
                    // 先删除最久未使用的数据,即链表尾部
                    MyLinkedNode n = tail.prev;
                    n.prev.next = tail;
                    tail.prev = n.prev;
                    cache.remove(n.key);
                    size--;
                }
                // 放入链表头部
                move2head(newNode);
            } else { // 存在
                // 更新值
                node.value = value;
                // 先删除链表中的该节点
                node.prev.next = node.next;
                node.next.prev = node.prev;
    &emsp;&emsp;![java lru算法_lru算法原理_lru算法题][4]

                // 放到链表头部
                move2head(node);
            }
        }
        private void move2head(MyLinkedNode node) {
            //放到头部
            node.prev = head;
            node.next = head.next;
            head.next.prev = node;
            head.next = node;
        }
    }

</p>
  测试(Junit)

   package com.zys.test;

    import com.zys.cache.LRUCache;
    import org.junit.Test;
    <p>![lru算法原理_lru算法题_java lru算法][5]

    /**
     * LRU算法测试
     *
     * @author Leo
     * @create 2021/1/27 9:55
     **/
    public class LRUCacheTest {
        @Test
        public void testLRUCache() {
            LRUCache lRUCache = new LRUCache(2);
            lRUCache.put(1, 1); // 缓存是 {1=1}
            lRUCache.put(2, 2); // 缓存是 {1=1, 2=2}
            System.out.println(lRUCache.get(1)); //返回 1
            lRUCache.put(3, 3); // 该操作会使得key为 2的缓存作废,缓存是 {1=1, 3=3}
            System.out.println(lRUCache.get(2));// 返回 -1 ,缓存 2 已被删除
            lRUCache.put(4, 4); // 该操作会使得 key为 1 的缓存作废,缓存是 {4=4, 3=3}
            System.out.println(lRUCache.get(1));// 返回 -1 ,缓存 1 已被删除
            System.out.println(lRUCache.get(3));    // 返回 3
            System.out.println(lRUCache.get(4));    // 返回 4
        }
    }

</p>
  文章来源:https://blog.csdn.net/qq_39340792/article/details/117303496