LinkedHashMap比HashMap多了啥？
文章目录
前言
继承自HashMap，LinkedHashMap = HashMap + LinkedList，话不多说，直接上源码。
一、LinkedHashMap数据结构
双链表结构：单向链表 + 双向链表。如下图所示：
实际情况双向链表before和after指针可能不是这样的，上图只是为了作图简单，看起来美观一点。
再来看看源码数据结构
static class Entry<K,V> extends HashMap.Node<K,V> {
// 双向链表的前后指针，如上图所示
Entry<K,V> before, after;
Entry(int hash, K key, V value, Node<K,V> next) {
super(hash, key, value, next);
}
}
二、源码分析
1.主要属性
/**
* 链表头结点
*/
transient LinkedHashMap.Entry<K,V> head;
/**
* 链表的尾节点
*/
transient LinkedHashMap.Entry<K,V> tail;
/**
* 是否按访问顺序，true-按访问顺序，false-按插入顺序
*/
final boolean accessOrder;
2.构造函数
都是调用HashMap的构造函数，双向链表默认按插入顺序排列，也提供可选排列方式顺序的构造函数。
public LinkedHashMap() {
super();
accessOrder = false; // 默认按插入顺序
}
public LinkedHashMap(int initialCapacity) {
super(initialCapacity);
accessOrder = false;
}
public LinkedHashMap(int initialCapacity,
float loadFactor,
boolean accessOrder) {
super(initialCapacity, loadFactor);
this.accessOrder = accessOrder;
}
3.关键方法
关键方法有两个，之前在分析HashMap源码的时候也提了一下，afterNodeAccess方法和afterNodeInsertion方法。那么首先我们来看下get方法。
1、get(Object key)
与HashMap的get方法相比，仅仅是多了一个访问顺序问题。
public V get(Object key) {
Node<K,V> e;
if ((e = getNode(hash(key), key)) == null)
return null;
if (accessOrder)// 仅仅是多了这个判断，如果为true，就要维护访问顺序
afterNodeAccess(e);
return e.value;
}
2、afterNodeAccess(Node e)
其实就是把传入的e节点放在双向链表的末尾。
void afterNodeAccess(Node<K,V> e) { // move node to last
LinkedHashMap.Entry<K,V> last;
if (accessOrder && (last = tail) != e) { // accessOrder为true且访问的节点不是链尾的节点
LinkedHashMap.Entry<K,V> p =
(LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;// 把访问节点的前节点后节点都标记好
p.after = null;
if (b == null) // 说明当前访问节点是头节点，那就把它后节点放头结点
head = a;
else // 不是头结点，那就直接把前节点的后指针指向后节点
b.after = a;
if (a != null) // 一般情况下都为true
a.before = b;
else
last = b;
if (last == null)// 如果链表中还没有元素，则将e设置为头结点
head = p;
else {//否则的话将e挪到链表末尾
p.before = last;
last.after = p;
}
tail = p;
++modCount;
}
}
3、afterNodeInsertion(boolean evict)
这个方法表示插入之后是否删除最老的节点，即头结点。evict这个参数如果为true才可能会删除。但是我看了调用这个方法的地方传入的都是true。除了构造函数调用、克隆时为false。
void afterNodeInsertion(boolean evict) { // possibly remove eldest
LinkedHashMap.Entry<K,V> first;
if (evict && (first = head) != null && removeEldestEntry(first)) {
K key = first.key;
removeNode(hash(key), key, null, false, true);
}
}
刚开始看源码的时候很好奇这个head是在哪里赋值了？于是我找到了put方法，新建节点的时候做了如下事情：
Node<K,V> newNode(int hash, K key, V value, Node<K,V> e) {
LinkedHashMap.Entry<K,V> p =
new LinkedHashMap.Entry<K,V>(hash, key, value, e);
linkNodeLast(p);// 这个方法做了啥呢？
return p;
}
// 仅仅是把新建的节点放在链表最后
private void linkNodeLast(LinkedHashMap.Entry<K,V> p) {
LinkedHashMap.Entry<K,V> last = tail;
tail = p;
if (last == null)
head = p;
else {
p.before = last;
last.after = p;
}
}
由此可见put的时候就默认把元素按插入顺序排好了，如果accessOrder为false的话那这个双向链表的顺序就不会变了，即按插入顺序排列，如果accessOrder为true，则按访问顺序排列。
4.遍历方式
还记得HashMap遍历方式是怎么遍历的吗？先从数组下标0开始遍历链表，直到遍历到最后一个数组下标的链表末尾。
但是LinkedHashMap也是这样遍历的吗？我们来看看。
abstract class LinkedHashIterator {
LinkedHashMap.Entry<K,V> next;
LinkedHashMap.Entry<K,V> current;
int expectedModCount;
LinkedHashIterator() {
next = head;
expectedModCount = modCount;
current = null;
}
public final boolean hasNext() {
return next != null;
}
// 关键是获取下一个元素的方法，我们可以看到，直接用的是双向链表的方式，so easy
final LinkedHashMap.Entry<K,V> nextNode() {
LinkedHashMap.Entry<K,V> e = next;
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
if (e == null)
throw new NoSuchElementException();
current = e;
next = e.after;
return e;
}
public final void remove() {
Node<K,V> p = current;
if (p == null)
throw new IllegalStateException();
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
current = null;
K key = p.key;
removeNode(hash(key), key, null, false, false);
expectedModCount = modCount;
}
}
所以LinkedHashMap遍历只能说招式是一样的，提供一样的遍历api，结构也是一样的，但是遍历方式本质上完全不一样。
总结
LinkedHashMap是基于HashMap做的操作，所以阅读完HashMap源码再来看LinkedHashMap源码显得很简单。
加油吧，骚年！
本文地址：https://blog.csdn.net/Soldier_son/article/details/110001988