一、前言
前段时间研究了memcached，而且操作系统的课程也刚刚完成，在两个里面多次出现LRU（last recently used最近最少使用）算法，虽然思想很简单。但是还是值得我们研究，无意间在看LinkedHashMap的源码的时候看见貌似这个类里面有默认的LRU实现。我们现在就来分析一下他的源代码
/*** Returns <tt>true</tt> if this map should remove its eldest entry.* This method is invoked by <tt>put</tt> and <tt>putAll</tt> after* inserting a new entry into the map. It provides the implementor* with the opportunity to remove the eldest entry each time a new one* is added. This is useful if the map represents a cache: it allows* the map to reduce memory consumption by deleting stale entries.** <p>Sample use: this override will allow the map to grow up to 100* entries and then delete the eldest entry each time a new entry is* added, maintaining a steady state of 100 entries.* <pre>*private static final int MAX_ENTRIES = 100;**protected boolean removeEldestEntry(Map.Entry eldest) {*return size() > MAX_ENTRIES;*}* </pre>** <p>This method typically does not modify the map in any way,* instead allowing the map to modify itself as directed by its* return value. It <i>is</i> permitted for this method to modify* the map directly, but if it does so, it <i>must</i> return* <tt>false</tt> (indicating that the map should not attempt any* further modification). The effects of returning <tt>true</tt>* after modifying the map from within this method are unspecified.** <p>This implementation merely returns <tt>false</tt> (so that this* map acts like a normal map – the eldest element is never removed).** @param eldest The least recently inserted entry in the map, or if*this is an access-ordered map, the least recently accessed*entry. This is the entry that will be removed it this*method returns <tt>true</tt>. If the map was empty prior*to the <tt>put</tt> or <tt>putAll</tt> invocation resulting*in this invocation, this will be the entry that was just*inserted; in other words, if the map contains a single*entry, the eldest entry is also the newest.* @return <tt>true</tt> if the eldest entry should be removed*from the map; <tt>false</tt> if it should be retained.*/protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {return false;//返回false代表不会删除map会自动扩容，返回true代表会删除}很明显，上一个函数写得很清楚，该函数数默认返回false的，代表linkedhashmap会自动的进行扩容操作，如果返回true的话map则会删掉排在最后的一个元素（linkedhashmap是有序的）我们可以来看看addENtry函数是怎样的
/*** This override alters behavior of superclass put method. It causes newly* allocated entry to get inserted at the end of the linked list and* removes the eldest entry if appropriate.*/void addEntry(int hash, K key, V value, int bucketIndex) {createEntry(hash, key, value, bucketIndex);// Remove eldest entry if instructed, else grow capacity if appropriateEntry<K,V> eldest = header.after;if (removeEldestEntry(eldest)) {//返回true，删掉entryremoveEntryForKey(eldest.key);} else {//否则自动两倍扩容if (size >= threshold)resize(2 * table.length);}}那么现在就剩下排序的问题了，大家都知道LRU的原理就是把最近使用的排在前面，最少使用的排在后面（addENTRY时会删除多余的元素），那么linkedhashmap是在什么时候开始为最近使用的排序呢？很明显我们要知道他什么时候使用就应该是i我们调用get方法的时候，那我们现在来看看get方法
/*** Returns the value to which the specified key is mapped,* or {@code null} if this map contains no mapping for the key.** <p>More formally, if this map contains a mapping from a key* {@code k} to a value {@code v} such that {@code (key==null ? k==null :* key.equals(k))}, then this method returns {@code v}; otherwise* it returns {@code null}. (There can be at most one such mapping.)** <p>A return value of {@code null} does not <i>necessarily</i>* indicate that the map contains no mapping for the key; it's also* possible that the map explicitly maps the key to {@code null}.* The {@link #containsKey containsKey} operation may be used to* distinguish these two cases.*/public V get(Object key) {Entry<K,V> e = (Entry<K,V>)getEntry(key);//取得entry，if (e == null)return null;e.recordAccess(this);//这个方法很重要return e.value;}还有一点笔者必须要提醒大家，我们传入参数的时候有个这个参数accessOrder，顾名思义，他是为了排序而生。true代表排序。false反之
/*** The iteration ordering method for this linked hash map: <tt>true</tt>* for access-order, <tt>false</tt> for insertion-order.** @serial*/private final boolean accessOrder;我们可以看到。当我们执行get方法的时候会调用一个recordAccess的方法传入this变量。ok，他应该是把操作交给entry类了吧。好吧我们来看看entry的源代码
/*** LinkedHashMap entry.*/private static class Entry<K,V> extends HashMap.Entry<K,V> {// These fields comprise the doubly linked list used for iteration.Entry<K,V> before, after;Entry(int hash, K key, V value, HashMap.Entry<K,V> next) {super(hash, key, value, next);}/*** Removes this entry from the linked list.*/private void remove() {//删除该entrybefore.after = after;after.before = before;}/*** Inserts this entry before the specified existing entry in the list.//加入到头部*/private void addBefore(Entry<K,V> existingEntry) {after = existingEntry;before = existingEntry.before;before.after = this;after.before = this;}/*** This method is invoked by the superclass whenever the value* of a pre-existing entry is read by Map.get or modified by Map.set.* If the enclosing Map is access-ordered, it moves the entry* to the end of the list; otherwise, it does nothing.*/void recordAccess(HashMap<K,V> m) {LinkedHashMap<K,V> lm = (LinkedHashMap<K,V>)m;if (lm.accessOrder) {//得到传过来的linkedhashmap的order值。如果是true这进行一下操作，，先执行remove（）接着执行addbefore()lm.modCount++;//根据方法名字大家都应该恍然大悟了吧remove();addBefore(lm.header);}}void recordRemoval(HashMap<K,V> m) {remove();}}ok！linkedHashmap的Lru实现就是这么简单，但是个人认为不算很完美的LRU，大家有没有看到一个弊端，只要调用一次就跑到最前面去了，我觉得这不是一个很好的实现。
下面给出一个自己实现的一个简单的LRUCache类
真凉爽啊！青山绿水映入我的眼中，景色怡人啊！
