JDK源码学习系列09----LinkedHashMap

之前的博客已经分析了HashMap的源码，当遍历其内数据时是无序的，而当我们要按照元素插入的顺序来访问键-值对，就需要用到LinkedHashMap。他保持着元素的插入顺序，并可以按照我们的插入顺序进行访问。

LinkedHashMap 类结构

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

LinkedHashMap 继承了HashMap, 后续仔细阅读源码也可以发现，两者之间有许多相似之处，我们只需要 着眼于他们的不同之处即可。

LinkedHashMap 的数据结构

LinkedHashMap 在HashMap“数组+链表+红黑数”的基础上添加了双向不循环链表结构，用于记录节点的存入顺序。

具体代码从源码中的基础存储节点就可以看出：

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的存储节点的基础上又添加了对前后节点的引用。

LinkedHashMap 源码分析

   由于之前已经分析过HashMap的源码，因此这次主要对二者间的不同进行着重分析。

类的成员属性

除了从父类继承的属性外，还有两个LinkedHashMap.Entry<K,V>类型的属性，用于表示双向链表的头尾节点。还有一个布尔类型的属性表示访问顺序。

public class LinkedHashMap<K,V> extends HashMap<K,V> implements Map<K,V>
{ 
    /**
     * 双向链表头节点
     */
    transient LinkedHashMap.Entry<K,V> head;

    /**
     * 双向链表尾节点
     */
    transient LinkedHashMap.Entry<K,V> tail;
    
    /**
     * 访问顺序
     */
    final boolean accessOrder;
}

构造方法

LinkedHashMap的构造方法基本与HashMap一致, 在创建对象时都不会对数组进行初始化，而是在创建时进行。同时初始化数组时会指定排序顺序（默认为false）

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;
    //调用父类HashMap中的putMapentries()方法
    putMapEntries(m, false);
}

public LinkedHashMap(int initialCapacity,
                     float loadFactor,
                     boolean accessOrder) {
    super(initialCapacity, loadFactor);
    this.accessOrder = accessOrder;
}

重要函数分析

newNode

Node<K,V> newNode(int hash, K key, V value, Node<K,V> e) {
    // 生成Node结点
    LinkedHashMap.Entry<K,V> p =
        new LinkedHashMap.Entry<K,V>(hash, key, value, e);
    //将节点添加至双向链表尾部
    linkNodeLast(p);
    return p;
}

重写了父类HashMap中的newNode()方法主要加入了linkedNodeLast()方法， 将新建的节点添加至双向链表末尾。当LinkedHashMap存储数据时，会调用putValue()方法，进而调用newNode方法。

afterNodeAccess

void afterNodeAccess(Node<K,V> e) { // move node to last
    LinkedHashMap.Entry<K,V> last;
    //根据调用前的代码可以看出，次数的条件为accessOrder == true 且 添加的数据的key在原来的Map中存在，且访问的节点不是双向链表尾节点
    // 因此这个条件可以看为如果accessOrder == true将更新的节点放至双向链表尾部
    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;
    }
}

具象化数据结构如下：

get

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

当accessOrder为true时， 也会讲取得的节点放到链表末尾

containsValue

public boolean containsValue(Object value) {
    for (LinkedHashMap.Entry<K,V> e = head; e != null; e = e.after) {
        V v = e.value;
        if (v == value || (value != null && value.equals(v)))
            return true;
    }
    return false;
}

LinkedHashMap 判断value是否存在时，遍历双向链表去查找。效率与HashMap基本一致