HashMap的结构式数组+单向链表，LinkedHashMap继承自HashMap，在原有的基础上新增了四个主要元素，并重写了一些HashMap的方法
/**
* 元素
*/
head //根结点
before //前节点
after //后节点
accessOrder // true-访问顺序 false-插入顺序
/**
* 方法
*/
newNode()
replacementNode()
newTreeNode()
replacementTreeNode()
afterNodeRemoval()
afterNodeInsertion()
afterNodeAccess()
所以LinkedHashMap维护了一个双向链表，并且该链表定义了迭代顺序，下面分析一下他的存储方式和结构
LinkedHashMap的构造方法均调用了super()，就是调用了HashMap的构造方法，不过在之后给accessOrder赋值了，默认为false
LinkedHashMap并没有选择重写put方法，回顾下HashMap的put方法
put
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null); //1.重写
else {
//忽略部分代码
...
}
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e); //2.重写
return oldValue;
}
}
++modCount;
if (++size > threshold)
resize();
afterNodeInsertion(evict); //3.重写
return null;
在来看看LinkedHashMap重写的方法
1.newNode
Node<K,V> newNode(int hash, K key, V value, Node<K,V> e) {
LinkedHashMapEntry<K,V> p =
new LinkedHashMapEntry<K,V>(hash, key, value, e);
linkNodeLast(p);
return p;
}
private void linkNodeLast(LinkedHashMapEntry<K,V> p) {
LinkedHashMapEntry<K,V> last = tail;
tail = p;
if (last == null)
head = p; //1
else {
p.before = last; //2
last.after = p; //3
}
}
主要代码还是在linkNodeLast中，如果第一次添加或者添加的元素都被清空了，那last==null成立，会给head赋值成为根结点，之后的put里，last==null永远不会成立，通过2、3两次赋值组成一个双向链表
双向链表结构.png
再看看put方法中注释3的重写方法，注释2中的方法会在get的时候被调用，晚点在看
//这个方法也是HashMap专门为LinkedHashMap提供的，在某些条件下会删除最早添加进来的数据
void afterNodeInsertion(boolean evict) { // possibly remove eldest
LinkedHashMapEntry<K,V> first;
if (evict && (first = head) != null && removeEldestEntry(first)) {
K key = first.key;
removeNode(hash(key), key, null, false, true);
}
}
put方法和HashMap的差异并不大，主要的改变是如果选择顺序为访问顺序，那么在get的时候会改变链表的节点位置，方法如下
public V get(Object key) {
Node<K,V> e;
if ((e = getNode(hash(key), key)) == null)
return null;
if (accessOrder)
afterNodeAccess(e);
return e.value;
}
/**
*accessOrder指的就是顺序，默认是插入顺序，如果是访问顺序的话，会调用afterNodeAccess
*看到了吧，如果是访问顺序的话，那么每次get，都会重新对链表进行位置交换
*/
void afterNodeAccess(Node<K,V> e) { // move node to last
LinkedHashMapEntry<K,V> last;
//tail保存的是链表尾部，因为如果是访问顺序，get后的节点都会从尾部插入
//p=当前节点e，那么b=p的上一个节点，a=p的下一个节点
//如果p是根结点，那么b一定为null，如果p是尾节点，那么a一定为null
if (accessOrder && (last = tail) != e) {
LinkedHashMapEntry<K,V> p =
(LinkedHashMapEntry<K,V>)e, b = p.before, a = p.after;
p.after = null;
if (b == null)
head = a;
else
b.after = a;
if (a != null)
a.before = b;
else
last = b;
if (last == null)
head = p;
else {
p.before = last;
last.after = p;
}
tail = p;
++modCount;
}
}
用图片解释一下转换的过程，如果get的是最后一个的话，那链表是不会有变化的
改变节点的变化如下
结构变化图.png
其它的方法没有细看过，只看了主要的get方法，大家有兴趣可以去看看
