上一篇文章我和大家一起解读了HashMap的原理源码，各位童鞋可以点击链接查看线性表数据结构解读（五）哈希表结构-HashMap
这次我们一起来看一下LinkedHashMap，它保留插入的顺序，如果需要输出的顺序和输入时的相同，那么就选用LinkedHashMap。就LinkedHashMap而言，它继承了HashMap，底层使用哈希表与双向链表来保存所有元素。其基本操作与父类HashMap相似，它通过重写父类相关的方法，来实现自己的链接列表特性。
LinkedHashMap是Map接口的哈希表和链接列表实现，具有可预知的迭代顺序。此实现提供所有可选的映射操作，并允许使用null值和null键。此类不保证映射的顺序，特别是它不保证该顺序恒久不变。
LinkedHashMap实现与HashMap的不同之处在于，后者维护着一个运行于所有条目的双重链接列表。此链接列表定义了迭代顺序，该迭代顺序可以是插入顺序或者是访问顺序。
- 第一种和队列一样默认是按插入顺序排序，先进来的是最老的元素，放在队头，将来会被先移出去，最后进来的是新的元素。
- 第二种，基于访问排序，那么调用get方法后，会将每次访问的元素移至队尾，将来移除的时候移除的是队头，最先访问的元素最后才被移除，不断访问可以形成按访问顺序排序的链表。
下图是我在小黑板手绘的双链回环循环链表
下面我们一起来分析一下LinkedHashMap的源码：
初始化及构造方法
/**
* 双链回环循环链表
*/
public class LinkedHashMap<K, V> extends HashMap<K, V> {
/**
* 双向链表的头结点
*/
transient LinkedEntry<K, V> header;
/**
* true通过访问来排序，false通过插入排序
*/
private final boolean accessOrder;
/**
* Constructs a new empty {@code LinkedHashMap} instance.
*/
public LinkedHashMap() {
init();
accessOrder = false;// 默认是插入排序
}
public LinkedHashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
public LinkedHashMap(int initialCapacity, float loadFactor) {
this(initialCapacity, loadFactor, false);
}
public LinkedHashMap(
int initialCapacity, float loadFactor, boolean accessOrder) {
super(initialCapacity, loadFactor);
init();
this.accessOrder = accessOrder;
}
public LinkedHashMap(Map<? extends K, ? extends V> map) {
this(capacityForInitSize(map.size()));
constructorPutAll(map);
//LinkedHashMap重写了init()方法，在调用父类的构造方法完成构造后，进一步实现了对其元素Entry的初始化操作
@Override
void init() {
header = new LinkedEntry<K, V>();
}
/**
* 继承HashMap的Entry元素，又保存了其上一个元素before和下一个元素after的引用
*/
static class LinkedEntry<K, V> extends HashMapEntry<K, V> {
LinkedEntry<K, V> nxt;
LinkedEntry<K, V> prv;
/** Create the header entry */
LinkedEntry() {
super(null, null, 0, null);
nxt = prv = this;
}
/** Create a normal entry */
LinkedEntry(K key, V value, int hash, HashMapEntry<K, V> next,
LinkedEntry<K, V> nxt, LinkedEntry<K, V> prv) {
super(key, value, hash, next);
this.nxt = nxt;
this.prv = prv;
}
}
/**
* 拿到最老的元素
* Returns the eldest entry in the map, or {@code null} if the map is empty.
* @hide
*/
public Entry<K, V> eldest() {
LinkedEntry<K, V> eldest = header.nxt;
return eldest != header ? eldest : null;
}
}addNewEntry方法
/**
* 重写了HashMap中的添加新元素方法
*/
@Override
void addNewEntry(K key, V value, int hash, int index) {
// 找到头结点
LinkedEntry<K, V> header = this.header;
// 找到用于移除的队头的最老结点
LinkedEntry<K, V> eldest = header.nxt;
// 如果最老的结点不等于头结点（有元素存在）且removeEldestEntry为true
if (eldest != header && removeEldestEntry(eldest)) {
remove(eldest.key);// 移除最老元素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);
table[index] = oldTail.nxt = header.prv = newTail;// 把新的加入到table数组中
}下图是我在小黑板手绘的插入方法实现原理图，注意其中指针的变化：
remove方法
// 移除最老的元素
protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
return false;
}get方法
/**
* Returns the value of the mapping with the specified key.
* @param key the key.
* @return the value of the mapping with the specified key, or {@code null}
* if no mapping for the specified key is found.
*/
@Override 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;
}下面博文，我将为大家带来LinkedHashMap的最佳实践：LruCache缓存算法的解析，敬请查阅LinkedHashMap最佳实践：LruCache