[数据结构与算法]手写LRU算法两种方式

LRU是Least Recently Used的缩写，即最近最少使用，是一种常用的页面置换算法，选择最近最久未使用的页面予以淘汰。

 本质就是哈希表+双向链表来完成的，并且时间复杂度是O(1)也就是最快的方式.
 下面两种方式我参考学习来，在此做个记录直接上代码

第一种：

// 第一种方式
package com.gm.wj.demo;

import java.util.LinkedHashMap;
import java.util.Map;

public class LRUDemoLinkedHashMap<K,V> extends LinkedHashMap<K,V> {
    /**
     * 手写LRU算法·借助linkedHashMap实现
     *
     */

    /**
     * 负载因子
     */
    static private  float  load_factor = 0.75f;
    /**
     * 缓存容量
     */
     private int initialCapacity;


    /**
     * 调用父类的构造方法
     * @param initialCapacity
     *
     * 使用指定的初始容量、负载因子和排序模式构造一个空的LinkedHashMap实例。
     *
     * 当accessOrder：true时，排序按照访问(put和get都是访问)顺序进行排序。
     * （也就是插入和访问都会将当前节点放置到尾部，尾部代表的是最近访问的数据，这和JDK1.6是反过来的，jdk1.6头部是最近访问的）
     * 如果根据lru删除策略来进行处理近期访问次数较少的数据，则会首先删除头部的数据。
     *
     *
     * 当accessOrder：false时，排序按照插入顺序(put)进行排序。
     * (完全按照插入顺序为主，就算get数据，也不会改变数据在链表中的位置)
     *   如果根据lru删除策略来进行处理数据，则会首先删除头部的数据，且是先进先出。
     *
     */
    public LRUDemoLinkedHashMap(int initialCapacity){
        super(initialCapacity,load_factor,false);
        this.initialCapacity=initialCapacity;
    }


    /**
     * 调用父类的删除方法
     * @param eldest
     * @return

     * *如果此映射应删除其最早的条目，则返回true。
     * *此方法由put和putAll、after调用
     *
     * *在map中插入一个新条目。它提供了实现者每次有机会删除最老的条目时，都会删除一个新条目
     * 增加了。如果映射表示缓存，这将非常有用：它允许通过删除过时条目来减少内存消耗的映射。

     * *<p>示例使用：此覆盖将允许map增长到100条目，然后在每次创建新条目时删除最旧的条目
        添加，保持100个条目的稳定状态。<p>
     *
     * *私有静态最终int MAX_条目=100；

     * *受保护的布尔重构（Map.Entry最早）{
     *
     * *返回大小（）> 最大输入；
     *
     * * }
     *<p>此方法通常不会以任何方式修改map，而是允许map按照其返回值。允许对该方法进行修改
     * 直接映射，但如果它这样做，它必须返回false（表示映射不应尝试任何进一步修改）。
     * 返回true从该方法中修改映射后，未指定。

     * *<p>此实现仅返回false（因此map的行为类似于普通map-最老的元素永远不会被删除）。

     * *@param最早是最近在map中插入的条目，或者如果这是一个按访问顺序排列的映射，是最近访问最少的映射进入。这是将于本周删除的条目
    方法返回true。如果之前map是空的到put或putAll调用在这个调用中，这将是插入；换句话说，如果map包含一个最老的条目也是最新的条目。
     *
     * *@returntrue如果应该删除最老的条目从map上看false如果应该保留。
     *
     * */

    @Override
    protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
        return super.size() > 4;
    }





    public static void main(String[] args) {
        LRUDemoLinkedHashMap kvlruDemo = new LRUDemoLinkedHashMap(4);

        kvlruDemo.put("1", 1);
        kvlruDemo.put("2", 1);
        kvlruDemo.put("3", 1);
        kvlruDemo.put("4", 1);
        kvlruDemo.put("7", 1);
        kvlruDemo.put("8", 1);
        kvlruDemo.get("4");
        kvlruDemo.get("4");
        kvlruDemo.put("x",1);
       /* kvlruDemo.get("7");
        kvlruDemo.get("7");*/
        /*kvlruDemo.get("2");
        kvlruDemo.get("3");*/
        /*kvlruDemo.get("2");
        kvlruDemo.get("2");

        kvlruDemo.put("6", 1);*/
        /*kvlruDemo.put("7", 1);*/



        System.out.println(kvlruDemo.keySet());
    }


/**true
 * [7, 8, 3, x]
 *
 *
 */


/**
 * false
 *
 * [4, 7, 8, x]
 */
}

第二种：

package com.gm.wj.demo;

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

public class HandwrittenLRUDemo {

    /**
     *  手写LRU算法,此方式是按照元素的插入顺序（accessOrder：false）复现LRU算法
     *
     *      accessOrder：false时，排序按照插入顺序(put)进行排序。
     *      * (完全按照插入顺序为主，就算get数据，也不会改变数据在链表中的位置)
     *      *   如果根据lru删除策略来进行处理数据，则会首先删除头部的数据，且是先进先出。
     *
     *  */

    /**
     * 1.仿照linkedHashMap或者AbstractQueuedSynchronizer定义一个存放数据的载体Node<K,V>
     */
    class Node<K,V>{
        K key;
        V value;
        /**
         * 前指针
         */
        Node<K,V> prev;
        /**
         * 后指针
         */
        Node<K,V> next;

        /**
         * 无参构造方法
         */
        public Node(){
            this.prev =this.next = null;
        }

        /**
         * 有参构造方法，初始化Node
         * @param key
         * @param value
         */
        public Node(K key,V value){
            this.key = key;
            this.value = value;
            this.prev =this.next = null;
        }



    }

    /**
     * 2.构建一个双向链表用于存放Node节点,也可以理解为创建了一个队列
     */

    class bidirectionalLinkedList<K,V>{

        /**
         * 头指针
         */
        Node<K,V> head;
        /**
         * 尾指针
         */
        Node<K,V> tail;

        /**
         * 无参构造方法
         *
         *          <pre>         prev
         *      *      +------+  <===== +-----+       +-----+
         *      * head |      |      |     |       |     |  tail
         *      *      +------+  =====> +-----+       +-----+
         *      *   </pre>        next
         *
         *      如图此时初始化成为一个虚拟的双向队列，并且head头节点的next指针指向tail尾节点,
         *      tail尾节点的prev前指针指向head头节点，由此形成闭环。
         *      (注：head 和 tail 可以理解为指针也可以理解成Node节点)
         */

        public bidirectionalLinkedList(){
            head = new Node<>();
            tail = new Node<>();
            head.next =tail;
            tail.prev = head;
        }

        /**
         * 新增一个Node进入队列,相当于是在head节点和tail节点中间插入一个新的node节点，以head节点参照物。
         *
         * 1.head头节点的next指针指向新进入的node节点
         * 2.node节点的prev前指针指向head头节点
         * 2.node节点的next后指针指向tail尾节点（此时的tail是head头节点的下一个节点，用head.next表示）
         * 2.tail节点的prev前指针指向新进入的node节点（此时形成闭环）
         *
         * @param node
         */
        public void addHead(Node<K,V> node){
            node.prev = head;
            node.next = head.next;
            head.next.prev = node;
            head.next = node;
        }


        /**
         * 删除一个节点，就以node参照物.
         * 在这个虚拟队列中删除node,就是把node节点的前后指针的指向不再指向其他节点。
         * 在将node的前后两个节点连接起来，这样就是将node删除掉了，被删除的node节点将会被jvm回收清理
         *
         * @param node
         */
        public void removeNode(Node<K,V> node){
            node.next.prev = node.prev;
            node.prev.next = node.next;
            node.prev = null;
            node.next = null;

        }

        public Node<K,V>  getLast(){
           return tail.prev;
        }


    }

    /**
     * 缓存容量
     */
    private int initialCapacity;

    Map<Object,Node<Object,Object>> map;

    bidirectionalLinkedList<Object,Object> bidirectionalLinkedList;

    /**
     * 构造方法
     * @param initialCapacity
     */
    public HandwrittenLRUDemo(int initialCapacity){
        this.initialCapacity = initialCapacity;
        map = new HashMap<>();
        bidirectionalLinkedList = new bidirectionalLinkedList<>();

    }

    //查询方法
    public Object get(Object key){
        //如果不存在返回-1
        if (!map.containsKey(key)){
            return -1;
        }else {
            /**
             * 如果存在，通过key查找出map中存放的node节点，
             * 更新node节点的位置，从队列中删除该节点并添加到队列的尾部
             */
            Node<Object, Object> node = map.get(key);
            bidirectionalLinkedList.removeNode(node);
            bidirectionalLinkedList.addHead(node);
            return node.value;
        }
    }

    /**
     * 新增or更新，
     * @param key
     * @param value
     */
    public void put(Object key,Object value){
        /**
         * map中存在这个key,则更新数据并更新在队列中的位置
         */
        if (map.containsKey(key)){
            Node<Object, Object> node = map.get(key);
            node.value = value;
            map.put(key,node);
            bidirectionalLinkedList.removeNode(node);
            bidirectionalLinkedList.addHead(node);
        }else {
            /**
             * 当达到了缓存容量时，将从队列中找到tail尾节点的前一个节点，
             * 同时从队列中和map中删除
             */
            if (map.size() == initialCapacity){
                Node<Object, Object> lastNode = bidirectionalLinkedList.getLast();
                bidirectionalLinkedList.removeNode(lastNode);
                map.remove(lastNode.key);
            }
        }
        /**
         * 新增：
         */
        Node<Object, Object> newNode = new Node<>(key,value);
        map.put(key,newNode);
        bidirectionalLinkedList.addHead(newNode);

    }


    public static void main(String[] args) {
        HandwrittenLRUDemo kvlruDemo = new HandwrittenLRUDemo(4);

        kvlruDemo.put("1", 1);
        kvlruDemo.put("2", 1);
        kvlruDemo.put("3", 1);
        kvlruDemo.put("4", 1);
        kvlruDemo.put("7", 1);
        kvlruDemo.put("8", 1);
        kvlruDemo.get("4");
        kvlruDemo.get("4");
        kvlruDemo.put("x",1);
       /* kvlruDemo.get("7");
        kvlruDemo.get("7");*/
        /*kvlruDemo.get("2");
        kvlruDemo.get("3");*/
        /*kvlruDemo.get("2");
        kvlruDemo.get("2");

        kvlruDemo.put("6", 1);*/
        /*kvlruDemo.put("7", 1);*/



        System.out.println(kvlruDemo.map.keySet());
    }



}