LinkedHashMap

LinkedHashMap使一个集合类，继承了HashMap，并且在HashMap的基础上维护了一条双向链表，使其具有如下特性：

• 支持遍历时会按照插入顺序有序的进行迭代
• 支持按照元素访问顺序排序，适用于封装LRU缓存策略的工具（继承LinkedHashMap实现简单的LRU算法 | Feliks）
• 因为内部使用双向链表维护各个节点，所以遍历时的效率和元素个数成正比，相较于和容量成正比的HashMap来说，迭代效率会高很多

LinkedHashMap是在HashMap的基础上在各个节点之间维护一条双向链表，使得原本散列在数组不同位置上的节点、链表、红黑树关联起来

代码演示

插入顺序遍历

public static void main(String[] args) {
    HashMap<String, String> map = new LinkedHashMap<>();
    map.put("a", "1");
    map.put("b", "2");
    map.put("c", "3");
    map.put("d", "4");
    map.put("e", "5");
    for (Map.Entry<String, String> entry : map.entrySet()) {
        System.out.println(entry.getKey() + " : " + entry.getValue());
    }
}

输出

LinkedHashMap的迭代顺序和插入顺序都是一致的，这是HashMap不具备的

访问顺序遍历

LinkedHashMap定义了排序模式accessOrder

boolean类型，默认为false（访问顺序则为true，插入顺序则为false）

在使用LinkedHashMap构造器的时候可以传入accessOrder属性，将其设置为true，代表其具备访问有序性

public static void main(String[] args) {
    HashMap<Integer, String> map = new LinkedHashMap<>(16, 0.75f, true);
    map.put(1, "one");
    map.put(2, "two");
    map.put(3, "three");
    map.put(4, "four");
    map.put(5, "five");
    // 访问元素，该元素会被移动至链表末端
    map.get(2);
    map.get(3);
    for (Map.Entry<Integer, String> entry : map.entrySet()) {
        System.out.println(entry.getKey() + " : " + entry.getValue());
    }
}

输出

可见，LinkedHashMap的迭代顺序和访问顺序是一致的

LRU缓存

继承LinkedHashMap实现简单的LRU算法 | Feliks

• 继承LinkedeHashMap

• 构造器中指定accessOrder为true，在这样访问元素，该元素会被移动至链表末端，链表首元素就是最近最少被访问的元素

  

• 重写removeEldestEntry方法，该方法会返回一个boolean指，告知LinkedHashMap是否需要移除链表首元素（因为缓存空间是有限的）

  

测试代码是重写了LinkedHashMap中的removeEldestEntry方法实现的本地缓存

import com.feliks.core.MyCache;
import com.feliks.core.MyCacheBs;

import java.util.HashMap;

public class testMyCache {
    public static void main(String[] args) {
        MyCache cache = MyCacheBs
                .newBuilder()
                .setSize(3)
                .setLock(testMyCache.class)
                .build();

        cache.putValue("1", "test1");
        cache.putValue("2", "test2");
        cache.putValue("3", "test3");
        System.out.println(cache);

        cache.putValue("1", "test1");
        System.out.println(cache.getValue("1"));
        System.out.println(cache);

        cache.putValue("3", "test3");
        System.out.println(cache.getValue("3"));
        System.out.println(cache);

        cache.putValue("4", "test4");
        System.out.println(cache.getValue("4"));
        System.out.println(cache);
    }
}

LinkedHashMap源码

Node

HashMap的数组上的因为冲突转为链表的节点会在符合以下两个条件时会将链表转为红黑树

1. 链表长度>=阈值（TREEIFY_THRESHOLD）-1时
2. 数组的长度达到最小树化容量（MIN_TREEIFY_CAPACITY）时

LinkedHashMap是在HashMap数组的基础上为每一个节点建立一条双向链表（可以在LinkedHashMap的源码中看到前驱和后继节点：Entry<K, V> before, after），但是这样的话就使得红黑树的树节点也需要具备双向链表节点的特性，即每个树节点都需要拥有两个引用存储前驱节点和后继节点的地址。

1. LinkedHashMap的节点内部类Entry基于HashMap的基础上增加了before和after指针使节点具备双向链表的特性

   

2. HashMap的红黑树节点TreeNode继承了具备双向链表特性的LinkedHashMap的Entry

   

为什么HashMap的TreeNode要通过LinkedHashMap获取双向链表的特性？

因为LinkedHashMap是在HashMap基础上对节点增加双向指针实现双向链表的特性，所以LinkedHashMap内部链表转为红黑树时，对应的节点会转为TreeNode，为了保证使用LinkedHashMap时的树节点具备双向链表的特性，所以树节点TreeNode需要继承LinkedHashMap的Entry

为什么不直接在Node上实现前驱和后继指针？

因为如果这么做的话会在使用HashMap的时候让节点携带多了两个没有必要的引用，占用没必要的内存空间。

对于在使用HashMap的TreeNode时，作者认为在良好的hashCode算法下，HashMap转为红黑树的概率并不大，就算转为红黑树变成树节点，也可能会因为移除或者扩容将TreeNode变成Node，所以TreeNode使用的概率并不算很大，对于这一点资源空间的浪费是可以接受的

构造器

LinkedHashMap有四个构造器，直接调用父类（HashMap）的构造器来完成初始化

/**
 * Constructs an empty insertion-ordered {@code LinkedHashMap} instance
 * with the default initial capacity (16) and load factor (0.75).
 */
public LinkedHashMap() {
    super();
    accessOrder = false;
}

/**
 * Constructs an empty insertion-ordered {@code LinkedHashMap} instance
 * with the specified initial capacity and a default load factor (0.75).
 *
 * @param  initialCapacity the initial capacity
 * @throws IllegalArgumentException if the initial capacity is negative
 */
public LinkedHashMap(int initialCapacity) {
    super(initialCapacity);
    accessOrder = false;
}

/**
 * Constructs an insertion-ordered {@code LinkedHashMap} instance with
 * the same mappings as the specified map.  The {@code LinkedHashMap}
 * instance is created with a default load factor (0.75) and an initial
 * capacity sufficient to hold the mappings in the specified map.
 *
 * @param  m the map whose mappings are to be placed in this map
 * @throws NullPointerException if the specified map is null
 */
public LinkedHashMap(Map<? extends K, ? extends V> m) {
    super();
    accessOrder = false;
    putMapEntries(m, false);
}

/**
 * Constructs an empty {@code LinkedHashMap} 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 - {@code true} for
 *         access-order, {@code false} 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;
}

accseeOrder就是上面提到的默认为false，当其指定为true时，访问元素，该元素会被移动至链表末端，链表首元素就是最近最少被访问的元素

get方法

/**
 * Returns the value to which the specified key is mapped,
 * or {@code null} if this map contains no mapping for the key.
 *
 * <p>More formally, if this map contains a mapping from a key
 * {@code k} to a value {@code v} such that {@code (key==null ? k==null :
 * key.equals(k))}, then this method returns {@code v}; otherwise
 * it returns {@code null}.  (There can be at most one such mapping.)
 *
 * <p>A return value of {@code null} does not <i>necessarily</i>
 * indicate that the map contains no mapping for the key; it's also
 * possible that the map explicitly maps the key to {@code null}.
 * The {@link #containsKey containsKey} operation may be used to
 * distinguish these two cases.
 */
public V get(Object key) {
    Node<K,V> e;
    if ((e = getNode(key)) == null)
        return null;
    if (accessOrder)
        afterNodeAccess(e);
    return e.value;
}

get方法是LinkedHashMap增删改查中唯一重写过的方法，因为要考虑accessOrder是否为true的情况，如果为true则会在查询完元素后将当前访问的元素移动到链表的末尾

执行步骤：

1. 调用父类（HashMap）的getNode方法获取键值对，如果为空则直接返回

2. 判断accessOrder是否为true，为true则说明需要保证LinkedHashMap的链表访问有序执行

3. 调用LinkedHashMap重写的afterNodeAccess方法

   void afterNodeAccess(Node<K,V> e) { // move node to last
       LinkedHashMap.Entry<K,V> last;
       // 如果accessOrder为true且当前节点不在链表的表尾
       if (accessOrder && (last = tail) != e) {
           // 获取当前节点及其前驱和后继节点
           LinkedHashMap.Entry<K,V> p = (LinkedHashMap.Entry<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指向前驱节点，
               last = b;
           // 如果last为空，则说明当前链表只有一个节点p，则让head指向p
           if (last == null)
               head = p;
           else {
               // 反之让p的前驱节点指向尾节点，再让尾节点的前驱节点指向p
               p.before = last;
               last.after = p;
           }
           // tail指向p，自此将节点p移动到链表末尾
           tail = p;
           ++modCount;
       }
   }

   1. 如果accessOrder为true且链表尾节点不是当前节点p，需要将当前节点移动到链表尾部
   2. 获取当前节点p以及其前驱节点b和后继节点a
   3. 将当前节点p的后继节点指向null，使其和后继节点p断开联系
   4. 尝试将前驱节点指向后继节点，若前驱节点为空，则说明当前节点p就是整个链表的首元结点，直接将后继节点a设置为首元结点，然后再将p添加到a的末尾
   5. 尝试让后继节点a指向前驱节点b
   6. 此时已经让前驱和后继节点完成关联，节点p被独立出来，再将节点p添加到链表的末端，如果链表末端为空则说明当前链表只有一个节点p，直接让head指向p即可
   7. 此时节点p已经在链表的末端，让链表的尾指针指向p即可

   

remove方法

LinkedHashMap的remove方法并没有重写，而是直接调用了父类的removeNode方法

// LinkedHashMap中
public final boolean remove(Object key) {
    return removeNode(hash(key), key, null, false, true) != null;
}

// HashMap中
final Node<K,V> removeNode(int hash, Object key, Object value,
                           boolean matchValue, boolean movable) {
    Node<K,V>[] tab; Node<K,V> p; int n, index;
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (p = tab[index = (n - 1) & hash]) != null) {
        Node<K,V> node = null, e; K k; V v;
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            node = p;
        else if ((e = p.next) != null) {
            if (p instanceof TreeNode)
                node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
            else {
                do {
                    if (e.hash == hash &&
                        ((k = e.key) == key ||
                         (key != null && key.equals(k)))) {
                        node = e;
                        break;
                    }
                    p = e;
                } while ((e = e.next) != null);
            }
        }
        if (node != null && (!matchValue || (v = node.value) == value ||
                             (value != null && value.equals(v)))) {
            if (node instanceof TreeNode)
                ((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
            else if (node == p)
                tab[index] = node.next;
            else
                p.next = node.next;
            ++modCount;
            --size;
            afterNodeRemoval(node);
            return node;
        }
    }
    return null;
}

且为了保证键值对移除后双向链表中的节点也会同步被移除，LinkedHashMap重写了HashMap的空实现方法afterNodeRemoval

// HashMap中的空实现
void afterNodeRemoval(Node<K,V> p) { }

// LinkedHashMap对该方法重写
void afterNodeRemoval(Node<K,V> e) { // unlink
    // 获取当前节点p及其前驱节点b和后继节点a
    LinkedHashMap.Entry<K,V> p = (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
    // 将p的前驱和后继指针都置为null，是其前驱后继节点断开连接
    p.before = p.after = null;
    // 如果前驱节点为空则说明当前p节点是链表的首元结点，让head指向后继节点a即可
    if (b == null)
        head = a;
    // 如果前驱节点b不为空则让b指向后继节点a
    else
        b.after = a;
    // 如果后继节点为空，则说明当前节点p的位置在链表的末尾，直接让tail尾指针指向前驱节点b即可
    if (a == null)
        tail = b;
    // 后继节点不为空则让后继节点的前驱指针指向前驱节点
    else
        a.before = b;
}

将p节点的前驱和后继都指向null为了等待gc进行回收

put方法

LinkedHashMap并没有实现插入方法，而是直接继承HashMap中的所有插入方法

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
               boolean evict) {
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    else {
        Node<K,V> e; K k;
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;
        else if (p instanceof TreeNode)
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        else {
            for (int binCount = 0; ; ++binCount) {
                if ((e = p.next) == null) {
                    p.next = newNode(hash, key, value, null);
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        treeifyBin(tab, hash);
                    break;
                }
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                p = e;
            }
        }
        if (e != null) { // existing mapping for key
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e);
            return oldValue;
        }
    }
    ++modCount;
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict);
    return null;
}

在HashMap的putVal方法中，有两个方法：afterNodeAccess和afterNodeInsertion，这两个方法在HashMap中都是空实现

void afterNodeAccess(Node<K,V> p) { }
void afterNodeInsertion(boolean evict) { }

而在LinkedHashMap中重写了这两个方法

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);
    }
}

void afterNodeAccess(Node<K,V> e) { // move node to last
    LinkedHashMap.Entry<K,V> last;
    if (accessOrder && (last = tail) != e) {
        LinkedHashMap.Entry<K,V> p =
            (LinkedHashMap.Entry<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;
    }
}

• afterNodeAccess方法，如果当前悲插入的ke已存在于map中，因为linkedHashMap的插入操作会将新节点追加到链表末尾，所以对于存在的key则调用afterNodeAccess将其放到链表末尾
• afterNodeInsertion方法，当removeEldestEntry返回true时，会将链表首元结点移除

来看看afterNodeInsertion的工作流程，假如我们重写了removeEldestEntry，当链表size大于capacity时就返回true，就会告知LinkedHashMap移除最老的缓存项（链表第一个元素）

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

LinkedHashMap和HashMap遍历性能比较

LinkedHashMap中维护了一个双向链表来记录数据插入的顺序，因此在迭代遍历生成的迭代器的时候，是按照双向链表的路径进行遍历的，这一点相比HashMap遍历整个bucket方式来说高效很多

HashMap的迭代器，nextNode方法会返回next指向的下一个元素，并且会从next开始遍历bucket找到下一个table中不为空的元素

final class EntryIterator extends HashIterator
    implements Iterator<Map.Entry<K,V>> {
    public final Map.Entry<K,V> next() { return nextNode(); }
}

final Node<K,V> nextNode() {
    Node<K,V>[] t;
    Node<K,V> e = next;
    if (modCount != expectedModCount)
        throw new ConcurrentModificationException();
    if (e == null)
        throw new NoSuchElementException();
    if ((next = (current = e).next) == null && (t = table) != null) {
        do {} while (index < t.length && (next = t[index++]) == null);
    }
    return e;
}

LinkedHashMap的迭代器，直接使用通过after指针快速定位到当前节点的后继节点

final class LinkedEntryIterator extends LinkedHashIterator
    implements Iterator<Map.Entry<K,V>> {
    public final Map.Entry<K,V> next() { return nextNode(); }
}

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直接指向当前节点的after指针快速定位到下一个节点
        next = e.after;
        return e;
    }

什么是LinkedHashMap？

LinkedHashMap是Java集合框架中HashMap的一个子类，它继承了HashMap的所有属性和方法，并且在HashMap的基础上重写了afterNodeRemoval、afterNodeInsertion、afterNodeAccess方法，使其拥有顺序插入和访问有序的特性

LinkedHashMap如何按照插入顺序迭代元素？

LinkedHashMap按照插入顺序迭代元素是其默认的行为，因为其内部维护了一个双向链表用于记录元素的插入顺序，因此当我们使用其内部的迭代器迭代元素时，元素的顺序与他们最初插入的顺序相同

LinkedHashMap如何按照访问顺序迭代元素？

LinkedHashMap可以通过构造器中的accessOrder参数指定访问顺序迭代元素，当其为true时，每次访问一个元素该元素就会移动到链表的末端，因此下次访问该元素的时候，它就会成为链表中的最后一个元素，从而实现按照访问顺序迭代元素

LinkedHashMap与HashMap有什么区别？

LinkedHashMap与HashMap都是Java集合框架中的Map接口的实现类，他们最大的区别在于迭代元素的顺序，HashMap迭代元素的顺序是不确定的，而LinkedHashMap提供了按照顺序或访问顺序迭代元素的功能，此外LinkedHashMap内部维护了一个双向链表，用于记录元素的插入插入顺序或访问顺序，而HashMap则没有这个链表，因此LinkedHashMap的插入性能可能会比HashMap略低，但LinkedHashMap提供了更多的功能并且迭代效率相较于HashMap更加高效