007Java集合008详解LinkedHashMap

注意：本文基于JDK1.8进行记录。

不允许插入key值相同的元素，允许插入null的key值。

继承自HashMap，底层由数组、链表、红黑树组成。在此基础上，新增了双向链表，连接了集合中的所有节点，维护了节点的插入顺序。

线程不安全。

同HashMap。

// 指定长度和负载因子的构造器，调用HashMap的构造器。
public linkedHashMap(int initialCapacity, float loadFactor);
// 指定长度的构造器，调用HashMap的构造器。
public linkedHashMap(int initialCapacity);
// 空参构造器，调用HashMap的构造器。
public linkedHashMap();
// 传入了一个集合的构造器，调用HashMap的构造器，添加指定集合。
public linkedHashMap(Map m);
// 指定长度和负载因子以及遍历顺序标志位的构造器，调用HashMap的构造器。
public linkedHashMap(int initialCapacity, float loadFactor, boolean accessOrder);

同HashMap。

在linkedHashMap中，对HashMap的节点进行了扩展，在节点中维护了插入顺序：

static class Entry extends HashMap.Node {
    Entry before, after;
    Entry(int hash, K key, V value, Node next) {
        super(hash, key, value, next);
    }
}

可以看到，仍使用next节点维护节点间的访问顺序，但新增了before节点和after节点维护节点间的插入顺序。

// 双向链表的头节点。
transient linkedHashMap.Entry head;
// 双向链表的尾节点。
transient linkedHashMap.Entry tail;
// 双向链表访问顺序标志位，true表示双向链表按访问顺序排列，false表示双向链表按插入顺序排列。默认为false，可以在构造器中指定。
final boolean accessOrder;

accessOrder用于支持LRU算法，即最近最少使用算法，是一种数据删除方法，表示删除最近一段时间内最少使用的数据。

双向链表是按时间顺序排列的，插入的数据永远在尾部，访问的数据是否要移动到尾部是通过accessOrder判断的：

当accessOrder为true时，访问的数据会被放置到双向链表尾部，表示双向链表是按照访问顺序排列的。

当accessOrder为false时，访问的数据不会被处理，表示双向链表是按照插入顺序排列的。

// 重写newNode()方法，添加双向链表的处理。
Node newNode(int hash, K key, V value, Node e) {
    // 创建节点。
    linkedHashMap.Entry p = new linkedHashMap.Entry(hash, key, value, e);
    // 将节点放在双向链表尾部。
    linkNodeLast(p);
    // 返回节点。
    return p;
}
// 将节点放在双向链表尾部。
private void linkNodeLast(linkedHashMap.Entry p) {
    linkedHashMap.Entry last = tail;
    tail = p;
    if (last == null)
        head = p;
    else {
        p.before = last;
        last.after = p;
    }
}
// 重写get()方法，添加双向链表的处理。
public V get(Object key) {
    Node e;
    // 根据key获取节点。
    if ((e = getNode(hash(key), key)) == null)
        return null;
    // 如果按照访问顺序排列。
    if (accessOrder)
        // 处理访问节点。
        afterNodeAccess(e);
    return e.value;
}
// 处理访问节点，将访问节点移动到双向链表尾部。
void afterNodeAccess(Node e) {
    linkedHashMap.Entry last;
    if (accessOrder && (last = tail) != e) {
        linkedHashMap.Entry p = (linkedHashMap.Entry)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;
    }
}
// 处理插入节点，尝试删除双向链表的首节点。
void afterNodeInsertion(boolean evict) {
    linkedHashMap.Entry first;
    if (evict && (first = head) != null && removeEldestEntry(first)) {
        K key = first.key;
        removeNode(hash(key), key, null, false, true);
    }
}
// 处理删除节点，在双向链表中删除节点。
void afterNodeRemoval(Node e) {
    linkedHashMap.Entry p = (linkedHashMap.Entry)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;
}

// 指定长度和负载因子的构造器，调用HashMap的构造器。
public linkedHashMap(int initialCapacity, float loadFactor) {
    super(initialCapacity, loadFactor);
    accessOrder = false;
}
// 指定长度的构造器，调用HashMap的构造器。
public linkedHashMap(int initialCapacity) {
    super(initialCapacity);
    accessOrder = false;
}
// 空参构造器，调用HashMap的构造器。
public linkedHashMap() {
    super();
    accessOrder = false;
}
// 传入了一个集合的构造器，调用HashMap的构造器，添加指定集合。
public linkedHashMap(Map m) {
    super();
    accessOrder = false;
    putMapEntries(m, false);
}
// 指定长度和负载因子以及遍历顺序标志位的构造器，调用HashMap的构造器。
public linkedHashMap(int initialCapacity, float loadFactor, boolean accessOrder) {
    super(initialCapacity, loadFactor);
    this.accessOrder = accessOrder;
}

同HashMap。