在上一篇博客Java HashMap源码简单解析（JDK 1.8）中，我们分析了HashMap的实现原理。HashMap内部使用数组+链表（或红黑树）的形式。结点的key的hash值决定了该结点在数组中的位置（hash值前16位和后16位相与的值再和数组长度减1相与，得到的值就是结点在数组中的位置），当发生hash碰撞（也就是几个结点都需要放在数组的同一个位置，就使用链表把他们连接起来）。
LinkedHashMap与HashMap最大的不同之处在于，HashMap存储的数据是无序的，通过迭代器访问的顺序和插入的顺序无关。而LinkedHashMap通过双向链表将结点连接起来（有人说是循环链表，但是从JDK1.8的源码来看并不是循环链表），可以通过双向链表可以顺序地访问已存储的结点（访问顺序可以是插入顺序也可以是LRU顺序）。
下面我们来看一下LinkedHashMap内部是怎么实现的。
继承关系
public class LinkedHashMap<K,V> extends HashMap<K,V> implements Map<K,V>
LinkedHashMap继承了HashMap，并实现了Map接口
成员变量
/**
* 保存的头结点
*/
transient LinkedHashMap.Entry<K,V> head;
/**
* 保存的尾结点
*/
transient LinkedHashMap.Entry<K,V> tail;
/**
* 是否按访问顺序排序
*/
final boolean accessOrder;
LinkedHashMap内部保存了双向链表的头结点和尾结点，并且有一个标志位accessOrder，用来确定是否按访问顺序排序。
结点
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);
}
}
LinkedHashMap使用的结点继承了HashMap的结点，在原来的基础上增加了before和after两个参数，通过着两个参数可以使结点形成一个双向链表。LinkedHashMap和HashMap最大的不同也就是怎么处理这两个变量。
构造方法
public LinkedHashMap(int initialCapacity, float loadFactor) {
super(initialCapacity, loadFactor);
accessOrder = false;
}
public LinkedHashMap(int initialCapacity) {
super(initialCapacity);
accessOrder = false;
}
public LinkedHashMap() {
super();
accessOrder = false;
}
public LinkedHashMap(Map<? extends K, ? extends V> m) {
super();
accessOrder = false;
putMapEntries(m, false);
}
public LinkedHashMap(int initialCapacity,
float loadFactor,
boolean accessOrder) {
super(initialCapacity, loadFactor);
this.accessOrder = accessOrder;
}
LinkedHashMap的构造方法中都调用了HashMap的构造方法，可以说从构造方法来看，两个差距不大。
put方法
你会发现在LinkedHashMap中找不到put方法，这是这时因为LinkedHashMap直接使用了父类HashMap的put方法，他只重写了Node<K,V> newNode(int hash, K key, V value, Node<K,V> e)方法。在HashMap中该方法就是创建了一个结点，我们看在LinkedHashMap中该方法做了什么工作。
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;
}
}
从上面的代码我们看出，newNode内部也是先创建了一个结点，然后调用了LinkNodeLast函数。LinkNodeLast函数中将新结点插入到双向链表的末尾，并更新head 和tail两个成员变量。
put总结：LinkNodeLast和HashMap的put方法不同之处就是LinkNodeLast对于插入的每一个节点，都将其插入到双向链表中。
get方法
public V get(Object key) {
Node<K,V> e;
if ((e = getNode(hash(key), key)) == null) //根据hash值获取结点
return null;
if (accessOrder) //如果按照访问顺序排序，更新结点排序
afterNodeAccess(e);
return e.value;
}
void afterNodeAccess(Node<K,V> e) { // 将结点放到双向链表的最后
LinkedHashMap.Entry<K,V> last;
if (accessOrder && (last = tail) != e) {
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)
a.before = b;
else
last = b;
if (last == null)
head = p;
else {
p.before = last;
last.after = p;
}
tail = p;
++modCount;
}
}
同样的LinkedHashMap和HashMap的get操作最大的不同也是双向链表这一点。在LinkedHashMap的get方法中，首先根据hash值获得结点，如果双向链表是根据访问顺序排序的，还需要对双向链表重新排序，使最新访问的结点在链表的最后。
迭代器
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;
}
}
由于LinkedHashMap内部使用双向链表来顺序保存数据，所以在使用迭代器内部也是通过在双向链表上的移动来访问数据的。
网友评论