LinkedHashMap 的原理与使用

LinkedHashMap 是对 HashMap 的封装和拓展，在保留了 HashMap 原有功能的基础上，加了一些链表相关的属性，用来记录 HashMap 元素的先后顺序，这样如果要根据（节点插入或访问）顺序访问节点时，只要去遍历链表即可。

默认元素插入顺序排序：

@Test
public void test1() {
    LinkedHashMap map = new LinkedHashMap();
    map.put("222", 222);
    map.put("111", 111);
    map.put("333", 333);

    System.out.println("遍历迭代器：");
    Iterator iterator = map.entrySet().iterator();
    while (iterator.hasNext()) {
        Map.Entry entry = (Map.Entry) iterator.next();
        System.out.println(entry.getKey() + ": " + entry.getValue());
    }

    System.out.println("遍历map：");
    map.forEach((k, v) -> {
        System.out.println(k + ": " + v);
    });

    /**
         * 执行结果：
         *
         * 遍历迭代器：
         * 222: 222
         * 111: 111
         * 333: 333
         * 遍历map：
         * 222: 222
         * 111: 111
         * 333: 333
         */
}

按照元素访问顺序排序：

@Test
public void test2() {
    LinkedHashMap map = new LinkedHashMap(4, 0.8f, true);
    map.put("222", 222);
    map.put("111", 111);
    map.put("333", 333);

    map.get("333");
    map.get("111");
    map.get("222");

    System.out.println("遍历迭代器：");
    Iterator iterator = map.entrySet().iterator();
    while (iterator.hasNext()) {
        Map.Entry entry = (Map.Entry) iterator.next();
        System.out.println(entry.getKey() + ": " + entry.getValue());
    }

    System.out.println("遍历map：");
    map.forEach((k, v) -> {
        System.out.println(k + ": " + v);
    });

    /**
         * 执行结果：
         * 
         * 遍历迭代器：
         * 333: 333
         * 111: 111
         * 222: 222
         * 遍历map：
         * 333: 333
         * 111: 111
         * 222: 222
         */
}

LinkedHashMap 源码解析

内部类

Entry

static class Entry<K,V> extends HashMap.Node<K,V> {
    // before 指向此节点的前一个节点
    // after 指向此节点的后一个节点
    Entry<K,V> before, after;
    // Entry 构造方法，内部是调用了父类 HashMap 的构造方法
    Entry(int hash, K key, V value, Node<K,V> next) {
        super(hash, key, value, next);
    }
}

LinkedKeySet

// LinkedHashMap 中所有节点元素的 key 集合
final class LinkedKeySet extends AbstractSet<K> {
    public final int size()                 { return size; }
    public final void clear()               { LinkedHashMap.this.clear(); }
    // 获取 key 迭代器
    public final Iterator<K> iterator() {
        return new LinkedKeyIterator();
    }
    public final boolean contains(Object o) { return containsKey(o); }
    public final boolean remove(Object key) {
        return removeNode(hash(key), key, null, false, true) != null;
    }
    public final Spliterator<K> spliterator()  {
        return Spliterators.spliterator(this, Spliterator.SIZED |
                                        Spliterator.ORDERED |
                                        Spliterator.DISTINCT);
    }
    // 遍历所有 key
    public final void forEach(Consumer<? super K> action) {
        if (action == null)
            throw new NullPointerException();
        int mc = modCount;
        for (LinkedHashMap.Entry<K,V> e = head; e != null; e = e.after)
            action.accept(e.key);
        // 遍历时不能修改该 LinkedHashMap 对象
        if (modCount != mc)
            throw new ConcurrentModificationException();
    }
}

LinkedValues

// LinkedHashMap 中所有节点元素的 value 集合
final class LinkedValues extends AbstractCollection<V> {
    public final int size()                 { return size; }
    public final void clear()               { LinkedHashMap.this.clear(); }
    public final Iterator<V> iterator() {
        return new LinkedValueIterator();
    }
    public final boolean contains(Object o) { return containsValue(o); }
    public final Spliterator<V> spliterator() {
        return Spliterators.spliterator(this, Spliterator.SIZED |
                                        Spliterator.ORDERED);
    }
    // 遍历所有 value
    public final void forEach(Consumer<? super V> action) {
        if (action == null)
            throw new NullPointerException();
        int mc = modCount;
        for (LinkedHashMap.Entry<K,V> e = head; e != null; e = e.after)
            action.accept(e.value);
        if (modCount != mc)
            throw new ConcurrentModificationException();
    }
}

LinkedEntrySet

// LinkedHashMap 中所有节点元素的 entry 对象集合
final class LinkedEntrySet extends AbstractSet<Map.Entry<K,V>> {
    public final int size()                 { return size; }
    public final void clear()               { LinkedHashMap.this.clear(); }
    public final Iterator<Map.Entry<K,V>> iterator() {
        return new LinkedEntryIterator();
    }
    public final boolean contains(Object o) {
        if (!(o instanceof Map.Entry))
            return false;
        Map.Entry<?,?> e = (Map.Entry<?,?>) o;
        Object key = e.getKey();
        Node<K,V> candidate = getNode(hash(key), key);
        return candidate != null && candidate.equals(e);
    }
    public final boolean remove(Object o) {
        if (o instanceof Map.Entry) {
            Map.Entry<?,?> e = (Map.Entry<?,?>) o;
            Object key = e.getKey();
            Object value = e.getValue();
            return removeNode(hash(key), key, value, true, true) != null;
        }
        return false;
    }
    public final Spliterator<Map.Entry<K,V>> spliterator() {
        return Spliterators.spliterator(this, Spliterator.SIZED |
                                        Spliterator.ORDERED |
                                        Spliterator.DISTINCT);
    }
    public final void forEach(Consumer<? super Map.Entry<K,V>> action) {
        if (action == null)
            throw new NullPointerException();
        int mc = modCount;
        for (LinkedHashMap.Entry<K,V> e = head; e != null; e = e.after)
            action.accept(e);
        if (modCount != mc)
            throw new ConcurrentModificationException();
    }
}

LinkedHashIterator

// 迭代器
abstract class LinkedHashIterator {
    LinkedHashMap.Entry<K,V> next;
    LinkedHashMap.Entry<K,V> current;
    int expectedModCount;

    LinkedHashIterator() {
        next = head;
        expectedModCount = modCount;
        current = null;
    }

    // 是否有下个节点
    public final boolean hasNext() {
        return next != null;
    }

    // 返回下一个节点
    final LinkedHashMap.Entry<K,V> nextNode() {
        LinkedHashMap.Entry<K,V> e = next;
        if (modCount != expectedModCount)
            throw new ConcurrentModificationException();
        if (e == null)
            throw new NoSuchElementException();
        // 当前遍历到的节点
        current = e;
        // next 指向下一个要遍历的节点
        next = e.after;
        return e;
    }

    public final void remove() {
        Node<K,V> p = current;
        if (p == null)
            throw new IllegalStateException();
        if (modCount != expectedModCount)
            throw new ConcurrentModificationException();
        current = null;
        K key = p.key;
        removeNode(hash(key), key, null, false, false);
        expectedModCount = modCount;
    }
}

LinkedKeyIterator

// key 迭代器
final class LinkedKeyIterator extends LinkedHashIterator
    implements Iterator<K> {
    // 返回下一个节点的 key
    public final K next() { return nextNode().getKey(); }
}

LinkedValueIterator

// value 迭代器
final class LinkedValueIterator extends LinkedHashIterator
    implements Iterator<V> {
    // 返回下一个节点的 value 值
    public final V next() { return nextNode().value; }
}

LinkedEntryIterator

// entry 迭代器
final class LinkedEntryIterator extends LinkedHashIterator
    implements Iterator<Map.Entry<K,V>> {
    // 返回下一个节点的 entry 对象
    public final Map.Entry<K,V> next() { return nextNode(); }
}

属性

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

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

// 链表节点的排序规则：
// accessOrder 为 true，根据访问顺序排序
// accessOrder 为 false，根据插入顺序排序
final boolean accessOrder;

构造方法

// 默认是插入排序
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;
    putMapEntries(m, false);
}

// 可以指定元素排序方式 accessOrder
/**
     * Constructs an empty <tt>LinkedHashMap</tt> instance with the
     * specified initial capacity, load factor and ordering mode.
     *
     * @param  initialCapacity the initial capacity
     * @param  loadFactor      the load factor
     * @param  accessOrder     the ordering mode - <tt>true</tt> for
     *         access-order, <tt>false</tt> for insertion-order
     * @throws IllegalArgumentException if the initial capacity is negative
     *         or the load factor is nonpositive
     */
public LinkedHashMap(int initialCapacity,
                     float loadFactor,
                     boolean accessOrder) {
    super(initialCapacity, loadFactor);
    this.accessOrder = accessOrder;
}

方法

linkNodeLast

// 将节点 p 插入到链表的尾部
private void linkNodeLast(LinkedHashMap.Entry<K,V> p) {
    // 记录旧的尾结点
    LinkedHashMap.Entry<K,V> last = tail;
    // 更新 tail 指针，指向新插入的尾结点 p
    tail = p;
    // 如果插入前尾结点为 null，则表示链表当前无节点，
    // 则 head 结点也指向新插入的第一个节点 p
    if (last == null)
        head = p;
    else { // 链表不为空，直接将 p 插入到链表尾部
        p.before = last;
        last.after = p;
    }
}

transferLinks

// 用 dst 节点替换掉原来的 src 结点
private void transferLinks(LinkedHashMap.Entry<K,V> src,
                           LinkedHashMap.Entry<K,V> dst) {
    // dst 的 before 指针指向 src 的 before 指针指向的节点
    LinkedHashMap.Entry<K,V> b = dst.before = src.before;
    // dst 的 after 指针指向 src 的 after 指针指向的节点
    LinkedHashMap.Entry<K,V> a = dst.after = src.after;
    
    // b 也指向 src.before
    // b 为 null，说明 src 是头结点，则现在 dst 也是头结点
    if (b == null)
        head = dst;
    else
        // 如果 src 不是头结点，则因为 dst 已经指向了 src.before
        // 所以现在只要将 src.before 指向的前序节点的 after 指针指向 dst 即可完成 dst 节点插入操作
        b.after = dst;
    
    // 同上
    if (a == null)
        tail = dst;
    else
        a.before = dst;
}

newNode

// 插入一个 HashMap 的节点到链表尾部，并返回插入后的 LinkedHashMap 节点
// LinkedHashMap 继承了 HashMap 类，在调用 put 方法时，会调用 newNode 方法
// linkNodeLast 方法是按照元素插入顺序进行排序（将元素插入到链表尾部）
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;
}

replacementNode

Node<K,V> replacementNode(Node<K,V> p, Node<K,V> next) {
    LinkedHashMap.Entry<K,V> q = (LinkedHashMap.Entry<K,V>)p;
    // 使用 HashMap 节点 next 构造一个 LinkedHashMap 节点 t
    LinkedHashMap.Entry<K,V> t =
        new LinkedHashMap.Entry<K,V>(q.hash, q.key, q.value, next);
    // 然后用新构造的节点 t 替换原来的节点 p
    transferLinks(q, t);
    // 返回新构造的节点 t
    return t;
}

newTreeNode

// 同 newNode 方法
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;
}

replacementTreeNode

// 同 replacementNode 方法
TreeNode<K,V> replacementTreeNode(Node<K,V> p, Node<K,V> next) {
    LinkedHashMap.Entry<K,V> q = (LinkedHashMap.Entry<K,V>)p;
    TreeNode<K,V> t = new TreeNode<K,V>(q.hash, q.key, q.value, next);
    transferLinks(q, t);
    return t;
}

afterNodeRemoval

// 删除节点 e
void afterNodeRemoval(Node<K,V> e) { // unlink
    // 将 e 转成 LinkedHashMap  节点 p
    // b 指向 p 的 before 节点
    // a 指向 p 的 after 节点
    LinkedHashMap.Entry<K,V> p =
        (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
    // 将 p.before 和 p.after 置空，即删除节点 p
    p.before = p.after = null;
    // 如果 b 为 null，表示 p 是链表第一个节点
    if (b == null)
        // 则 head 指向 p 的下一个节点（p.after）
        head = a;
    else
        // 如果 b（p.before）不为空
        // 则 p 的前序节点的（b） after 指针指向 p 的 after 节点（a）
        b.after = a;
    
    // 如果 a 为空，表示 p 是链表的最后一个节点
    if (a == null)
        // 则 p.before 节点 b 现在是链表的最后一个节点，则更新 tail 节点
        tail = b;
    else
        // 如果 a 不为空
        // 则 p 的后继节点的（a） before 指针指向 p 的 before 节点（b）
        a.before = b;
}

afterNodeInsertion

// 节点插入 HashMap 后的钩子方法
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);
    }
}

afterNodeAccess

// 访问了 HashMap 节点后的钩子方法
void afterNodeAccess(Node<K,V> e) { // move node to last
    LinkedHashMap.Entry<K,V> last;
    // 如果 accessOrder 为 true
    // 并且 e 不为链表的尾结点
    // 则根据节点的访问顺序将节点排序，即将访问的节点 e 移动到链表的尾部
    if (accessOrder && (last = tail) != e) {
        // 将节点 e 转成 LinkedHashMap 节点 p
        LinkedHashMap.Entry<K,V> p =
            (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
        // 要将节点 p 移动到链表的尾部
        // 所以将 p.after 置空
        p.after = null;
        // 如果 b 为 null，则 p 原先为头结点
        if (b == null)
            // 现在要将 p 移动到链表尾部
            // 则 p 的后继节点 a 现在为头结点
            head = a;
        else
            // 如果 b 不为 null
            // 则将 p 的前序节点（b）的后继节点（b.after）指向 p 的后继节点（a）
            b.after = a;
        // 如果 a 不为空，则表示 p 不为尾结点
        if (a != null)
            // 则将 p 的后继节点（a）的前序节点（a.before）指向 p 的前序节点（b）
            a.before = b;
        else
            // 否则 p 为链表的尾结点
            // 使用 last 记录 p 的前序节点 b
            // （外层判断了 p 不能为尾节点）
            last = b;
        
        // 上面 last 记录了 p 的前序节点 b
        // 如果 b 为 null
        if (last == null)
            // 则链表中只有 p 这一个节点
            head = p;
        else { // 将 p 移到链表尾部
            p.before = last;
            last.after = p;
        }
        // 尾结点指向 p
        tail = p;
        ++modCount;
    }
}

containsValue

// 判断链表节点中是否有值为 value 的
public boolean containsValue(Object value) {
    // 从头结点开始遍历链表
    for (LinkedHashMap.Entry<K,V> e = head; e != null; e = e.after) {
        V v = e.value;
        // 如果链表节点元素值等于 value
        if (v == value || (value != null && value.equals(v)))
            // 则返回 true
            return true;
    }
    return false;
}

get

// 根据 key 获取节点元素的值
public V get(Object key) {
    Node<K,V> e;
    // 根据 key 找不到元素，则直接返回 null
    if ((e = getNode(hash(key), key)) == null)
        return null;
    // 根据 key 找到了元素，则判断是否根据访问顺序排序
    if (accessOrder)
        afterNodeAccess(e);
    return e.value;
}

getOrDefault

// 根据 key 获取节点元素的值，如果获取不到，则返回默认值 defaultValue
public V getOrDefault(Object key, V defaultValue) {
    Node<K,V> e;
    if ((e = getNode(hash(key), key)) == null)
        return defaultValue;
    if (accessOrder)
        afterNodeAccess(e);
    return e.value;
}

keySet

transient Set<K>        keySet;

// 所有所有 key 的集合
public Set<K> keySet() {
    // 获取 keySet
    Set<K> ks = keySet;
    // 如果 keySet 为空
    if (ks == null) {
        // 则构造一个 LinkedKeySet 对象
        ks = new LinkedKeySet();
        keySet = ks;
    }
    return ks;
}

values

public Collection<V> values() {
    Collection<V> vs = values;
    if (vs == null) {
        vs = new LinkedValues();
        values = vs;
    }
    return vs;
}

entrySet

public Set<Map.Entry<K,V>> entrySet() {
    Set<Map.Entry<K,V>> es;
    return (es = entrySet) == null ? (entrySet = new LinkedEntrySet()) : es;
}

forEach

// 遍历
public void forEach(BiConsumer<? super K, ? super V> action) {
    if (action == null)
        throw new NullPointerException();
    int mc = modCount;
    // 从 head 结点开始遍历节点
    for (LinkedHashMap.Entry<K,V> e = head; e != null; e = e.after)
        action.accept(e.key, e.value);
    if (modCount != mc)
        throw new ConcurrentModificationException();
}

replaceAll

public void replaceAll(BiFunction<? super K, ? super V, ? extends V> function) {
    if (function == null)
        throw new NullPointerException();
    int mc = modCount;
    for (LinkedHashMap.Entry<K,V> e = head; e != null; e = e.after)
        e.value = function.apply(e.key, e.value);
    if (modCount != mc)
        throw new ConcurrentModificationException();
}