LinkedHashMap原理和源码分析详解编程语言

上两篇文章分别介绍了《HashMap的原理和源码解析》和《HashTable的原理和源码解析》，至此，第三篇文章就是LinkedHashMap的原理特性介绍以及部分源码的解析。

LinkedHashMap的特性

1. LinkedHashMap 直接继承HashMap，所以基础特性、数据结构都没什么变化。

2. LinkedHashMap 在HashMap的基础上，新增一个双向链表，每个Node增加了一个before，after，表示上一个结点和下一个结点。不过，双向链表顺序是根据插入或者访问顺序来决定的。before、after跟hashMap的next表达的含义是不一样的，next表示hash桶内部顺序，而before、after表示插入或访问顺序。

   

3. 在上面的图可以很清晰的看到，蓝色的线表示的就是访问或者顺序，串联成为一个双向链表。由此也可以猜想到LinkedHashMap的原理，就是在HashMap插入、访问、删除等操作后，及时修改LinkedHashMap的双向链表，维持顺序。

LinkedHashMap 源码分析

重要的数据结构

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

LinkedHashMapEntry继承自HashMap的Node，内部多了before, after，形成一个双向链表。

transient LinkedHashMapEntry<K,V> head; // 双向链表头部结点 
 
transient LinkedHashMapEntry<K,V> tail; // 双向链表尾部结点 
 
final boolean accessOrder;// 是否按照访问顺序排序，若false，则按照插入顺序 

接下来看下LinkedHashMap内部常用的比较重要的方法：

// 插入P结点到链表尾部 
private void linkNodeLast(LinkedHashMapEntry<K,V> p) {
    
    LinkedHashMapEntry<K,V> last = tail; 
    tail = p; 
    if (last == null) 
        head = p; 
    else {
    
        p.before = last; 
        last.after = p; 
    } 
} 

linkNodeLast 顾名思义就是把结点P挂在链表尾部，如果链表为空，就将P设置为头节点。

// 将中间的src节点（链表）替换成 dest 节点（链表） 
private void transferLinks(LinkedHashMapEntry<K,V> src, LinkedHashMapEntry<K,V> dst) {
    
    LinkedHashMapEntry<K,V> b = dst.before = src.before; 
    LinkedHashMapEntry<K,V> a = dst.after = src.after; 
    if (b == null) // dst.before为null，说明是头节点 
        head = dst; // 设置成头节点 
    else 
        b.after = dst; 
    if (a == null) 
        tail = dst; 
    else 
        a.before = dst; 
} 

将中间的src节点（链表）替换成 dest 节点（链表），src、dest既可以表示链表头部也可以表示单独结点。

直接看上面的转换可能会有点难以理解的，如果参照下面的图会清晰很多。

几个重要的方法

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; 
    } 
 
    Node<K,V> replacementNode(Node<K,V> p, Node<K,V> next) {
    
        LinkedHashMapEntry<K,V> q = (LinkedHashMapEntry<K,V>)p; 
        LinkedHashMapEntry<K,V> t = 
            new LinkedHashMapEntry<K,V>(q.hash, q.key, q.value, next); 
        transferLinks(q, t); 
        return t; 
    } 
 
    TreeNode<K,V> newTreeNode(int hash, K key, V value, Node<K,V> next) {
    
        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) {
    
        LinkedHashMapEntry<K,V> q = (LinkedHashMapEntry<K,V>)p; 
        TreeNode<K,V> t = new TreeNode<K,V>(q.hash, q.key, q.value, next); 
        transferLinks(q, t); 
        return t; 
    } 

以上的方法都是重写了HashMap的方法，操作基本是相同的：

1. 将LinkedHashMapEntry替换掉Node；
2. 修改LinkedHashMap的双向链表，插入或者替换节点，维持顺序。

例如：newNode方法，外部调用newNode获取一个新结点，而内部生成LinkedHashMapEntry，并插入LinkedhashMap内部链表的尾部。同理，replacementNode也是修改了链表。

再来看三个重要的方法

这几个方法在HashMap中都是空实现，但LinkedHashMap重写了，全都是HashMap在一些操作之后调用，例如插入、删除操作后。

1. afterNodeRemoval

// HashMap删除hash桶中的结点之后调用，负责将节点从双向链表移除 
void afterNodeRemoval(Node<K,V> e) {
    // unlink 
        LinkedHashMapEntry<K,V> p = 
            (LinkedHashMapEntry<K,V>)e, b = p.before, a = p.after; 
        p.before = p.after = null; 
        if (b == null) 
            head = a; 
        else 
            b.after = a; 
        if (a == null) 
            tail = b; 
        else 
            a.before = b; 
    } 

2. afterNodeInsertion

	// HashMap插入结点之后调用，eveict表示是否移除最老的hash结点（首结点） 
    void afterNodeInsertion(boolean evict) {
    // possibly remove eldest 
        LinkedHashMapEntry<K,V> first; 
        if (evict && (first = head) != null && removeEldestEntry(first)) {
    
            K key = first.key; 
            removeNode(hash(key), key, null, false, true);// 需要移除最老的节点 
        } 
    } 
     
  	// 是否移除最老的节点，默认是false 
    protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
    
        return false; 
    } 

newNode 和 afterNodeInsertion 都是在新增结点操作中引发的，但是负责的事情不一样。

• newNode 负责新增一个结点，并将结点添加到双向链表中；
• afterNodeInsertion 负责在新增结点完成后，可能需要移除最老的结点（首结点），如LruCache。

3. afterNodeAccess

    // hashmap调用get、replace等访问节点方法会调用 
   // 如果accessOrders是true，会将访问的节点移动到尾部，表示最新节点 
    void afterNodeAccess(Node<K,V> e) {
    // move node to last 
        LinkedHashMapEntry<K,V> last; 
        if (accessOrder && (last = tail) != e) {
    
            LinkedHashMapEntry<K,V> p = 
                (LinkedHashMapEntry<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; 
        } 
    } 

4. entrySet
   返回一个 LinkedEntrySet，内部遍历是有序的，根据双向链表进行访问

public Set<Map.Entry<K,V>> entrySet() {
    
    Set<Map.Entry<K,V>> es; 
    return (es = entrySet) == null ? (entrySet = new LinkedEntrySet()) : es; 
} 
 
final class LinkedEntrySet extends AbstractSet<Map.Entry<K,V>> {
    
	... 
	public final Iterator<Map.Entry<K,V>> iterator() {
    
        return new LinkedEntryIterator(); 
    } 
} 
 
final class LinkedEntryIterator extends LinkedHashIterator 
    implements Iterator<Map.Entry<K,V>> {
    
    public final Map.Entry<K,V> next() {
    return nextNode(); } 
} 

顺着再看下LinkedHashIterator怎么实现的

abstract class LinkedHashIterator {
    
    LinkedHashMapEntry<K,V> next; 
    LinkedHashMapEntry<K,V> current; 
    int expectedModCount; 
 
    LinkedHashIterator() {
    
        next = head;// 双向链表首节点 
        expectedModCount = modCount; 
        current = null; 
    } 
 
    final LinkedHashMapEntry<K,V> nextNode() {
    
        LinkedHashMapEntry<K,V> e = next; 
        if (modCount != expectedModCount) 
            throw new ConcurrentModificationException(); 
        if (e == null) 
            throw new NoSuchElementException(); 
        current = e; 
        next = e.after; 
        return e; 
    } 
    ... 
} 

在LinkedHashIterator 构造函数中，next被赋为首节点，每次nextNode()就顺着LinkHashMap的双向链表往后访问，这样就能维持entrySet()的有序访问