LRUCache 详解

刺骨的言语ヽ痛彻心扉 2022-08-05 07:24 158阅读 0赞

### LRU的基本概念： ###

LRU是Least Recently Used的缩写，近期最少使用算法。

### Java 实现LRUCache ###

1、基于LRU的基本概念，为了达到按近期最少使用排序，可以选择HashMap的子类  
 LinkedHashMap来作为LRUCache的存储容器。  
  2、LinkedHashMap的原理：  
  a、 对于LinkedHashMap而言，它继承与HashMap、底层使用哈希表与双向链表来保存所有元素。其基本操作与父类HashMap相似，它通过重写父类相关的方法，来实现自己的链接列表特性。HashMap是单链表，LinkedHashMap是双向链表  
  b、存储：LinkedHashMap并未重写父类HashMap的put方法，而是重写了父类HashMap的put方法调用的子方法void recordAccess(HashMap m)   ，void addEntry(int hash, K key, V value, int bucketIndex) 和void createEntry(int hash, K key, V value, int bucketIndex)，提供了自己特有的双向链接列表的实现。  
  c、读取：LinkedHashMap重写了父类HashMap的get方法，实际在调用父类getEntry()方法取得查找的元素后，再判断当排序模式accessOrder为true时，记录访问顺序，将最新访问的元素添加到双向链表的表头，并从原来的位置删除。由于的链表的增加、删除操作是常量级的，故并不会带来性能的损失。

### LRUCache的简单实现 ###

package com.knowledgeStudy.lrucache;
    import java.util.ArrayList;
    import java.util.Collection;
    import java.util.LinkedHashMap;
    import java.util.Map;
    /**
     * 固定大小 的LRUCache<br>
     * 线程安全
     **/
    public class LRUCache<K, V> {
        private static final float factor = 0.75f;//扩容因子
        private Map<K, V> map; //数据存储容器
        private int cacheSize;//缓存大小
        public LRUCache(int cacheSize) {
            this.cacheSize = cacheSize;
            int capacity = (int) Math.ceil(cacheSize / factor) + 1;
            map = new LinkedHashMap<K, V>(capacity, factor, true) {
                private static final long serialVersionUID = 1L;
                /**
                 * 重写LinkedHashMap的removeEldestEntry()固定table中链表的长度
                 **/
                @Override
                protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
                    boolean todel = size() > LRUCache.this.cacheSize;
                    return todel;
                }
            };
        }
        /**
         * 根据key获取value
         *
         * @param key
         * @return value
         **/
        public synchronized V get(K key) {
            return map.get(key);
        }
        /**
         * put一个key-value
         *
         * @param key
         *            value
         **/
        public synchronized void put(K key, V value) {
            map.put(key, value);
        }
        /**
         * 根据key来删除一个缓存
         *
         * @param key
         **/
        public synchronized void remove(K key) {
            map.remove(key);
        }
        /**
         * 清空缓存
         **/
        public synchronized void clear() {
            map.clear();
        }
        /**
         * 已经使用缓存的大小
         **/
        public synchronized int cacheSize() {
            return map.size();
        }
        /**
         * 获取缓存中所有的键值对
         **/
        public synchronized Collection<Map.Entry<K, V>> getAll() {
            return new ArrayList<Map.Entry<K, V>>(map.entrySet());
        }
    }