Java集合(九) —— LinkedHashMap源码分析

Java集合(一) —— Collection源码分析
Java集合(二) —— ArrayList源码分析
Java集合(三) —— LinkedList源码分析
Java集合(四) —— PriorityQueue源码分析
Java集合(五) —— HashSet源码分析
Java集合(六) —— LinkedHashSet源码分析
Java集合(七) —— TreeSet源码分析
Java集合(八) —— HashMap源码分析
Java集合(九) —— LinkedHashMap源码分析
Java集合(十) —— TreeMap源码分析

1.总结

1.LinkedHashMap继承自HashMap，所以HashMap有的特性LinkedHashMap都有，比如数据结构为数组+链表+红黑树，默认容量为16，负载因子为0.75等(HashMap源码分析)。
2.LinkedHashMap使用双向链表维持数据的插入顺序或访问顺序(默认是以插入顺序排序)。
3.当以访问顺序排序时，被访问的节点都要从当前位置移到链表尾部。

2.继承关系图

LinkedHashMap.png

3.源码分析

3.1成员变量分析

// 双向链表的头结点
transient LinkedHashMap.Entry<K,V> head;

// 双向链表的尾结点
transient LinkedHashMap.Entry<K,V> tail;

// 排序方式，false：插入顺序；true：访问顺序
final boolean accessOrder;

3.2构造方法分析

/**
 * 指定初始化容量和负载因子
 * accessOrder：默认都为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;
}

/**
 * 用已存在的map初始化LinkedHashMap
 */
public LinkedHashMap(Map<extends K, extends V> m) {
    super();
    accessOrder = false;
    putMapEntries(m, false);
}

public LinkedHashMap(int initialCapacity,
                     float loadFactor,
                     boolean accessOrder) {
    super(initialCapacity, loadFactor);
    this.accessOrder = accessOrder; // 指定是否以访问顺序排序
}

3.3常用方法分析

1.put方法

调用的就是HashMap的put方法，不同的是LinkedHashMap重写了newNode方法，实现了afterNodeAccess和afterNodeInsertion方法

/**
 * 新建节点，新节点接在双向链表尾部
 */
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;
    // 将尾结点指向p
    tail = p;
    // 如果last为null，表示链表还没有建立
    if (last == null)
        head = p;
    else {
        // 将新节点接到链表尾部，新节点的前向指针指向last，last的后继指针指向新节点
        p.before = last;
        last.after = p;
    }
}

再看看实现的两个方法：

• afterNodeAccess方法

void afterNodeAccess(Node<K,V> e) { // move node to last 将节点移到链表最后
    LinkedHashMap.Entry<K,V> last;
    // 当以访问顺序排序，且e不是尾结点时
    if (accessOrder && (last = tail) != e) {
        // p => e; b => p的前驱; a => p的后继
        LinkedHashMap.Entry<K,V> p =
            (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
        p.after = null;
        if (b == null) // 表示p原先为头节点
            // 将p移到链表尾部后，p的后继节点a成为头结点
            head = a;
        else
            // 否则将b的后继指向a（此时p从链表中删除，将断开的链表重新连接起来）
            b.after = a;
        if (a != null)
            // a不为null，则a的前驱指向b
            a.before = b;
        else
            // 否则b成为最后一个节点
            last = b;
        if (last == null)
            // 链表只有p节点，将头结点指向p
            head = p;
        else {
            // 否则将p节点连接到链表尾部
            p.before = last;
            last.after = p;
        }
        // 尾结点指向p
        tail = p;
        ++modCount;
    }
}

• afterNodeInsertion方法

void afterNodeInsertion(boolean evict) { // possibly remove eldest
    LinkedHashMap.Entry<K,V> first;
    if (evict && (first = head) != null && removeEldestEntry(first)) {
        K key = first.key;
        // 删除节点
        removeNode(hash(key), key, null, false, true);
    }
}

protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
    return false;
}

从源码可以看到，需要同时满足三个条件才会才会进入if语句
1.evict为true
2.first不为null
3.removeEldestEntry(first)方法返回true
然而默认的removeEldestEntry(first)始终返回false，也就是说默认不会删除节点。removeEldestEntry(first)用于定义删除最老元素的规则。

2.get方法

public V get(Object key) {
    Node<K,V> e;
    // getNode()方法为查找节点的具体实现，在HashMap中已经分析过，这里不再说明
    if ((e = getNode(hash(key), key)) == null)
        return null;
    // 如果accessOrder为true，表示以访问顺序排序
    if (accessOrder)
        // 调整链表，将访问的节点移到链表尾部
        afterNodeAccess(e);
    return e.value;
}

3.remove方法

调用的就是HashMAp的remove方法，不同的是LinkedHashMap实现了afterNodeRemoval方法。

/**
 * e：待删除节点
 */
void afterNodeRemoval(Node<K,V> e) { // unlink
    LinkedHashMap.Entry<K,V> p =
        (LinkedHashMap.Entry<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;
}

afterNodeRemoval()实现从双向链表中删除节点，并将断开的链表重新连接起来。

4.entrySet，keySet，values方法

entrySet，keySet，values与HashMap中的这三个方法大同小异，其中entrySet和keySet通过迭代器将键值对/键映射到entrySet和keySet上，values是一个Collection集合：

/**
 * 跟HashMap的实现是一样的
 */
public Collection<V> values() {
    Collection<V> vs = values;
    if (vs == null) {
        vs = new LinkedValues();
        values = vs;
    }
    return vs;
}