概念

LinkedHashMap继承自HashMap，它的结构如图所示：

• hashmap是无序的，LinkedHashMap是有序的，且默认为插入顺序。

• LinkedHashMap通过在HashMap的基础上增加一条双向链表，实现了插入顺序和访问顺序一致。通过对HashMap一些方法的覆盖,例如newNode, replacementNode, replacementTreeNode, newTreeNode，让所有对底层HashMap数据结构修改的同时该链表进行修改,遍历的时候便是遍历这一条有序的链表。需要注意的是get()方法在accessOrder为true的时候也会对底层结构进行修改。

• 基于get()在accessOrder为true时，会将访问到的元素放到链表的最后的特性，我们可以使用LinkedHashMap实现LRU缓存。

• LinkedHashMap和HashMap一样，线程不安全。

• 另外，leetcode中剑指 Offer 50. 第一个只出现一次的字符 也使用到了这个数据结构。

• 关于访问顺序和插入顺序， 最开始都是按照插入顺序排列的，而如果设置了accessOrder = true， 则在调用get()方法时，会因为 if(accessOrder == true ) 而调用afterNodeAccess方法来调整顺序。

源码分析

get

和hashmap相比，只是在后面增加了if (accessOrder) 代码，目的是实现 LinkedHashMap 按照访问顺序排序。

另外，没有重写getNode()方法，和hashmap一样。

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

afterNodeAccess

就是将一个结点移动到链表尾部

    void afterNodeAccess(Node<K,V> e) {
     // move node to last
        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;
          
          // 如果e为头结点
            if (b == null)
                head = a;
            else
                b.after = a;
          // 如果e为尾结点
            if (a != null)
                a.before = b;
            else
                last = b;
         // 如果链表为空
            if (last == null)
                head = p;
            else {
    
                p.before = last;
                last.after = p;
            }
            tail = p;
            ++modCount;
        }
    }

-------------------

put

LinkedHashMap没有对put和putVal()进行重写，但是对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;
    }

linkNodeLast

private void linkNodeLast(LinkedHashMap.Entry<K,V> p) {
    
        LinkedHashMap.Entry<K,V> last = tail;
        tail = p;
  		// 如果链表为空，则设置p为头部
        if (last == null)
            head = p;
      // 不为空，则放到尾部
        else {
    
            p.before = last;
            last.after = p;
        }
    }

--------------------

remove

LinkedHashMap也没有重写remove()方法，而是重写了removeNode()方法里的afterNodeRemoval()方法

afterNodeRemoval

removeNode()方法中只是将HashMap.Entry的next指针删掉， 而 LinkedHashMap.Entry的 before和after指针还没删除，因此这个方法就是断掉双向链表里的after和before

​

应用

LRU

获取LinkedHashMap的头部元素

时间复杂度O(1)

public <K, V> Entry<K, V> getHead(LinkedHashMap<K, V> map) {
    
    return map.entrySet().iterator().next();
}

获取LinkedHashMap的尾部元素

• 利用迭代器，时间复杂度为 O(n)

public <K, V> Entry<K, V> getTail(LinkedHashMap<K, V> map) {
    
    Iterator<Entry<K, V>> iterator = map.entrySet().iterator();
    Entry<K, V> tail = null;
    while (iterator.hasNext()) {
    
        tail = iterator.next();
    }
    return tail;
}

• 利用反射，时间复杂度为O(1)

	public static  <K, V> Map.Entry<K, V> getTail(LinkedHashMap<K, V> map) throws NoSuchFieldException, IllegalAccessException {
    
		Class<? extends LinkedHashMap> aClass = map.getClass();
		Field tail = aClass.getDeclaredField("tail");
		tail.setAccessible(true);
		return (Map.Entry<K, V>)tail.get(map);
	}