注：本文来自Android中LinkedHashMap的解析
阅读本篇文字建议先阅读以下HashMap解析
首先LinkedHashMap的字面意思链式Map，其实它继承自HashMap，所以它具备HashMap的特性：
public class LinkedHashMap<K,V>
extends HashMap<K,V>
implements Map<K,V>
{
//...省略
}
既然继承自HashMap，那么LinkedHashMap与HashMap有什么不一样的功能呢？
答案是LinkedHashMap比HashMap多的唯一功能是有序的，ok，那我就开始罗列问题了：
1、LinkedHashMap采用的数据结构是什么？
2、LinkedHashMap的有序是key的有序还是value有序？
3、LinkedHashMap是怎么确保有序的？
4、LinkedHashMap是怎么实现有序访问？
5、LinkedHashMap的应用场景？
6、LinkedHashMap与HashMap的区别
问题1、LinkedHashMap采用的数据结构是什么？
因为LinkedHashMap是继承自HashMap的，其存储还是采用一维数组+链表结构，但这里注意了这里链表是双向链表，而HashMap采用的是单向链表；其有序性是通过外层的双向链表确保的
/**
* The head (eldest) of the doubly linked list.
*/
transient LinkedHashMapEntry<K,V> head;
/**
* The tail (youngest) of the doubly linked list.
*/
transient LinkedHashMapEntry<K,V> tail;
//节点结构
static class LinkedHashMapEntry<K,V> extends HashMap.Node<K,V> {
LinkedHashMapEntry<K,V> before, after;
LinkedHashMapEntry(int hash, K key, V value, Node<K,V> next) {
super(hash, key, value, next);
}
}
上述代码可以看到，LinkedHashMap额外添加的head和tail是用来确保有序的，分别表示链表的头部和尾部。其中节点使用的时候LinkedHashMapEntry，LinkedHashMapEntry中通过before, after来确保双向的
问题2、LinkedHashMap的有序是key的有序还是value有序？
答案是既不是key有序也不是value有序，其有两种有序：一种是插入有序；一种是访问有序。插入有序即遍插入时后插入的排在后面，迭代访问时是按照插入的顺序进行迭代的；访问有序，这个是不是有点懵逼？访问有序指的是每次访问元素时，先将元素从链表中删除，接着再将此元素放到链表末尾，这样确保访问的有序性。
我们先来看其中一个很中的字段描述：
/**
* The iteration ordering method for this linked hash map: <tt>true</tt>
* for access-order, <tt>false</tt> for insertion-order.
*
* @serial
*/
final boolean accessOrder;
accessOrder就是用于确定是插入有序还是访问有序的。注释也说的很明白：当accessOrder为false是插入有序；当accessOrder为true是是访问有序，默认值为false，采用插入有序。
问题3、LinkedHashMap是怎么确保有序的？
问题2中accessOrder是确定采用的是那种有序，我们也知道有两种有序方式，那么下面我们分别来看下源码中这两种有序的实现：
插入有序
LinkedHashMap并没有重新put的方法，也就是说put操作默认采用的是HashMap的put实现，那么LinkedHashMap是通过什么来确保插入有序呢？我们重新看下HashMap的添加节点框架：
//HashMap.java
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);
//..省略
}
重点在于newNode方法，我们看到LinedHashMap是有覆盖了此方法的实现的：
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;
//将当前有序链表的末尾节点设置为新的节点p
tail = p;
if (last == null)
//如果原有序链表的末尾节点为空，代表有序链表是空的
head = p;
else {
//如果原有序链表的末尾节点不为空，将新的节点放入有序链表的末尾
p.before = last;
last.after = p;
}
}
插入有序采用的是HashMap的put操作，并不会更改HashMap的put逻辑，只是在其基础上通过新增有序链表来确保插入的有序性，在添加新的节点时将新节点放入有序链表的末尾即可。
这个里面的信息量还是挺多的：
- LinekedHashMap的put操作还是用的是HashMap的put操作
- LinkedHashMap 散列表还是用的HashMap的散列表实现方式
- LinkedHashMap只是新增额外的有序链表来确保插入的有序性
访问有序
访问有序顾名思义对每次访问的元素进行排序，后面访问的元素排在前面访问的元素的后面。既然是访问，那么对于的就是get方法，LinkedHashMap是有重新get方法的，我们来看下其实现源码：
public V get(Object key) {
Node<K,V> e;
// 通过父类的getNode方法获取key对于的元素
if ((e = getNode(hash(key), key)) == null)
return null;
if (accessOrder)
//如果采用的是访问有序，那么调用afterNodeAccess方法将访问的元素放入有序链表的表尾
afterNodeAccess(e);
return e.value;
}
/**
将当前访问节点放入有序链表的表尾，思想是先将当前访问节点进行链表删除操作，再将访问的节点放入链表末尾
*/
void afterNodeAccess(Node<K,V> e) { // move node to last
LinkedHashMapEntry<K,V> last;
if (accessOrder && (last = tail) != e) {
// 如果是访问有序方式
/**
p，e： 当前访问的节点
b：当前访问节点的前一个节点
a: 当前访问节点的后一个节点
*/
LinkedHashMapEntry<K,V> p =
(LinkedHashMapEntry<K,V>)e, b = p.before, a = p.after;
//将当前节点的后一个节点设置为空，代表此节点是表尾节点
p.after = null;
if (b == null)
/**
当前访问节点的前一个节点为空，代表链表为空，所以设置表头为a(当前访问节点的后台一个节点)。意思对当前访问节点的删除操作
*/
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;
}
}
访问节点的实现思想是：先将访问的节点从有序链表中删除，再放入有序链表的表尾。
- 综合插入有序和访问有序的源码，细心的会发现，不管是插入有序还是访问有序，每次添加的元素都是放入有序链表的表尾。
问题4、LinkedHashMap是遍历有序？
如果说key是int类型，并且值分别0,1,2,3，那么是否通过for已经自增key来get是否是有序的呢？答案是否定的，前面也分析了LinkedHashMap是插入有序或者访问有序，而不是key或者value有序。所以只能通过迭代器对有序链表进行迭代才是王道，可以使用LinkedHashMap的keySet()、values()、entrySet()进行迭代实现遍历的有序，我们看下其内部LinkedEntrySet类迭代的实现：
public final void forEach(Consumer<? super Map.Entry<K,V>> action) {
if (action == null)
throw new NullPointerException();
int mc = modCount;
// Android-changed: Detect changes to modCount early.
//对有序链表进行迭代访问，实现有序访问
for (LinkedHashMapEntry<K,V> e = head; (e != null && mc == modCount); e = e.after)
action.accept(e);
if (modCount != mc)
throw new ConcurrentModificationException();
}
问题5、LinkedHashMap的应用场景？
LinkeHashMap的特性是可以实现插入有序和访问有序，其最常见的应用场景就是实现LRU（Least Recently Used）缓存算法。LRU缓存算法的思想是有序淘汰最近最少使用（最不常访问）的数据，而LinkedHashMap访问排序方式是可以轻松的实现此需求的，LinkedHashMap中每次访问的元素（最近访问的数据）放入有序链表的末尾，意思表头是最近最不常使用的数据，所以如果LinkedHashMap实现LRU算法，优先淘汰的是表头的数据。
问题6、LinkedHashMap与HashMap的区别
主要的区别是：LinkedHashMap是插入有序或者访问有序的散列表，而HashMap不是有序散列表
网友评论