源码分析——LinkedHashMap
理解了HashMap就可以很容易理解LinkedHashMap了，首先来看一下LinkedHashMap所处的体系结构：
从上面可以看出LinkedHashMap处于Map接口中，作为HashMap的一个子类，其继承了HashMap的方法，并且比它多了一项特性，也就是可以保证输入的顺序和输出的顺序是一样的。接下来继续看其如何实现：
public class LinkedHashMap<K,V> extends HashMap<K,V> implements Map<K,V>由于它继承的是HashMap这个类，因此自然也继承了HashMap的所有接口，所以也就不需要再重复实现了，除此之外，LinkedHashMap还实现了Map接口。
再继续看其成员变量：
private static final long serialVersionUID = 3801124242820219131L;
//序列化标识符，用于反序列化
transient LinkedHashMap.Entry<K,V> head;
//头结点，不被序列化
transient LinkedHashMap.Entry<K,V> tail;
//尾结点，不被序列化
final boolean accessOrder;
//设置顺序，true：按访问顺序排序，false:按插入顺序排序
static class Entry<K,V> extends HashMap.Node<K,V>{
//静态内部类，继承自HashMap中的Node内部类
Entry<K,V> before, after;
//多了两个Entry指针，分别指向前一个Entry和后一个Entry
Entry(int hash, K key, V value, Node<K,V> next){
//构造器，传的值也是一样的
super(hash,key,value,next);
}由于LinkedHashMap是继承了HashMap的，所以也继承了其中所有的非final修饰的成员变量，因此LinkedHashMap在此继承上还增加了head、tail、accessOrder三个成员变量，head和tail主要是作为头结点和尾结点的标志，accessOrder是作为以何种顺序排序的判断，如果为true，则表示按访问顺序，将最近访问的放入链表的尾部，而为false，则表示按照插入的顺序排序。从此可以看出，LinkedHashMap是在HashMap的基础上再在所有的键值对上面建立一个链表，该链表的键值对排列的顺序即accessOrder指定的顺序，这样就达成了有序的特点。提醒一下这个有序并不是代表递增或者递减这样的顺序，其实可以说是一种时间顺序。
同样，LinkedHashMap中放置键值对的结点Entry也是继承了HashMap中的Node结点，而且还增加了before和after两个结点指针。即分别指向顺序链表中的前置结点和后置结点。
接下来继续看其构造函数：
public LinkedHashMap(int initialCapacity, float loadFactor){
//构造器1，参数为初始容量与加载因子
super(initialCapacity,loadFactor);
//调用父类的构造器
accessOrder = false;
//将accessOrder设置为false，即按插入顺序排序
}
public LinkedHashMap(int initialCapacity){
//构造器2，参数为初始容量
super(initialCapacity);
//调用父类构造器
accessOrder = false;
//设置accessOrder为false,按插入顺序排序
}
public LinkedHashMap(){
//构造器3，空参
super();
accessOrder = false;
}
public LinkedHashMap(Map<? extends K, ? extends V> m){
//构造器4，参数为Map类容器
super();
accessOrder = false;
putMapEntries(m,false);
}
public LinkedHashMap(int initialCapacity, float loadFactor, boolean accessOrder){
//构造器5，参数为初始容量、加载因子以及访问顺序
//此构造器可以自己设置链表排列顺序为插入顺序还是访问顺序
super(initialCapacity, loadFactor);
this.accessOrder = accessOrder
}LinkedHashMap包含五个构造器，当传入的是初始容量与加载因子，则先调用父类构造器，并将accessOrder置为false，即顺序为插入顺序；如果传入的是初始容量，则将加载因子置为默认值，将accessOrder也置为false,再调用父类构造器；当传入的为空参，则将直接调用父类空参构造器并将accessOrder置为false；当传入的是一个Map集合类，则先调用父类空参构造器，再将accessOrder置为false,并调用putMapEntries将键值对依次放入LinkedHashMap中；当传入的是一个初始容量、加载因子与accessOrder时，则按照传入的参数先调用父类构造器，再设置accessOrder。总之，如果不设置accessOrder参数，则其为默认false，即默认是按照插入顺序排序，当然可以通过构造器设置accessOrder为访问顺序排序。
接下来再研究一下其常用方法：
1.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;
}由于LinkedHashMap是直接继承HashMap类的，所以HashMap中的常用的get、put、remove、clear等方法是可以直接用的，而对于get方法两者的最大的区别就是当LinkedHashMap的accessOrder设置为true时，当前访问的结点要移动的排序链表的末尾。因此才重写get方法。其实此get方法的主体还是HashMap中的get方法。
2.containsValue
public boolean containsValue(Object value){
//判断链表中是否含有value值，由于直接用此类中的链表查找
//value时比HashMap中的查找效率要高，所以就重写了此方法
for(LinkedHashMap.Entry<K,V> e = head; e != null; e = e.after){
//遍历链表，如果找到了返回true，没找到返回false
V v = e.value;
if(v == value || (value != null && value.equals(v)))
return true;
}
return false;
}此方法是通过传入的value值寻找到第一个value值与其相等的键值对，而HashMap中只能通过key来寻找相关的键值对，如果通过value来寻找则效率比较低，毕竟其实里面的每一个链表或者红黑树都是散列的分布在数组槽中的，而LinkedHashMap中建立了一个连接所有键值对的链表，而从这条链表中查询某一个value值就容易的多。因此重写了此方法。
3.clear
public void clear(){
//清空数组
super.clear();
//调用父类清空方法
head = tail = null;
//将链表也清空
}此处的清空方法除了要调用父类的清空方法之外还要将两个头尾指针置为空。
总结：LinkedHashMap其实就是在HashMap所建立的哈希表-链表-红黑树的结构的基础上再加上一条连接包含所有键值对的链表，此链表中排列顺序有两种方式，方式可以在创建LinkedHashMap时通过设置accessOrder变量选择，从而实现以插入顺序排序和访问顺序排序两种排序方式。
总代码：
public class LinkedHashMap<K,V> extends HashMap<K,V> implements Map<K,V>{
static class Entry<K,V> extends HashMap.Node<K,V>{
//静态内部类，继承自HashMap中的Node内部类
Entry<K,V> before, after;
//多了两个Entry指针，分别指向前一个Entry和后一个Entry
Entry(int hash, K key, V value, Node<K,V> next){
//构造器，传的值也是一样的
super(hash,key,value,next);
}
}
private static final long serialVersionUID = 3801124242820219131L;
//序列化标识符，用于反序列化
transient LinkedHashMap.Entry<K,V> head;
//头结点，不被序列化
transient LinkedHashMap.Entry<K,V> tail;
//尾结点，不被序列化
final boolean accessOrder;
//设置顺序，true：按访问顺序排序，false:按插入顺序排序
private void linkNodeLast(LinkedHashMap.Entry<K,V> p){
//在链表尾部插入一个结点
LinkedHashMap.Entry<K,V> last = tail;
//将尾结点取出赋给last结点
tail = p;//将尾结点移到p结点处
if(last == null)
//如果原尾结点为空，说明链表为空
head = p;
//将p结点作为头结点
else{
p.before = last;
//将p的前置指针指向last
last.after = p;
//将last的后置指针指向p
}
}
private void transferLinks(LinkedHashMap.Entry<K,V> src, LinkedHashMap.Entry<K,V> dst){
//用dst结点替换掉src结点
LinkedHashMap.Entry<K,V> b = dst.before = src.before;
//将src结点的前置结点作为dst的前置结点且赋给b结点
LinkedHashMap.Entry<K,V> a = dst.after = src.after;
//将src结点的后置结点作为dst的后置结点且赋给a结点
if(b == null)
//如果b结点为空，说明src是头结点
head = dst;
//将dst作为头结点
else
//否则，将src的前置结点的后置指针由指向src结点变为指向dst结点
b.after = dst;
if(a == null)
//如果b结点为空，说明src时尾结点
tail = dst;
//将dst作为尾结点
else
//否则，将src的后置结点的前置指针由指向src结点变为指向dst结点
a.before = dst;
}
void reinitialize(){
//重新初始化
super.reinitialize();
//调用父类的初始化方法
head = tail = null;
//将头尾结点置空
}
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;
//返回新插入的结点
}
Node<K,V> replacementNode(Node<K,V> p, Node<K,V> next){
//将红黑树结点转化为LinkedHashMap.Entry结点，此处重写了HashMap中的
//replacementNode方法
LinkedHashMap.Entry<K,V> q = (LinkedHashMap.Entry<K,V>)p;
//将传入的p结点强转为LinkedHashMap.Entry结点q
LinkedHashMap.Entry<K,V> t = new LinkedHashMap.Entry<K,V>(q.hash, q.key, q.value, next);
//重新创建一个结点t，将必要信息写进去
transferLinks(q,t);
//将q与t替换
return t;
//返回t结点
}
TreeNode<K,V> newTreeNode(int hash, K key, V value, Node<K,V> next){
//创建一个新的TreeNode，并将其插入到链表尾部
TreeNode<K,V> p = new TreeNode<K,V>(hash,key,value,next);
linkNodeLast(p);
return p;
}
TreeNode<K,V> replacementTreeNode(Node<K,V> p, Node<K,V> next){
//将LinkedHashMap.Entry结点转化为红黑树结点，重写HashMap中的
//replacementTreeNode方法
LinkedHashMap.Entry<K,V> q = (LinkedHashMap.Entry<K,V>)p;
TreeNode<K,V> t = new TreeNode<K,V>(q.hash, q.key, q.value, next);
transferLinks(q,t);
return t;
}
void afterNodeRemoval(Node<K,V> e){
//此方法在HashMap中也声明了，但是没有写方法体，而且在删除结点方法里面
//成功删除后也调用了此方法，因此继承自HashMap的本类只需要重写此方法就可以
//不必再重写删除方法，懒惰是人类进步的阶梯(^~^)
//传进来的是被删除的结点e，此方法是将e结点从插入顺序这条双向链表中删去
LinkedHashMap.Entry<K,V> p = (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
//p表示传进来的e结点，b表示e结点的前置结点，a表示e结点的后置结点
p.before = p.after = null;
//先将结点的前置指针和后置指针置为空
if(b == null)
//如果e结点的前置结点是空，说明e结点是首节点
head = a;
//将e结点的后置结点作为首结点
else
b.after = a;
//否则，将e结点的前置结点的后置指针指向e结点的后置结点就够了
if(a == null)
//同理，如果e结点的后置结点为空，说明e结点是尾结点
tail = b;
//将e结点的前置结点作为尾结点
else
a.before = b;
//否则，将e结点的后置结点的前置指针指向e结点的前置结点就够了
}
void afterNodeInsertion(boolean evict){
//在插入新结点的时候删除最老的结点，由于removeEldestEntry返回的false
//所以此方法无法执行，特定场合需要时可以重写removeEldestEntry方法
LinkedHashMap.Entry<K,V> first;
if(evict && (first = head) != null && removeEldestEntry(first)){
K key = first.key;
removeNode(hash(key), key, null, false, true);
}
}
void afterNodeAccess(Node<K,V> e){
//当accessOrder为true时，表示链表是按照访问顺序排序的，
//也就是按被访问的时间进行排序，已经访问的往后放。而e结点
//表示刚被访问过，因此需要将其移动到链表的尾部(此方法在getNode())
//方法中被调用
LinkedHashMap.Entry<K,V> last;//先设置一个last结点
if(accessOrder && (last = tail) != e){
//如果accessOrder为true且e不是尾结点
LinkedHashMap.Entry<K,V> p = (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
//p表示e结点,b表示e的前置结点,a表示e的后置结点
p.after = null;
//先将p的后置指针置空
if(b == null)
//如果e的前置指针为空，说明e是首结点
head = a;
//将e的后置结点作为首结点
else
b.after = a;
//否则将e的前置结点的后置指针指向其后置结点
if(a != null)
//如果e的后置结点不为空，说明其不是尾结点
a.before = b;
//则将e的后置结点的前置指针指向其前置结点
else
last = b;
//否则说明e是尾结点，则将其前置结点作为尾结点
//上面主要是将e结点从链表中删除，而下面则将e结点插在链表尾部
if(last == null)
//如果链表为空，则将e作为首结点
head = p;
else{
//否则将e的前置指针指向last
p.before = last;
//将last的后置指针指向e
last.after = p;
}
tail = p;
//将p结点作为尾结点
++modCount;
}
}
void internalWriteEntries(java.io.ObjectOutputStream s) throws IOException{
//按照顺序将LinkedHashMap写入进去
for(LinkedHashMap.Entry<K,V> e = head; e != null; e = e.after){
s.writeObject(e.key);
s.writeObject(e.value);
}
}
public LinkedHashMap(int initialCapacity, float loadFactor){
//构造器1，参数为初始容量与加载因子
super(initialCapacity,loadFactor);
//调用父类的构造器
accessOrder = false;
//将accessOrder设置为false，即按插入顺序排序
}
public LinkedHashMap(int initialCapacity){
//构造器2，参数为初始容量
super(initialCapacity);
//调用父类构造器
accessOrder = false;
//设置accessOrder为false,按插入顺序排序
}
public LinkedHashMap(){
//构造器3，空参
super();
accessOrder = false;
}
public LinkedHashMap(Map<? extends K, ? extends V> m){
//构造器4，参数为Map类容器
super();
accessOrder = false;
putMapEntries(m,false);
}
public LinkedHashMap(int initialCapacity, float loadFactor, boolean accessOrder){
//构造器5，参数为初始容量、加载因子以及访问顺序
//此构造器可以自己设置链表排列顺序为插入顺序还是访问顺序
super(initialCapacity, loadFactor);
this.accessOrder = accessOrder
}
public boolean containsValue(Object value){
//判断链表中是否含有value值，由于直接用此类中的链表查找
//比HashMap中的查找效率要高，所以就重写了此方法
for(LinkedHashMap.Entry<K,V> e = head; e != null; e = e.after){
//遍历链表，如果找到了返回true，没找到返回false
V v = e.value;
if(v == value || (value != null && value.equals(v)))
return true;
}
return false;
}
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;
}
public V getOrDefault(Object key, V defaultValue){
//此方法的重写目的和上一个方法一样
Node<K,V> e;
if((e = getNode(hash(key),key)) == null)
return defaultValue;
if(accessOrder)
afterNodeAccess(e);
return e.value;
}
public void clear(){
//清空数组
super.clear();
//调用父类清空方法
head = tail = null;
//将链表也清空
}
protected boolean removeEldestEntry(Map.Entry<K,V> eldest){
//表示插入新结点时是否需要删除最老的结点
return false;
}
public Set<K> keySet(){
//获得一个包含key值的Set容器
Set<K> ks = KeySet;
if(ks == null){
ks = new LinkedKeySet();
keySet = ks;
}
return ks;
}
final class LinkedKeySet extends AbstractSet<K>{
//和HashMap中的KeySet基本类似，主要是遍历部分变简单了
public final int size(){
return size;
}
public final void clear(){
LinkedHashMap.this.clear();
}
public final Iterator<K> iterator(){
return new LinkedKeyIterator();
}
public final boolean contains(Objects o){
return containsKey(o);
}
public final boolean remove(Object key){
return removeNode(hash(key), key, null, false, true) != null;
}
public final Spliterator<K> spliterator(){
return Spliterators.spliterator(this, Spliterator.SIZED | Spliterator.ORDERED | Spliterator.DISTINCT);
}
public final void forEach(Consumer<? super K> action){
if(action == null)
throw new NullPointerException();
int mc = modCount;
for(LinkedHashMap.Entry<K,V> e = head; e != null; e = e.after)
action.accept(e.key);
if(modCount != mc)
throw new ConcurrentModificationException();
}
}
public Collection<V> values(){
//获得一个包含value值的集合
Collection<V> vs = values;
if(vs == null){
vs = new LinkedValues();
values = vs;
}
return vs;
}
final class LinkedValues extends AbstractCollection<V>{
//和HashMap中的values基本类似，主要是遍历部分变简单了
public final int size(){
return size;
}
public final void clear(){
LinkedHashMap.this.clear();
}
public final Iterator<V> iterator(){
return new LinkedValueIterator();
}
public final boolean contains(Object o){
return containsValue(o);
}
public final Spliterator<V> spliterator(){
return Spliterators.spliterator(this, Spliterator.SIZED | Spliterator.ORDERED);
}
public final void forEach(Consumer<? super V> action){
if(action == null)
return new NullPointerException();
int mc = modCount;
for(LinkedHashMap.Entry<K,V> e = head; e != null; e = e.after)
action.accept(e.value);
if(modCount != mc)
throw new ConcurrentModificationException();
}
}
public Set<Map.Entry<K,V>> entrySet(){
//获得一个包含键值对的Set集合
Set<Map.Entry<K,V>> es;
return (es = entrySet) == null ? (entrySet = new LinkedEntrySet());
}
final class LinkedEntrySet extends AbstractSet<Map.Entry<K,V>>{
//和HashMap中的EnterySet基本类似，主要是遍历部分变简单了
public final int size(){
return size;
}
public final void clear(){
LinkedHashMap.this.clear();
}
public final Iterator<Map.Entry<K,V>> iterator(){
return new LinkedEntryIterator();
}
public final boolean contains(Object o){
if(!(o instanceof Map.Entry))
return false;
Map.Entry<?,?> e = (Map.Entry<?,?>)o;
Object key = e.getKey();
Node<K,V> candidate = getNode(hash(key),key);
return candidate != null && candidate.equals(e);
}
public final boolean remove(Object o){
if(o instanceof Map.Entry){
Map.Entry<?,?> e = (Map.Entry<?,?>)o;
Object key = e.getKey();
Object value = e.getValue();
return removeNode(hash(key), key, value, true, true) != null;
}
return false;
}
public final Spliterator<Map.Entry<K,V>> spliterator(){
return Spliterators.spliterator(this, Spliterator.SIZED | Spliterator.ORDERED | Spliterator.DISTINCT);
}
public final void forEach(Consumer<? super Map.Entry<K,V>> action){
if(action == null)
throw new NullPointerException();
int mc = modCount;
for(LinkedHashMap.Entry<K,V> e = head; e != null; e = e.after)
action.accept(e);
if(modCount != mc)
throw new ConcurrentModificationException();
}
}
public void forEach(BiConsumer<? super K, ? super V> action){
//java 1.8新特性
if(action == null)
throw new NullPointerException();
int mc = modCount;
for(LinkedHashMap.Entry<K,V> e = head; e != null; e = e.after)
action.accept(e.key,e.value);
if(modCount != mc)
throw new ConcurrentModificationException();
}
public void replaceAll(BiFunction<? super K, ? super V, ? extends V> function){
//java 1.8新特性
if(function == null)
throw new NullPointerException();
int mc = modCount;
for(LinkedHashMap.Entry<K,V> e = head; e != null; e = e.after)
e.value = function.apply(e.key, e.value);
if(modCount != mc)
throw new ConcurrentModificationException();
}
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;
}
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;
}
}
final class LinkedKeyIterator extends LinkedHashIterator implements Iterator<K>{
//key值迭代器
public final K next(){
return nextNode().getKey();
}
}
final class LinkedValueIterator extends LinkedHashIterator implements Iterator<V<{
//value值迭代器
public final V next(){
return nextNode().value;
}
}
final class LinkedEntryIterator extends LinkedHashIterator implements Iterator<Map.Entry<K,V>>{
//键值对迭代器
public final Map.Entry<K,V> next(){
return nextNode();
}
}
}参考资料：