LRUMap 源代码实现解读

引自：http://www.blogjava.net/xmatthew/archive/2012/06/28/380150.html
jar包下载地址：
http://commons.apache.org/proper/commons-collections/download_collections.cgi?Preferred=http%3A%2F%2Fmirror.bit.edu.cn%2Fapache%2F

本文通过对Apache Commons Collections 项目中LRUMap这个集合类的源代码进行详细解读，为帮助大家更好的了解这个集合类的实现原理以及使用如何该集合类。

首先介绍一下LRU算法. LRU是由Least Recently Used的首字母组成，表示最近最少使用的含义，一般使用在对象淘汰算法上。也是比较常见的一种淘汰算法。



LRUMap 则是实现的LRP算法的Map集合类，它继承于AbstractLinkedMap 抽象类。LRUMap的使用说明如下：

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

那么那些操作会影响元素的使用情况：

1.       put 当新增加一个集合元素对象，则表示该对象是最近被访问的

2.       get 操作会把当前访问的元素对象作为最近被访问的，会被移到链接表头

注：当执行containsKey和containsValue操作时，不会影响元素的访问情况。

               LRUMap也是非线程安全。在多线程下使用可通过 Collections.synchronizedMap(Map)操作来保证线程安全。



LRUMap的一个简单使用示例：

    public static void main(String[] args) {

       

        LRUMap lruMap = new LRUMap(2);

       

        lruMap.put("a1", "1");

        lruMap.put("a2", "2");

        lruMap.get("a1");//mark as recent used

        lruMap.put("a3", "3");

        System.out.println(lruMap);

    }

               上面的示例，当增加”a3”值时，会淘汰最近最少使用的”a2”, 最后输出的结果为：

                                   {a1=1, a3=3}



下面根据LRUMap的源码来解读一下LRUMap的实现原理

整体类图


LRUMap类的关键代码说明如下：

1.       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 [e-mail])");

        }

    }

2.       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 [e-mail] 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 [e-mail] 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更新为新加入的值，并再次加入到链接表中，并重新排定次序。

reuseMapping函数代码如下：

    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 [e-mail] 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 [e-mail] as a bug.");

        }

    }

    上面的代码中：

          removeEntry 方法是删除最近最少使用的节点在链接中的引用

    reuseEntry方法则把该节点的key和value赋新加入的节点的key和value值

    addEntry 方法则把该节点加入到链接表，并保障相关的链接顺序

    /**

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

 }

       LRUMap的主要源码实现就解读到这里，实现思路还是比较好理解的。

LRUMap的使用场景会比较多，例如可以很方便的帮我们实现基于内存的 LRU 缓存服务实现。