LinkedHashMap原理分析
本文主要内容
- 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，同时还能有自己的特色，真是完美的代码，多向源码学习。
