（1）.LRU算法
百度百科中对LRU算法的解释如下：
LRU是（Least Recently Used）近期最少使用算法。
其实就是把近期最少使用的内容淘汰出局。LRU是一种缓存算法，在空间有限的情况下，把使用频率最低的内容淘汰出缓存，让使用频率高的内容留在缓存里。
（2）在看项目框架的代码时，看到了LRUMap这个类，是apache-commons下的类，由于是第一次听说LRU算法，所以就决定研究一下它的源码。
（3）先来看一下例子：
1 public class TestLRUMap { 2 public static void main(String[] args) { 3 LRUMap<Integer, Integer> map = new LRUMap<Integer, Integer>(3); 4 map.put(1, 1); 5 map.put(2, 2); 6 map.put(3, 3); 7 map.put(4, 4); 8 System.out.println(map); 9 } 10 }
输出：{2=2, 3=3, 4=4}
增加一行代码，再看结果：
1 public class TestLRUMap { 2 public static void main(String[] args) { 3 LRUMap<Integer, Integer> map = new LRUMap<Integer, Integer>(3); 4 map.put(1, 1); 5 map.put(2, 2); 6 map.put(3, 3); 7 map.get(1); 8 map.put(4, 4); 9 System.out.println(map); 10 } 11 }
输出：{3=3, 1=1, 4=4}
两个结果为什么不一样呢？因为第二个例子，我们添加了一行代码：map.get(1);代表1元素是最新使用的，而相应的2就是最长时间没有使用的元素，而map的长度又限制为3，所以2就被删掉了。
（4）下面分析源码：
首先看get方法：
1 public V get(final Object key) { 2 final LinkEntry<K, V> entry = getEntry(key); 3 if (entry == null) { 4 return null; 5 } 6 //主要看这个方法 7 moveToMRU(entry); 8 return entry.getValue(); 9 }
moveToMRUst方法：
1 protected void moveToMRU(final LinkEntry<K, V> entry) { 2 if (entry.after != header) { 3 modCount++; 4 // remove 5 if(entry.before == null) { 6 throw new IllegalStateException("Entry.before is null." + 7 " Please check that your keys are immutable, and that you have used synchronization properly." + 8 " If so, then please report this to [email protected] as a bug."); 9 } 10 //其实就是链表指正的改变，使得被get的元素排到链表中header前面 11 entry.before.after = entry.after; 12 entry.after.before = entry.before; 13 // add first 14 entry.after = header; 15 entry.before = header.before; 16 header.before.after = entry; 17 header.before = entry; 18 } else if (entry == header) { 19 throw new IllegalStateException("Can't move header to MRU" + 20 " (please report this to [email protected])"); 21 } 22 }
接下来看put方法：
1 public V put(final K key, final V value) { 2 //如果key为null，则将其转换为new Object() 3 final Object convertedKey = convertKey(key); 4 //获得key的hashCode 5 final int hashCode = hash(convertedKey); 6 //根据hashCode得到其所在数组中的下标 7 final int index = hashIndex(hashCode, data.length); 8 //获得数组对应下标的HashEntry对象 9 HashEntry<K, V> entry = data[index]; 10 while (entry != null) { 11 //如果entry不为空，则判断是否已经有相同key的元素存在 12 if (entry.hashCode == hashCode && isEqualKey(convertedKey, entry.key)) { 13 //判断是否有相同的key存在，如果有相同的key存在，则替换其值，但不会改变其在链表中的位置 14 final V oldValue = entry.getValue(); 15 updateEntry(entry, value); 16 return oldValue; 17 } 18 entry = entry.next; 19 } 20 //如果entry为空，说明这个下标上还没有HashEntry对象 21 addMapping(index, hashCode, key, value); 22 return null; 23 } 24 25 26 protected void addMapping(final int hashIndex, final int hashCode, final K key, final V value) { 27 //如果map已满，则执行删除到目前为止最长时间没有使用的元素 28 if (isFull()) { 29 //由于LRUMap每次添加元素的时候都放在链表中header的前面，所以，header后面的元素是删除的对象 30 LinkEntry<K, V> reuse = header.after; 31 boolean removeLRUEntry = false; 32 if (scanUntilRemovable) { 33 while (reuse != header && reuse != null) { 34 if (removeLRU(reuse)) { 35 removeLRUEntry = true; 36 break; 37 } 38 reuse = reuse.after; 39 } 40 if (reuse == null) { 41 throw new IllegalStateException( 42 "Entry.after=null, header.after" + header.after + " header.before" + header.before + 43 " key=" + key + " value=" + value + " size=" + size + " maxSize=" + maxSize + 44 " Please check that your keys are immutable, and that you have used synchronization properly." + 45 " If so, then please report this to [email protected] as a bug."); 46 } 47 } else { 48 removeLRUEntry = removeLRU(reuse); 49 } 50 51 if (removeLRUEntry) { 52 if (reuse == null) { 53 throw new IllegalStateException( 54 "reuse=null, header.after=" + header.after + " header.before" + header.before + 55 " key=" + key + " value=" + value + " size=" + size + " maxSize=" + maxSize + 56 " Please check that your keys are immutable, and that you have used synchronization properly." + 57 " If so, then please report this to [email protected] as a bug."); 58 } 59 //执行LRUMap的reuseMapping方法 60 reuseMapping(reuse, hashIndex, hashCode, key, value); 61 } else { 62 super.addMapping(hashIndex, hashCode, key, value); 63 } 64 } else { 65 super.addMapping(hashIndex, hashCode, key, value); 66 } 67 } 68 69 70 protected void reuseMapping(final LinkEntry<K, V> entry, final int hashIndex, final int hashCode, 71 final K key, final V value) { 72 // find the entry before the entry specified in the hash table 73 // remember that the parameters (except the first) refer to the new entry, 74 // not the old one 75 try { 76 //获得删除元素在数组中的下标 77 final int removeIndex = hashIndex(entry.hashCode, data.length); 78 final HashEntry<K, V>[] tmp = data; // may protect against some sync issues 79 HashEntry<K, V> loop = tmp[removeIndex]; 80 HashEntry<K, V> previous = null; 81 //loop的作用是防止map被其他线程修改了导致要删除的元素已经被其他线程给删了 82 while (loop != entry && loop != null) { 83 previous = loop; 84 loop = loop.next; 85 } 86 if (loop == null) { 87 throw new IllegalStateException( 88 "Entry.next=null, data[removeIndex]=" + data[removeIndex] + " previous=" + previous + 89 " key=" + key + " value=" + value + " size=" + size + " maxSize=" + maxSize + 90 " Please check that your keys are immutable, and that you have used synchronization properly." + 91 " If so, then please report this to [email protected] as a bug."); 92 } 93 94 // reuse the entry 95 modCount++; 96 removeEntry(entry, removeIndex, previous); 97 reuseEntry(entry, hashIndex, hashCode, key, value); 98 addEntry(entry, hashIndex); 99 } catch (final NullPointerException ex) { 100 throw new IllegalStateException( 101 "NPE, entry=" + entry + " entryIsHeader=" + (entry==header) + 102 " key=" + key + " value=" + value + " size=" + size + " maxSize=" + maxSize + 103 " Please check that your keys are immutable, and that you have used synchronization properly." + 104 " If so, then please report this to [email protected] as a bug."); 105 } 106 }
好了，通过源码分析，终于理解了LRUMap是怎么实现LRU算法的。
原创文章，作者：Maggie-Hunter，如若转载，请注明出处：https://blog.ytso.com/19414.html