为啥要说到这个呢，因为它是实现LRU算法的比较方便的类，同时它的实现也依赖hashmap，而hashmap是Map里面使用最频繁的类。所以分析它非常有意义。 我们可以从LRU算法角度来分析LMM的基础功能。首先温习下LRU淘汰算法： lru缓存淘汰算法:该算法师根据数据的历史访问记录来进行淘汰数据,思想,如果该数据最近倍访问过,那么将来的访问率也比较高 实现思想：如果该数据已经存在我们的链表中,经过一次遍历,找到到该元素,需要将该数据放到链表的头部 如果该数据不在链表中,此时链表有足够的空间,将该数据放到链表的头部即可,如果该链表的数据已经满了，则删除链表尾的数据.,这腾出存储空间,将该数据放到链表的头部,总之lru核心思想是将最近最少使用的数据放到链表的尾部,如果存储空间不足的时候,淘汰即可,链表的头部总是存放最近使用率最频繁的数据.（转载自：https://blog.csdn.net/w5201314ws6123/article/details/85806213） 那么我们先从初始化来分析吧。
public LinkedHashMap( int initialCapacity, float loadFactor, boolean accessOrder) { //直接调用HashMap的构造方法。 super(initialCapacity, loadFactor); init(); //accessOrder 如果LRU 算法的话，应该为true。 this.accessOrder = accessOrder; }init() { header = new LinkedEntry<K, V>(); } 初始头部header节点也就是root节点。这是一个双向循环链表，拥有nxt，prev,并且继承自HashMapEntry。 那么我们从put，get，还有迭代方法来分析LinkedHashMap的核心。 JDK 1.8中并没有put的方法是调用的HashMap的put，里面会addNewEntry。所以LLM重写了此方法。
void addNewEntry(K key, V value, int hash, int index) { LinkedEntry<K, V> header = this.header; //注意此处，意思是否需要将header.nxt 指向的节点删除，如果不是初始化的header，eldest!=header 会成立。但是removeEldestEntry 这个需要实现LRU算法的子类来实现。其实就是判断，目前的size是否太大，需要删除header.nxt,以便链表能够插入新的Entry. // Remove eldest entry if instructed to do so. LinkedEntry<K, V> eldest = header.nxt; if (eldest != header && removeEldestEntry(eldest)) { remove(eldest.key); } // Create new entry, link it on to list, and put it into table LinkedEntry<K, V> oldTail = header.prv; LinkedEntry<K, V> newTail = new LinkedEntry<K,V>( key, value, hash, table[index], header, oldTail); //此处实际上是将newTail插入到header头部。由于是循环链表，old6Tail.nxt= newTail。实际上LRU算法说简单点就是根据访问循序来的，但是实际上插入顺序也是默认的执行。 table[index] = oldTail.nxt = header.prv = newTail; }现在看看这个get方法。
public V get(Object key) { /* * This method is overridden to eliminate the need for a polymorphic * invocation in superclass at the expense of code duplication. */ if (key == null) { HashMapEntry<K, V> e = entryForNullKey; if (e == null) return null; if (accessOrder) makeTail((LinkedEntry<K, V>) e); return e.value; } int hash = Collections.secondaryHash(key); HashMapEntry<K, V>[] tab = table; for (HashMapEntry<K, V> e = tab[hash & (tab.length - 1)]; e != null; e = e.next) { K eKey = e.key; if (eKey == key || (e.hash == hash && key.equals(eKey))) { if (accessOrder) makeTail((LinkedEntry<K, V>) e); return e.value; } } return null; }核心实际就是 makeTail((LinkedEntry<K, V>) e);。这个方法会将get到的LinkedEntry 移动到head头部。看方法。
private void makeTail(LinkedEntry<K, V> e) { //首先将e的unlik，实际就是先删除e。 // Unlink e e.prv.nxt = e.nxt; e.nxt.prv = e.prv; //然后将e放入到头部。这个在put里面的算法一样就不分析了。 // Relink e as tail LinkedEntry<K, V> header = this.header; LinkedEntry<K, V> oldTail = header.prv; e.nxt = header; e.prv = oldTail; oldTail.nxt = header.prv = e; modCount++; }大家可以看到如果accessOrder 为true，get的时候会将get到的值放入头部这么做实际就是LRU算法。也可以叫做缓存算法。这样做的目的其实就是因为缓存容量优先，我们需要把最少使用的item放置到末尾，然后进行删除，这样cache维护的都是一些访问比较频繁的数据。这样当我们需要使用缓存的时候，首先可以直接到cache里面get，由于缓存存储的都是一些教频繁的数据，我们有一定的概率能够get到，那么如果命中那么就直接拿到对象了，不用再new了。这就是LRU算法思想，android开发里面大量使用了这种思想。而LinkedHashMap就是非常方便的实现这种算法的了。
