LinkedHashMap

Synopsis

LinkedHashMap 是将 HashMap 和双向链表相结合的产物，拥有了 HashMap 的特性外还保持了迭代的顺序。LRU Cache 内部就是通过 LinkedHashMap 实现的。

LinkedHashMap 与 HashMap 有什么不同

• 结点不同
  LinkedHashMap 的结点是继承自 HashMap.Node，并添加了 before 和 after 指针，用于维护节点的插入顺序，使得节点形成双向链表。
• put 操作不同
  在执行 put 操作后，Entry 都是保存在 HashMap 中的，LinkedHashMap 还会将 Entry 放到链表的尾部。

  source code

  我们来看一下比较重要的伪代码（省略了很多类似 clear 之类的代码）：

  public class LinkedHashMap<K,V>
    extends HashMap<K,V>
    implements Map<K,V> {
  
    /**
     * 重新定义 Node，增加了 before 和 after 用于维护双向链表。
     * next 用于维护 HashMap 各个桶中的 Entry 的连接顺序；
     * before 和 after 维护 entry 插入的先后顺序
     */
    static class LinkedHashMapEntry<K,V> extends HashMap.Node<K,V> {
        LinkedHashMapEntry<K,V> before, after;
        LinkedHashMapEntry(int hash, K key, V value, Node<K,V> next) {
            super(hash, key, value, next);
        }
    }
  
    //双向链表的头结点和尾结点
    transient LinkedHashMapEntry<K,V> head;
    transient LinkedHashMapEntry<K,V> tail;
  
    //双向链表的迭代顺序，false 是按照插入顺序，true 是按照访问顺序
    final boolean accessOrder;
  
    // 将结点放到尾部
    private void linkNodeLast(LinkedHashMapEntry<K,V> p) {
        LinkedHashMapEntry<K,V> last = tail;
        tail = p;
        if (last == null)
            head = p;
        else {
            p.before = last;
            last.after = p;
        }
    }
  
    // 创建新结点的时候，将结点放到链表的尾部
    Node<K,V> newNode(int hash, K key, V value, Node<K,V> e) {
        LinkedHashMapEntry<K,V> p =
            new LinkedHashMapEntry<K,V>(hash, key, value, e);
        linkNodeLast(p);
        return p;
    }
  
    void afterNodeInsertion(boolean evict) { // possibly remove eldest
        LinkedHashMapEntry<K,V> first;
        if (evict && (first = head) != null && removeEldestEntry(first)) {
            K key = first.key;
            removeNode(hash(key), key, null, false, true);
        }
    }
  
    // 调用 get 方法访问一个结点后，如果 accessOrder = true，则会调用该方法将该结点放到尾部
    // LRU Cache 就是利用的 LinkedHashMap 这点
    void afterNodeAccess(Node<K,V> e) { // move node to last
        LinkedHashMapEntry<K,V> last;
        if (accessOrder && (last = tail) != e) {
            LinkedHashMapEntry<K,V> p =
                (LinkedHashMapEntry<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;
        }
    }
  
    /**
     * Constructs an empty insertion-ordered <tt>LinkedHashMap</tt> instance
     * with the default initial capacity (16) and load factor (0.75).
     */
    public LinkedHashMap() {
        super();
        accessOrder = false;
    }
  
    /**
     * 主要看下这个构造函数
     *
     * @param  initialCapacity 初始容量
     * @param  loadFactor      加载因子
     * @param  accessOrder     顺序 - true 则按照访问顺序，false 按照插入顺序
     */
    public LinkedHashMap(int initialCapacity,
                         float loadFactor,
                         boolean accessOrder) {
        super(initialCapacity, loadFactor);
        this.accessOrder = accessOrder;
    }
  
    public V get(Object key) {
        Node<K,V> e;
        if ((e = getNode(hash(key), key)) == null)
            return null;
        if (accessOrder) // 调用 get 方法后，会将该结点放到链表尾部
            afterNodeAccess(e);
        return e.value;
    }
  
    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) {
            int mc = modCount;
            // Android-changed: Detect changes to modCount early.
            for (LinkedHashMapEntry<K,V> e = head; (e != null && modCount == mc); e = e.after)
                action.accept(e.key);
        }
    }
  
    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);
        }
        public final void forEach(Consumer<? super V> action) {
            int mc = modCount;
            // Android-changed: Detect changes to modCount early.
            for (LinkedHashMapEntry<K,V> e = head; (e != null && modCount == mc); e = e.after)
                action.accept(e.value);
        }
    }
  
    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) {
            int mc = modCount;
            // Android-changed: Detect changes to modCount early.
            for (LinkedHashMapEntry<K,V> e = head; (e != null && mc == modCount); e = e.after)
                action.accept(e);
        }
    }
  
    // Map overrides
  
    public void forEach(BiConsumer<? super K, ? super V> action) {
        if (action == null)
            throw new NullPointerException();
        int mc = modCount;
        // Android-changed: Detect changes to modCount early.
        for (LinkedHashMapEntry<K,V> e = head; modCount == mc && e != null; e = e.after)
            action.accept(e.key, e.value);
        if (modCount != mc)
            throw new ConcurrentModificationException();
    }
  
    public void replaceAll(BiFunction<? super K, ? super V, ? extends V> function) {
        if (function == null)
            throw new NullPointerException();
        int mc = modCount;
        // Android-changed: Detect changes to modCount early.
        for (LinkedHashMapEntry<K,V> e = head; modCount == mc && e != null; e = e.after)
            e.value = function.apply(e.key, e.value);
        if (modCount != mc)
            throw new ConcurrentModificationException();
    }
  
    // Iterators
  
    abstract class LinkedHashIterator {
        LinkedHashMapEntry<K,V> next;
        LinkedHashMapEntry<K,V> current;
        int expectedModCount;
  
        LinkedHashIterator() {
            next = head;
            expectedModCount = modCount;
            current = null;
        }
  
        public final boolean hasNext() {
            return next != null;
        }
  
        final LinkedHashMapEntry<K,V> nextNode() {
            LinkedHashMapEntry<K,V> e = next;
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();
            if (e == null)
                throw new NoSuchElementException();
            current = e;
            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;
        }
    }
  
    final class LinkedKeyIterator extends LinkedHashIterator
        implements Iterator<K> {
        public final K next() { return nextNode().getKey(); }
    }
  
    final class LinkedValueIterator extends LinkedHashIterator
        implements Iterator<V> {
        public final V next() { return nextNode().value; }
    }
  
    final class LinkedEntryIterator extends LinkedHashIterator
        implements Iterator<Map.Entry<K,V>> {
        public final Map.Entry<K,V> next() { return nextNode(); }
    }
  }
  

• Previous
  进程保活
• Next
  HashMap