LinkedHashMap 排序模式accessOrder-----LRU算法

在看LinkedHashMap源码时，可以发现读取操作的get（）方法很有意思。

代码如下

public V get(Object key) {
        Entry<K,V> e = (Entry<K,V>)getEntry(key);
        if (e == null)
            return null;
        e.recordAccess(this);
        return e.value;
    }
           

调用了redordAccess（）方法，代码如下：

void recordAccess(HashMap<K,V> m) {
            LinkedHashMap<K,V> lm = (LinkedHashMap<K,V>)m;
            if (lm.accessOrder) {
                lm.modCount++;
                remove();
                addBefore(lm.header);
            }
        }
           

判断accessOrder为true，就把当前操作的元素放到链表的第一位。

排序模式accessOrder，属性时布尔，对于访问操作其值为true，插入操作为false。也就是当get（Object key）时，将最新访问的元素放到双向链表的第一位。

引出了该哈希映射的迭代顺序就是最后访问其条目的顺序，也就很适合构建LRU缓存。

LRU算法 ：LRU（Least recently used，最近最少使用）算法根据数据的历史访问记录来进行淘汰数据，其核心思想是“如果数据最近被访问过，那么将来被访问的几率也更高

又知道，每次addEntry（）后都会调用removeEldestEntry（）方法

void addEntry(int hash, K key, V value, int bucketIndex) {
        super.addEntry(hash, key, value, bucketIndex);

        // Remove eldest entry if instructed
        Entry<K,V> eldest = header.after;
        //调用了默认返回false的removeEldestEntry（）
        if (removeEldestEntry(eldest)) {
            removeEntryForKey(eldest.key);
        }
    }

  protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
      //默认返回false
        return false;
    }
           

只需要稍作修改就可以构建一个有稳定状态的，每次添加新条目都会淘汰最旧条目的映射。