---恢复内容开始---

大多数情况下，只要不涉及线程安全问题，Map基本都可以使用HashMap，不过HashMap有一个问题，就是迭代HashMap的顺序并不是HashMap放置的顺序，也就是无序。HashMap的这一缺点往往会带来困扰，因为有些场景，我们期待一个有序的Map。

这个时候，LinkedHashMap就闪亮登场了，它虽然增加了时间和空间上的开销，但是通过维护一个运行于所有条目的双向链表，LinkedHashMap保证了元素迭代的顺序。

 

四个关注点在LinkedHashMap上的答案

关注点	结论
键值对可以为空	是
重复数据	key可以会覆盖
有序性	有序
线程安全	不安全

 

 

 

 

 

 

 

LinkedHashMap基本数据结构

关于LinkedHashMap，先提两点：

1、LinkedHashMap可以认为是HashMap+LinkedList，即它既使用HashMap操作数据结构，又使用LinkedList维护插入元素的先后顺序

2、LinkedHashMap的基本实现思想就是----多态。可以说，理解多态，再去理解LinkedHashMap原理会事半功倍；反之也是，对于LinkedHashMap原理的学习，也可以促进和加深对于多态的理解。

为什么可以这么说，首先看一下，LinkedHashMap的定义：

public class LinkedHashMap<K,V>
    extends HashMap<K,V>
    implements Map<K,V>
{

看到，LinkedHashMap是HashMap的子类，自然LinkedHashMap也就继承了HashMap中所有非private的方法。再看一下LinkedHashMap中本身的方法：

看到LinkedHashMap中并没有什么操作数据结构的方法，也就是说LinkedHashMap操作数据结构（比如put一个数据），和HashMap操作数据的方法完全一样，无非就是细节上有一些的不同罢了。

LinkedHashMap和HashMap的区别在于它们的基本数据结构上，看一下LinkedHashMap的基本数据结构，也就是Entry：

 /**
 * HashMap.Node subclass for normal LinkedHashMap entries.
 */
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);
    }
}

Entry继承了HashMap中的Node。

列一下Entry里面有的一些属性吧：

• K key
• V value
• Entry<K, V> next
• int hash
• Entry<K, V> before
• Entry<K, V> after

　　其中前面四个，也就是红色部分是从HashMap.Entry中继承过来的；后面两个，也就是蓝色部分是LinkedHashMap独有的。不要搞错了next和before、After，next是用于维护HashMap指定table位置上连接的Entry的顺序的，before、After是用于维护Entry插入的先后顺序的。

 

先看LinkedList的构造方法：

 

public LinkedHashMap() {
        super();
        accessOrder = false;
}

 

可以看出，它是直接使用了HashMap()的构造方法，acccessOrder=false时表示访问顺序等于插入元素的顺序。

 

LinkedHashMap添加元素

 

它并没有重写put(key,value)方法，因此是直接复用了HashMap的put()方法. 而在put()方法中，使用到了newNode()方法新建新节点，而在LinkedHashMap中，重写了newNode()方法。

LinkedHashMap的newNode()方法：

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;
    }
}

 

查找方法get()

 

 1  public V get(Object key) {
 2     Node<K,V> e;
 3     if ((e = getNode(hash(key), key)) == null)
 4         return null;
 5     if (accessOrder)
 6         // 当accessOrder为true的时候会进入这个方法
 7         afterNodeAccess(e);
 8     return e.value;
 9 }
10 
11 /**
12     把节点移动到链表最后
13 */
14 void afterNodeAccess(Node<K,V> e) { // move node to last
15     LinkedHashMap.Entry<K,V> last;
16     // 如果e不是最后一个节点
17     if (accessOrder && (last = tail) != e) {
18         // 获取p的前置和后置节点
19         LinkedHashMap.Entry<K,V> p =
20             (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
21         // 置空
22         p.after = null;
23         // 如果p的前置为空，则p原来就是头节点
24         if (b == null)
25             head = a;
26         else
27             b.after = a;
28         if (a != null)
29             a.before = b;
30         else
31             // 如果a为空，则原来p是尾节点
32             last = b;
33         if (last == null)
34             head = p;
35         else {
36             // 把p连接到链尾
37             p.before = last;
38             last.after = p;
39         }
40         tail = p;
41         ++modCount;
42     }
43 }

 

LinkedHashMap中有一个accessOrder字段，它的默认值为false，作用是：

（1）false，所有的Entry按照插入的顺序排列

（2）true，所有的Entry按照访问的顺序排列

第二点的意思就是，如果有1 2 3这3个Entry，那么访问了1，就把1移到尾部去，即2 3 1。每次访问都把访问的那个数据移到双向队列的尾部去，那么每次要淘汰数据的时候，双向队列最头的那个数据不就是最不常访问的那个数据了吗？换句话说，双向链表最头的那个数据就是要淘汰的数据。

"访问"，这个词有两层意思：

1、根据Key拿到Value，也就是get方法

2、修改Key对应的Value，也就是put方法

从上面的源码可以看到，当accessOrder为true的时候，就会把要访问的节点移到双向链表的链尾，这样我们得出结论，如果当accessOrder为ture时，链尾的节点就是我们最新访问过的节点，而链头的节点是离访问时间最远的节点。

这样，LinkedHashMap可以作为一个LRU缓存结构，所谓的LRU，就是Least Recently Used - 最近最少使用。