LRUMap解析

LRU 是 Least Recently Used 的缩写，即最近最少使用，是一种常用的数据淘汰算法，选择最近最久未使用的数据予以淘汰。 LRUMap 可以保存指定数量的固定的数据，并且它会按照 LRU 算法，帮你清除最不常用的数据。

示例：
幂等性判断

实现原理

LRUMap则是实现的LRP算法的Map集合类，它继承于AbstractLinkedMap抽象类。

LRUMap的初始化时需要指定最大集合元素个数，新增的元素个数大于允许的最大集合个数时，则会执行LRU淘汰算法。所有的元素在LRUMap中会根据最近使用情况进行排序。最近使用的会放在元素的最前面(LRUMap是通过链表来存储元素内容). 所以LRUMap进行淘汰时只需要删除链表最后一个即可（即header.after所指的元素对象）
那么那些操作会影响元素的使用情况：

1. put 当新增加一个集合元素对象，则表示该对象是最近被访问的
2. get 操作会把当前访问的元素对象作为最近被访问的，会被移到链接表头

注：当执行containsKey和containsValue操作时，不会影响元素的访问情况。
LRUMap也是非线程安全。在多线程下使用可通过Collections.synchronizedMap(Map)操作来保证线程安全。

get操作

public Object get(Object key) {
        LinkEntry entry = (LinkEntry) getEntry(key);
        if (entry == null) {
            return null;
        }
        moveToMRU(entry);//执行LRU操作
        return entry.getValue();
    }         
//moveToMRU方法代码如下：
 protected void moveToMRU(LinkEntry entry) {
        if (entry.after != header) {
            modCount++;
            // remove 从链接中移除当前点
            entry.before.after = entry.after;
            entry.after.before = entry.before;
            // add first 把节点增加到链接头部
            entry.after = header;
            entry.before = header.before;
            header.before.after = entry;
            header.before = entry;
        } else if (entry == header) {
            throw new IllegalStateException("Can't move header to MRU" +
                " (please report this to commons-dev@jakarta.apache.org)");
        }
}

put操作

//由于继承的AbstractLinkedMap，所以put操作会调用addMapping方法，代码如下：
    protected void addMapping(int hashIndex, int hashCode, Object key, Object value) {
        if (isFull()) {
            LinkEntry reuse = header.after;
            boolean removeLRUEntry = false;
            if (scanUntilRemovable) {
                while (reuse != header && reuse != null) {
                    if (removeLRU(reuse)) {
                        removeLRUEntry = true;
                        break;
                    }
                    reuse = reuse.after;
                }
                if (reuse == null) {
                    throw new IllegalStateException(
                        "Entry.after=null, header.after" + header.after + " header.before" + header.before +
                        " key=" + key + " value=" + value + " size=" + size + " maxSize=" + maxSize +
                        " Please check that your keys are immutable, and that you have used synchronization properly." +
                        " If so, then please report this to commons-dev@jakarta.apache.org as a bug.");
                }
            } else {
                removeLRUEntry = removeLRU(reuse);
            }
            if (removeLRUEntry) {
                if (reuse == null) {
                    throw new IllegalStateException(
                        "reuse=null, header.after=" + header.after + " header.before" + header.before +
                        " key=" + key + " value=" + value + " size=" + size + " maxSize=" + maxSize +
                        " Please check that your keys are immutable, and that you have used synchronization properly." +
                        " If so, then please report this to commons-dev@jakarta.apache.org as a bug.");
                }
                reuseMapping(reuse, hashIndex, hashCode, key, value);
            } else {
                super.addMapping(hashIndex, hashCode, key, value);
            }
        } else {
            super.addMapping(hashIndex, hashCode, key, value);
        }
    }
//当集合的个数超过指定的最大个数时，会调用reuseMapping函数，把要删除的对象的key和value更新为新加入的值，并再次加入到链接表中，并重新排定次序
    protected void reuseMapping(LinkEntry entry, int hashIndex, int hashCode, Object key, Object value) {
        // find the entry before the entry specified in the hash table
        // remember that the parameters (except the first) refer to the new entry,
        // not the old one
        try {
            int removeIndex = hashIndex(entry.hashCode, data.length);
            HashEntry[] tmp = data;  // may protect against some sync issues
            HashEntry loop = tmp[removeIndex];
            HashEntry previous = null;
            while (loop != entry && loop != null) {
                previous = loop;
                loop = loop.next;
            }
            if (loop == null) {
                throw new IllegalStateException(
                    "Entry.next=null, data[removeIndex]=" + data[removeIndex] + " previous=" + previous +
                    " key=" + key + " value=" + value + " size=" + size + " maxSize=" + maxSize +
                    " Please check that your keys are immutable, and that you have used synchronization properly." +
                    " If so, then please report this to commons-dev@jakarta.apache.org as a bug.");
            }
            // reuse the entry
            modCount++;
            removeEntry(entry, removeIndex, previous);
            reuseEntry(entry, hashIndex, hashCode, key, value);
            addEntry(entry, hashIndex);
        } catch (NullPointerException ex) {
            throw new IllegalStateException(
                    "NPE, entry=" + entry + " entryIsHeader=" + (entry==header) +
                    " key=" + key + " value=" + value + " size=" + size + " maxSize=" + maxSize +
                    " Please check that your keys are immutable, and that you have used synchronization properly." +
                    " If so, then please report this to commons-dev@jakarta.apache.org as a bug.");
        }
    }
    /**
     * Adds an entry into this map, maintaining insertion order.
     * <p>
     * This implementation adds the entry to the data storage table and
     * to the end of the linked list.
     * 
     * @param entry  the entry to add
     * @param hashIndex  the index into the data array to store at
     */
    protected void addEntry(HashEntry entry, int hashIndex) {
        LinkEntry link = (LinkEntry) entry;
        link.after  = header;
        link.before = header.before;
        header.before.after = link;
        header.before = link;
        data[hashIndex] = entry;
    }

removeEntry 方法是删除最近最少使用的节点在链接中的引用
reuseEntry方法则把该节点的key和value赋新加入的节点的key和value值
addEntry方法则把该节点加入到链接表，并保障相关的链接顺序