使用LinkedHashMap实现简单的LRU

绝地灬酷狼 2022-12-09 11:55 173阅读 0赞

`LRU`在很多缓存失效策略中会涉及，本质是一种更公平的节约资源策略  
  
比如使用redis缓存数据，不可能将所有资源都缓存起来，内存耗不起  
  
但也不能一刀切的设定一个过期时间，自动过期，因为可能热点数据它经常被访问到  
  
LRU算法思想应运而生，LRU是Least Recently Used的缩写，即最近最少使用  
  
在资源有限的情况下，我们要将**最近最少使用**的对象解除资源占用，给更需要的场景

java中的LinkedHashMap就有自带的实现`LRU`  
  
  
  
简单说一下LinkedHashMap这种数据结构，本质是HashMap+双向链表，不仅有HashMap的特性，还能维护元素的顺序，示意图如下  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xlaXN1cmVfbGlmZQ_size_16_color_FFFFFF_t_70_pic_center]  
使用LinkedHashMap实现简单的LRU  
  
杨家将父子打扑克，跑得快，一局只能有四个人参与，但杨家将父子有八人  
  
  
约定赢了（被访问次数多）的前两位留下，输了（访问次数少）的出局，给后面的新进的腾位置

package cn.com.suntree.utils.myself;
    
    import java.util.LinkedHashMap;
    import java.util.Map;
    import java.util.Set;
    
    /** * 自定义LRU 类 * @param <K> * @param <V> */
    public class LRU<K, V> { 
    
        private final float loadFactory = 0.75f; //使用LinkedHashMap容量，负载因子使用默认的0.75
        private LinkedHashMap<K, V> map;
    
        public LRU(int maxCacheSize) { 
            int capacity = (int)Math.ceil(maxCacheSize / this.loadFactory) + 1;// HashMap达到容量就进行扩容，if ((size >= threshold)，因此需要+1
    
            map = new LinkedHashMap<K, V>(capacity, loadFactory, true) { // accessOrder为true表示LRU
    
                @Override
                protected boolean removeEldestEntry(Map.Entry eldest) {  // 重写removeEldestEntry，当容量超过maxCacheSize会移除first
                    return size() > maxCacheSize;
                }
            };
        }
    
        /** * 都是调用 LinkedHashMap 的方法 */
        public void put(K key, V value) { 
            map.put(key, value);
        }
    
        public V get(K key) { 
            return map.get(key);
        }
    
        public void remove(K key) { 
            map.remove(key);
        }
    
        public boolean contain(K key) { 
            return map.containsKey(key);
        }
    
    
        /** * 跑得快，一局四个人，轮流来，最先进场的先出来 * @param args */
        public static void main(String[] args) { 
            LRU<String, String> runFast = new LRU<String, String>(4);// 一局四个人参与
            Set<Map.Entry<String, String>> entries = runFast.map.entrySet();
            runFast.put("1号选手", "杨大郎");
            runFast.put("2号选手", "杨二郎");
            runFast.put("3号选手", "杨三郎");
            runFast.put("4号选手", "杨四郎");
            System.out.println("第一局跑得快参与人：");
            for (Map.Entry<String, String> map:entries){ 
                System.out.print(map.getKey()+"---------"+map.getValue()+" ");
            }
    
            runFast.get("1号选手");// 杨大郎赢了
            runFast.get("4号选手");// 杨四郎赢了
    
    
    
    
            System.out.println();
            runFast.put("5号选手", "杨五郎");// 赢了的留下，输了的褪下（未被访问）
            runFast.put("6号选手", "杨六郎");
    
    
            System.out.println("第二局跑得快参与人：");// 二郎、三郎出局
            for (Map.Entry<String, String> map:entries){ 
                System.out.print(map.getKey()+"---------"+map.getValue()+" ");
            }
    
            runFast.get("1号选手");// 杨大郎赢了（被get，调用afterNodeAccess排到末尾去）
            runFast.get("5号选手");// 杨五郎赢了
    
    
            System.out.println();
            runFast.put("7号选手", "杨七郎");
            runFast.put("8号选手", "杨业");
    
    
            System.out.println("第三局跑得快参与人：");// 四郎、六郎出局
            for (Map.Entry<String, String> map:entries){ 
                System.out.print(map.getKey()+"---------"+map.getValue()+" ");
            }
            System.out.println();
        }
    }

## 核心思想 ##

1、构造LinkedHashMap时accessOrder传true  
  
2、LinkedHashMap特性，元素在被访问时，accessOrder为true，会进行重排序

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;
        }

afterNodeAccess，将元素排到最后

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;
            }
        }

3、覆写LinkedHashMap的removeEldestEntry方法，写自己的触发removeEldestEntry逻辑，什么情况下将**最近最少使用**元素移除，即双向链表的头部元素

我这里是只要内部元素大于4个就移除  
  
  
移除逻辑源代码在LinkedHashMap中

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);
            }
        }

而removeNode还是HashMap的

/** * Implements Map.remove and related methods. * * @param hash hash for key * @param key the key * @param value the value to match if matchValue, else ignored * @param matchValue if true only remove if value is equal * @param movable if false do not move other nodes while removing * @return the node, or null if none */
        final Node<K,V> removeNode(int hash, Object key, Object value,
                                   boolean matchValue, boolean movable) { 
            Node<K,V>[] tab; Node<K,V> p; int n, index;
            if ((tab = table) != null && (n = tab.length) > 0 &&
                (p = tab[index = (n - 1) & hash]) != null) { 
                Node<K,V> node = null, e; K k; V v;
                if (p.hash == hash &&
                    ((k = p.key) == key || (key != null && key.equals(k))))
                    node = p;
                else if ((e = p.next) != null) { 
                    if (p instanceof TreeNode)
                        node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
                    else { 
                        do { 
                            if (e.hash == hash &&
                                ((k = e.key) == key ||
                                 (key != null && key.equals(k)))) { 
                                node = e;
                                break;
                            }
                            p = e;
                        } while ((e = e.next) != null);
                    }
                }
                if (node != null && (!matchValue || (v = node.value) == value ||
                                     (value != null && value.equals(v)))) { 
                    if (node instanceof TreeNode)
                        ((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
                    else if (node == p)
                        tab[index] = node.next;
                    else
                        p.next = node.next;
                    ++modCount;
                    --size;
                    afterNodeRemoval(node);
                    return node;
                }
            }
            return null;
        }

先进先出，有点类似栈

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xlaXN1cmVfbGlmZQ_size_16_color_FFFFFF_t_70_pic_center 1]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xlaXN1cmVfbGlmZQ_size_16_color_FFFFFF_t_70_pic_center]: /images/20221123/6fcd5001f6fd48868f70bffc5cc1bbcd.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xlaXN1cmVfbGlmZQ_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221123/a1b5359546bd4adcb99e7ccfec62948b.png