本文主要内容
- LinkedHashMap运用
- LinkedHashMap源码解析
- Lru算法
今天计划看看android的图片缓存相关知识点，没想到引申到了LinkedHashMap容器了。
LinkedHashMap承继HashMap，相比于HashMap的无序，它是有序的，乃至它还能根据拜访次序输出内部存储元素，正是因为此特性，Lru（近期最少运用）算法一般由LinkedHashMap完成，特别合适缓存算法。
LinkedHashMap运用
先来看看LinkedHashMap是怎么运用的，以及它的奇特效果。
public class Lru<K, V> extends LinkedHashMap<K, V> {
public Lru(int initialCapacity,
float loadFactor,
boolean accessOrder){
super(initialCapacity, loadFactor, accessOrder);
}
@Override
protected boolean removeEldestEntry(java.util.Map.Entry<K, V> eldest) {
if(size() > 6){
return true;
}
return false;
}
public static void main(String[] args) {
Lru<Character, Integer> lru = new Lru<Character, Integer>(16, 0.75f, true);
String s = "abcdefghijkl";
for (int i = 0; i < s.length(); i++) {
lru.put(s.charAt(i), i);
}
System.out.println("LRU中key为h的Entry的值为： " + lru.get('h'));
System.out.println("LRU的巨细 ：" + lru.size());
System.out.println("LRU ：" + lru);
}
}
它的输出成果是：
LRU中key为h的Entry的值为： 7
LRU的巨细 ：6
LRU ：{g=6, i=8, j=9, k=10, l=11, h=7}
代码中的结构办法，前两个在HashMap中见过，可参照HashMap源码解析阅览。终究一个参数，accessOrder，十分奇特。
accessOrder，表明LinkedHashMap不按照刺进次序排序，而是按照拜访次序排序。
联络上述代码的输出成果，h落在了终究，这便是accessOrder元素的效果。
值得一提的是，HashMap就无序的，因为HashMap内的元素在数组中的方位是由元素的hash值决议的，并不是先刺进就在方位的前面。但LinkedHashMap是有序的，默许按刺进次序排序。
那么，为什么LinkedHashMap这么奇特呢？
LinkedHashMap源码解析
LinkedHashMap中申明了两个成员变量：
private transient Entry<K,V> header;
private final boolean accessOrder;
而且LinkedHashMap对Entry也重写了，Entry类中增加了两个成员变量 before， after。
private static class Entry<K,V> extends HashMap.Entry<K,V> {
Entry<K,V> before, after;
}
从上边来看，LinkedHashMap不但承继了父类运用数组存储元素，hash定位，自己内部还保存着一个双向链表，正是因为此双向链表的存在，LinkedHashMap才干有序。
我们来看它的put办法，不过LinkedHashMap并没有重写put办法，所以它的刺进办法依然同HashMap一致：
//HashMap的put办法
public V put(K key, V value) {
//省掉中间进程
addEntry(hash, key, value, i);
}
但LinkedHashMap重写了addEntry办法：
void addEntry(int hash, K key, V value, int bucketIndex) {
createEntry(hash, key, value, bucketIndex);
// Remove eldest entry if instructed, else grow capacity if appropriate
Entry<K,V> eldest = header.after;
if (removeEldestEntry(eldest)) {
removeEntryForKey(eldest.key);
} else {
if (size >= threshold)
resize(2 * table.length);
}
}
查看createEntry办法：
void createEntry(int hash, K key, V value, int bucketIndex) {
HashMap.Entry<K,V> old = table[bucketIndex];
Entry<K,V> e = new Entry<>(hash, key, value, old);
table[bucketIndex] = e;
e.addBefore(header);
size++;
}
乍一看和HashMap很类似，但它额定调用了addBefore办法：
private void addBefore(Entry<K,V> existingEntry) {
after = existingEntry;
before = existingEntry.before;
before.after = this;
after.before = this;
}
LinkedHashMap在初始化的时分，初始化header节点，header节点的after和before都是它自己。
void init() {
header = new Entry<>(-1, null, null, null);
header.before = header.after = header;
}
假如先后增加元素key0和key1，那么根据addBefore的逻辑，终究的连接状况如下：
假如 accessOrder 值为true时，当用户调用get办法时：
public V get(Object key) {
Entry<K,V> e = (Entry<K,V>)getEntry(key);
if (e == null)
return null;
e.recordAccess(this);
return e.value;
}
void recordAccess(HashMap<K,V> m) {
LinkedHashMap<K,V> lm = (LinkedHashMap<K,V>)m;
if (lm.accessOrder) {
lm.modCount++;
remove();
addBefore(lm.header);
}
}
假如accessOrder为true，那么会将此节点本来的after和before节点重置，终究调用addBefore办法，节点位于双向链表的终究一位，类似于上图中的 key1。
回顾第1节关于LinkedHashMap的运用，终究打印LinkedHashMap，其实便是调用LinkedHashMap的toString办法，元素的排序十分有意思。
LinkedHashMap的toString办法是定义在AbstractMap类中：
//AbstractMap的toString办法
public String toString() {
Iterator<Entry<K,V>> i = entrySet().iterator();
if (! i.hasNext())
return "{}";
StringBuilder sb = new StringBuilder();
sb.append('{');
for (;;) {
Entry<K,V> e = i.next();
K key = e.getKey();
V value = e.getValue();
sb.append(key == this ? "(this Map)" : key);
sb.append('=');
sb.append(value == this ? "(this Map)" : value);
if (! i.hasNext())
return sb.append('}').toString();
sb.append(',').append(' ');
}
}
//HashMap类
//HashMap类中的newEntryIterator办法，回来一个Iterator对象
public Iterator<Map.Entry<K,V>> iterator() {
return newEntryIterator();
}
//LinkedHashMap类
//LinkedHashMap重写newEntryIterator办法，回来自己的Iterator对象，以便于契合自己风格的遍历
Iterator<Map.Entry<K,V>> newEntryIterator() { return new EntryIterator(); }
private class EntryIterator extends LinkedHashIterator<Map.Entry<K,V>> {
//LinkedHashMap回来的Iterator，终究调用nextEntry办法，完成Iterator接口，完成遍历
public Map.Entry<K,V> next() { return nextEntry(); }
}
//以下代码是LinkedHashIterator类中的，初始化的nextEntry指向header的after
Entry<K,V> nextEntry = header.after;
//nextEntry办法，便是在回来nextEntry对象的after节点
Entry<K,V> nextEntry() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
if (nextEntry == header)
throw new NoSuchElementException();
Entry<K,V> e = lastReturned = nextEntry;
nextEntry = e.after;
return e;
}
查看完以上代码，发现LinkedHashMap终究遍历时，其实是以header为第1个节点，不停地向后遍历after节点，所以第1章中发生的成果就会是那样，先刺进的先显现出来，后刺进的后显现，假如accessOrder为true，那么调用get办法得到的元素也会被刺进到链表尾部，它也会被终究遍历。
Lru算法
Lru算法，便是 Least recently used，最近最少运用。运用LinkedHashMap能够容易完成此算法。
当LinkedHashMap增加元素时：
void addEntry(int hash, K key, V value, int bucketIndex) {
createEntry(hash, key, value, bucketIndex);
// Remove eldest entry if instructed, else grow capacity if appropriate
Entry<K,V> eldest = header.after;
//假如removeEldestEntry办法回来为true，那么则删去1个节点
//默许便是删去离header节点最近的节点，即header的after，即链表的头部
if (removeEldestEntry(eldest)) {
removeEntryForKey(eldest.key);
} else {
if (size >= threshold)
resize(2 * table.length);
}
}
默许状况下removeEldestEntry办法回来为false，所以，假如要完成Lru算法，那么需要重写此办法，回来为true才行
protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
return false;
}
当removeEldestEntry办法回来为true时，则每次都是删去离header最近的节点，回想起第1节，我们的测验代码成果也契合这一描述。
ps：没想到LinkedHashMap是这么有趣的一个容器，运用双向链表即可完成Lru算法，惊叹于Java的完美封装，LinkedHashMap能完美的承继于HashMap，同时还能有自己的特色，真是完美的代码，多向源码学习。
