LRUMAP 原理解析

作者：Charles，转载时请指明作者出处

背景：

在JDK的集合结构里面，我们用各种各样的map结构，例如HashMap,TreeMap,LInkedHashMap. ConcurrentHashMap等，不同的Map结构实际上是一种特殊的数据结构，来满足我们实际的业务需求，今天给大家介绍一种LRUMAP的实现。

Map 主要是实现快速随机的存储的key-value映射的结构，而LRUMAP是在有限的集合里面，

如果存储的时候，集合超出了限制，那么就淘汰最近最少使用的数据，实际上是一种资源调度的算法。操作系统的内存管理实际上就是一种LRU调度，在我们的程序中，如果想使用本地缓存来实现LRU的调度，使用apache common-collections框架中的LRUMAP不失为一种很好的选择，我们来分析下LRUMAP的实现原理。

使用方法：

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 recentused
    lruMap.put("a3", "3");
    System.out.println(lruMap);
}
1
2
3
4
5
6
7
8

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

{a1=1,a3=3}

实现原理:

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

LRUMap的使用说明如下：

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

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

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

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

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

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

作来保证线程安全。

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

1.get操作

public Object get(Object key) {
        LinkEntry entry = (LinkEntry) getEntry(key);
        if (entry == null) {
            return null;
        }
        moveToMRU(entry);//执行LRU操作
        return entry.getValue();
    }          
1
2
3
4
5
6
7
8

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)");
        }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

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 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);
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

当集合的个数超过指定的最大个数时，会调用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 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.");
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

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

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

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

    /**
     * Adds an entry into this map, maintaining insertion order.
     * 

     * 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;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

总结:

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