1.LinkedHashMap简介

根据插入顺序简单排序的哈希表实现

2.原理解析

2.1构造器

2.2链表操作

LinkedHashMap.Entry 继承 HashMap.Node<K,V> 实现双向链表结构。

1
2
3
4
5
6
7
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);
    }
}

在 LinkedHashMap 中

2.3Map接口

LinkedHashMap 的 Map 接口实现基本依赖于父类 HashMap 的实现，重写了少部分与排序有关的方法。

  1. 根据key获取value
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    public V get(Object key) {
        Node<K,V> e;
        //getNode()方法是 HashMap 的实现
        if ((e = getNode(hash(key), key)) == null)
            return null;
        //更新链表中的节点顺序
        if (accessOrder)
            afterNodeAccess(e);
        return e.value;
    }

V get(Object key) 方法调用了HashMap的 get(Object key)方法从哈希表中获取节点信息；如果初始时设置了 accessOrder 为 true 时，读取操作后会将被读取节点放置在链表最后，既排序会按照插入顺序与操作顺序结合的方式。

  1. 根据key获取value带默认值
    1
    2
    3
    4
    5
    6
    7
    8
    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;
    }

该方法与上一方法相同，多了节点信息为null时的默认值处理。

  1. 获取key的集合
    1
    2
    3
    4
    5
    6
    7
    8
    public Set<K> keySet() {
        Set<K> ks = keySet;
        if (ks == null) {
            ks = new LinkedKeySet();
            keySet = ks;
        }
        return ks;
    }

在 keySet() 方法中返回的是内部类 LinkedKeySet ，如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
final class LinkedKeySet extends AbstractSet<K> {
    public final int size()                 { return size; }
    public final void clear()               { LinkedHashMap.this.clear(); }
    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);
    }
    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);
        if (modCount != mc)
            throw new ConcurrentModificationException();
    }
}

重点在 forEach(Consumer<? super K> action)方法，可以看到是遍历链表中存放的节点信息，对比以下的 HashMap.KeySet 的 forEach 方法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public final void forEach(Consumer<? super K> action) {
    Node<K,V>[] tab;
    if (action == null)
        throw new NullPointerException();
    if (size > 0 && (tab = table) != null) {
        int mc = modCount;
        for (int i = 0; i < tab.length; ++i) {
            for (Node<K,V> e = tab[i]; e != null; e = e.next)
                action.accept(e.key);
        }
        if (modCount != mc)
            throw new ConcurrentModificationException();
    }
}

HashMap.KeySet 是直接读取哈希表（数组实现）的方式，所有就可以看出 LinkedHashMap 相对 HashMap 额外维护一个双向链表来确定顺序。

  1. 获取Value集合
    1
    2
    3
    4
    5
    6
    7
    8
    public Collection<V> values() {
        Collection<V> vs = values;
        if (vs == null) {
            vs = new LinkedValues();
            values = vs;
        }
        return vs;
    }

values() 和 keySet() 基本一致，实现一个集合 LinkedValues，直接读取链表中存放的节点信息。

  1. 获取entry集合
    1
    2
    3
    4
    public Set<Map.Entry<K,V>> entrySet() {
        Set<Map.Entry<K,V>> es;
        return (es = entrySet) == null ? (entrySet = new LinkedEntrySet()) : es;
    }

entrySet() 与前两个方法一致，实现了一个集合 LinkedEntrySet 来直接读取链表。

  1. forEach 遍历
    1
    2
    3
    4
    5
    6
    7
    8
    9
    public void forEach(BiConsumer<? super K, ? 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.key, e.value);
        if (modCount != mc)
            throw new ConcurrentModificationException();
    }

forEach() 的实现与前三个获取集合的实现一致，直接遍历链表。

  1. replaceAll 批量替换
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    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();
    }

批量替换实际上只是封装了遍历语句，提供函数接口 BiFunction 进行动态操作。

  1. LinkedHashIterator 迭代器

    LinkedHashIterator 迭代器提供了对 LinkedHashMap 内部 Entry 链表的一个迭代器；LinkedValueIterator 与 LinkedEntryIterator 都继承 LinkedHashIterator 实现 key 和 value 的迭代器。