手撸LRU算法(java实现)

深碍√TFBOYSˉ_ 2022-12-23 09:57 215阅读 0赞

正文在下面，先打个广告：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ZneWlidXBp_size_16_color_FFFFFF_t_70]

# 使用javaAPI #

java 的LinkedHashMap可以实现LRU算法，LinkedHashMap 本身内部有一个触发条件则自动执行的方法：删除最老元素（最近最少使用的元素）。我们只需要通过参数控制数据排序逻辑和数据删除规则就行了。

LinkedHashMap源码中有这么一个注释：

<p>The {@link #removeEldestEntry(Map.Entry)} method may be overridden to
     * impose a policy for removing stale mappings automatically when new mappings
     * are added to the map.

可以看到 removeEldestEntry 方法可以用来删除过时的数据。不过他的默认实现是返回false，需要我们手动重写该方法。

protected boolean removeEldestEntry(Map.Entry<K,V> eldest) { 
     return false;
    }

还有一个需要注意的是，LinkedHashMap默认是按照插入顺序排序的，很显然不能满足LRU算法的需求。LRU是希望按照访问顺序排序，最新访问的数据放到队头，老数据放到队尾，这样数据总量超过容量时，删除队尾的数据即可。

LinkedHashMap构造函数中有一个参数accessOrder，该参数控制了数据排序的规则。下面get方法中可以看到，有个if判断，如果accessOrder是true，则将当前访问的node移动到队尾last（LinkedHashMap是用last存储最新数据）

/** * Constructs an empty <tt>LinkedHashMap</tt> instance with the * specified initial capacity, load factor and ordering mode. * * @param initialCapacity the initial capacity * @param loadFactor the load factor * @param accessOrder the ordering mode - <tt>true</tt> for * access-order, <tt>false</tt> for insertion-order * @throws IllegalArgumentException if the initial capacity is negative * or the load factor is nonpositive */
    public LinkedHashMap(int initialCapacity,
                         float loadFactor,
                         boolean accessOrder) { 
        super(initialCapacity, loadFactor);
        this.accessOrder = accessOrder;
    }
    
    public V get(Object key) { 
            Node<K,V> e;
            if ((e = getNode(hash(key), key)) == null)
                return null;
            if (accessOrder)
                afterNodeAccess(e);
            return e.value;
        }
    
    void afterNodeAccess(Node<K,V> e) {  // move node to last
            LinkedHashMap.Entry<K,V> last;
            if (accessOrder && (last = tail) != e) { 
                LinkedHashMap.Entry<K,V> p =
                    (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
                p.after = null;
                if (b == null)
                    head = a;
                else
                    b.after = a;
                if (a != null)
                    a.before = b;
                else
                    last = b;
                if (last == null)
                    head = p;
                else { 
                    p.before = last;
                    last.after = p;
                }
                tail = p;
                ++modCount;
            }
        }

当插入数据时，就会通过removeEldestEntry方法的返回值决定是否需要删除老的数据。

void afterNodeInsertion(boolean evict) {  // possibly remove eldest
        LinkedHashMap.Entry<K,V> first;
        if (evict && (first = head) != null && removeEldestEntry(first)) { 
            K key = first.key;
            removeNode(hash(key), key, null, false, true);
        }
    }

完整代码：

public interface ILru { 
        void put(Object key, Object value);
    
        void remove(String key);
    
        Object get(String key);
    }

public class JavaLRUCache implements ILru{ 
    
        private Map<Object, Object> map;
        private final int capacity;
    
        public JavaLRUCache(int capacity) { 
            this.capacity = capacity;
            map = new LinkedHashMap<Object, Object>(capacity, 0.75f, true) { 
                @Override
                protected boolean removeEldestEntry(Map.Entry<Object, Object> eldest) { 
                    return size() > capacity;
                }
    
                @Override
                public String toString() { 
                    return super.toString();
                }
            };
        }
    
        @Override
        public Object get(String key) { 
            return map.get(key);
        }
    
        @Override
        public void put(Object key, Object value) { 
            map.put(key, value);
        }
    
        @Override
        public void remove(String key) { 
            map.remove(key);
        }
    
        @Override
        public String toString() { 
            return "JavaLRUCache{" +
                    "map=" + map +
                    ", capacity=" + capacity +
                    '}';
        }
    }

# 纯手撸 #

纯手撸的话，其实和上面LinkedHashMap原理一样。  
先定义node

/** * @author liubenlog * @className Node * @description map 中的V，设置为一个对象，主要是为了记录前后指针，已达到 0（1）的时间复杂度 * @date 2020/10/22 16:02 */
    @Data
    public class Node { 
        private Object key;
        private Object value;
        private Node pre;
        private Node next;
    
        public Node(Object key, Object value){ 
            this.key=key;
            this.value=value;
        }
    
        @Override
        public String toString() { 
            return key.toString() + "=" + value.toString();
        }
    }

再定义链表，包含LRU的核心算法

/** * @author liubenlog * @className MyList * @description 双向链表. 我这里规定head是最新的数据 * @date 2020/10/22 16:03 */
    public class MyList { 
    
        private long maxSize;
    
        private Node head;
    
        private Node tail;
    
        private long size;
    
        private Map map;
    
        public MyList(long maxSize, Map map) { 
            this.maxSize = maxSize;
            this.map = map;
        }
    
        /** * 直接添加到tail * * @param node */
        public void add(Node node) { 
            size++;
            if (null == head) { 
                //head为空，说明此时队列中一个数据也没有
                head = node;
                tail = node;
            } else { 
                node.setPre(tail);
                tail.setNext(node);
                tail = node;
    
                //超过容量后，将head元素删除
                if (size > maxSize) { 
                    map.remove(head.getKey());
    
                    Node next = head.getNext();
                    next.setPre(null);
                    head.setNext(null);
                    head = next;
                    size--;
                }
            }
        }
    
        public void remove(Node node) { 
            if (null == head) { //队列为空
                return;
            } else if (head == node && tail == node) { //只有一个元素时
                head = null;
                tail = null;
                size--;
            } else { 
                Node pre = node.getPre();
                Node next = node.getNext();
                if (null != pre) { 
                    pre.setNext(next);
                } else { 
                    head = next;
                }
                if (null != next) { 
                    next.setPre(pre);
                } else { 
                    tail = pre;
                }
                node.setPre(null);
                node.setNext(null);
                size--;
            }
        }
    
        public void get(Node node) { 
            remove(node);
            add(node);
        }
    
        public void update(Node node) { 
            remove(node);
            add(node);
        }
    
        @Override
        public String toString() { 
            String result = "";
            if (head == null) { 
                return result;
            } else { 
                Node next = head;
                result += next + ", ";
                while ((next = next.getNext()) != null) { 
                    result += next + ", ";
                }
                return result;
            }
        }
    }

最后封装LRU

public class LRU implements ILru{ 
        private HashMap<Object, Node> map = new HashMap();
        private MyList list;
    
        public LRU(long size) { 
            list = new MyList(size, map);
        }
    
        @Override
        public void put(Object key, Object value) { 
            Node node = map.get(key);
            if (node == null) { 
                node = new Node(key, value);
                map.put(key, node);
                list.add(node);
            } else { 
                node.setValue(value);
                map.put(key, node);
                list.update(node);
            }
        }
    
        @Override
        public void remove(String key) { 
            list.remove(map.get(key));
            map.remove(key);
        }
    
        @Override
        public Object get(String key) { 
            Node node = map.get(key);
            if (node == null) { 
                return null;
            }
            list.get(node);
    
            return node.getValue();
        }
    
        @Override
        public String toString() { 
            return "LRU{" +
                    "list=" + list +
                    '}';
        }
    }

# 测试 #

测试代码

public class Main { 
        public static void main(String[] args) { 
            lruTest(new LRU(5));
            System.out.println("-------------------------");
            lruTest(new JavaLRUCache(5));
        }
    
        static void lruTest(ILru lru){ 
            lru.put("a", 1);
            System.out.println(lru.toString());
            lru.put("b", 2);
            System.out.println(lru.toString());
            lru.put("c", 3);
            System.out.println(lru.toString());
            lru.put("d", 4);
            System.out.println(lru.toString());
            lru.get("a");
            System.out.println("get a 1 " + lru.toString());
            lru.get("b");
            System.out.println("get b 2 " + lru.toString());
            lru.get("b");
            System.out.println("get b 2 " + lru.toString());
            lru.get("d");
            System.out.println("get d 4 " + lru.toString());
            lru.put("e", 5);
            System.out.println(lru.toString());
            lru.put("f", 6);
            System.out.println(lru.toString());
            lru.put("g", 7);
            System.out.println(lru.toString());
            lru.remove("g");
            System.out.println("remove g 7 " + lru.toString());
            lru.remove("e");
            System.out.println("remove e 5 " + lru.toString());
            lru.put("e", 5);
            System.out.println(lru.toString());
            lru.put("e", 9);
            System.out.println(lru.toString());
            lru.put("f", "f");
            System.out.println(lru.toString());
        }
    }

输出：

LRU{ list=a=1, }
    LRU{ list=a=1, b=2, }
    LRU{ list=a=1, b=2, c=3, }
    LRU{ list=a=1, b=2, c=3, d=4, }
    get a 1  LRU{ list=b=2, c=3, d=4, a=1, }
    get b 2  LRU{ list=c=3, d=4, a=1, b=2, }
    get b 2  LRU{ list=c=3, d=4, a=1, b=2, }
    get d 4  LRU{ list=c=3, a=1, b=2, d=4, }
    LRU{ list=c=3, a=1, b=2, d=4, e=5, }
    LRU{ list=a=1, b=2, d=4, e=5, f=6, }
    LRU{ list=b=2, d=4, e=5, f=6, g=7, }
    remove g 7  LRU{ list=b=2, d=4, e=5, f=6, }
    remove e 5  LRU{ list=b=2, d=4, f=6, }
    LRU{ list=b=2, d=4, f=6, e=5, }
    LRU{ list=b=2, d=4, f=6, e=9, }
    LRU{ list=b=2, d=4, e=9, f=f, }
    -------------------------
    JavaLRUCache{ map={ a=1}, capacity=5}
    JavaLRUCache{ map={ a=1, b=2}, capacity=5}
    JavaLRUCache{ map={ a=1, b=2, c=3}, capacity=5}
    JavaLRUCache{ map={ a=1, b=2, c=3, d=4}, capacity=5}
    get a 1  JavaLRUCache{ map={ b=2, c=3, d=4, a=1}, capacity=5}
    get b 2  JavaLRUCache{ map={ c=3, d=4, a=1, b=2}, capacity=5}
    get b 2  JavaLRUCache{ map={ c=3, d=4, a=1, b=2}, capacity=5}
    get d 4  JavaLRUCache{ map={ c=3, a=1, b=2, d=4}, capacity=5}
    JavaLRUCache{ map={ c=3, a=1, b=2, d=4, e=5}, capacity=5}
    JavaLRUCache{ map={ a=1, b=2, d=4, e=5, f=6}, capacity=5}
    JavaLRUCache{ map={ b=2, d=4, e=5, f=6, g=7}, capacity=5}
    remove g 7  JavaLRUCache{ map={ b=2, d=4, e=5, f=6}, capacity=5}
    remove e 5  JavaLRUCache{ map={ b=2, d=4, f=6}, capacity=5}
    JavaLRUCache{ map={ b=2, d=4, f=6, e=5}, capacity=5}
    JavaLRUCache{ map={ b=2, d=4, f=6, e=9}, capacity=5}
    JavaLRUCache{ map={ b=2, d=4, e=9, f=f}, capacity=5}

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ZneWlidXBp_size_16_color_FFFFFF_t_70]: /images/20221120/b2c799840a2a4b8a9b6dfc331ff7e333.png