LinkedHashMap源码了解一下

前言

LinkedHashMap是面试中比较容易问到的集合之一。本篇文章主要通过分析LinkedHashMap的源码，更深入的了解LinkedHashMap，以及对比LinkedHashMap在JDK1.8和JDK1.7的不同。

本文基于jdk1.8

LinkedHashMap简介

LinkedHashMap类结构

可以从上图看出，LinkedHashMap继承HashMap，实现了Map接口。

LinkedHashMap特点

1. LinkedHashMap非线程安全，在多线程中保证线程安全的解决方法：使用Map map = Collections.synchronizedMap(new LinkedHashMap());。
2. LinkedHashMap底层是数组和双向链表组成的。
3. LinkedHashMap的key和value都允许为null。
4. LinkedHashMap的数据存储是有序的。
5. LinkedHashMap继承自HashMap，所以HashMap的特点，除了输出无序，其他LinkedHashMap都有。

LinkedHashMap提供的API

方法名	方法解释
clear()	从LinkedHashMap中移除所有映射。
containsValue(Object value)	LinkedHashMap中匹配到指定值，则返回true。
entrySet()	返回LinkedHashMap中包含的映射的Set。
forEach(BiConsumer<? super K, ? super V> action)	将给定操作（BiConsumer）应用于LinkedHashMap的每一个元素，直到处理完所有数据或操作抛出异常为止。
get(Object key)	返回指定key映射到的值;如果LinkedHashMap中不包含key的映射，则返回null。
getOrDefault(Object key, V defaultValue)	返回指定key映射到的值;如果LinkedHashMap中不包含key的映射，则返回defaultValue。
keySet()	返回LinkedHashMap中包含的key的Set。
removeEldestEntry(Map.Entry<K,V> eldest)	是否移除LinkedHashMap中最年长的节点。
replaceAll(BiFunction<? super K, ? super V, ? extends V> function)	对LinkedHashMap调用给定函数的结果替换每个数据的value，直到处理完所有数据或者该函数抛出异常。
values()	返回LinkedHashMap中包含的value的集合。

LinkedHashMap源码

LinkedHashMap成员变量

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

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

/**
 * 迭代时输出的顺序是插入节点的顺序。默认为false，若为true，则输出的顺序是按照访问节点的顺序
 */
final boolean accessOrder;

LinkedHashMap内部类

Entry

/**
 * 继承自HashMap的Node，添加了两个Entry，实现了双向链表
 */
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构造函数

LinkedHashMap有5个构造方法，与HashMap的很相似，就是多了一个accessOrder控制输出顺序。

public LinkedHashMap() {
    // 调用HashMap的无参构造函数，加载因子为默认值
    super();
    // 迭代时输出的顺序是插入节点的顺序
    accessOrder = false;
}

public LinkedHashMap(int initialCapacity) {
    // 调用HashMap的构造函数，指定初始容量
    super(initialCapacity);
    // 迭代时输出的顺序是插入节点的顺序
    accessOrder = false;
}

public LinkedHashMap(int initialCapacity, float loadFactor) {
    // 调用HashMap的构造函数，指定初始容量和加载因子
    super(initialCapacity, loadFactor);
    // 迭代时输出的顺序是插入节点的顺序
    accessOrder = false;
}

public LinkedHashMap(Map<? extends K, ? extends V> m) {
    // 调用HashMap的无参构造函数，加载因子为默认值
    super();
    // 迭代时输出的顺序是插入节点的顺序
    accessOrder = false;
    putMapEntries(m, false);
}

###LinkedHashMap重要方法解析

put(K key, V value)

LinkedHashMap没有重写HashMap的put方法，但是重写了newNode方法，HashMap的putVal方法会调用newNode方法。我们一起看一下：

HashMap#newNode：

Node<K,V> newNode(int hash, K key, V value, Node<K,V> next) {
    return new Node<>(hash, key, value, next);
}

LinkedHashMap#newNode：

Node<K,V> newNode(int hash, K key, V value, Node<K,V> e) {
    // 构建的节点是Entry，而不是Node
    LinkedHashMap.Entry<K,V> p =
        new LinkedHashMap.Entry<K,V>(hash, key, value, e);
    // 将新增的节点，连接在链表的尾部
    linkNodeLast(p);
    return p;
}

linkNodeLast：

private void linkNodeLast(LinkedHashMap.Entry<K,V> p) {
    // 记录原来的尾节点
    LinkedHashMap.Entry<K,V> last = tail;
    // 将新的节点设置为尾节点
    tail = p;
    // 如果原来的尾节点为null，就设置新的节点同样为头节点
    if (last == null)
        head = p;
    // 如果原来的尾节点不为null，将新的尾节点的上一个节点设置为原来的尾节点，将原来的尾节点的下一个节点设置为新的尾节点
    else {
        p.before = last;
        last.after = p;
    }
}

HashMap预留给LinkedHashMap的方法

afterNodeAccess(Node<K,V> e)：

// 将节点移到最后
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;
    }
}

afterNodeInsertion：

// 回调函数，新节点插入之后回调，根据evict和判断是否需要删除最老插入的节点
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);
    }
}

get(Object key)

public V get(Object key) {
    Node<K,V> e;
    // 调用HashMap的getNode方法获取节点，如果该节点为null的话返回null
    if ((e = getNode(hash(key), key)) == null)
        return null;
    // 如果输出的顺序是按照访问节点的顺序，就将最近访问的节点移动到链表的最后面
    if (accessOrder)
        afterNodeAccess(e);
    // 返回节点的值
    return e.value;
}

getOrDefault(Object key, V defaultValue)

public V getOrDefault(Object key, V defaultValue) {
    Node<K,V> e;
    // 调用HashMap的getNode方法获取节点，如果该节点为null的话返回defaultValue
    if ((e = getNode(hash(key), key)) == null)
        return defaultValue;
    // 如果输出的顺序是按照访问节点的顺序，就将最近访问的节点移动到链表的最后面
    if (accessOrder)
        afterNodeAccess(e);
    // 返回节点的值
    return e.value;
}

remove(Object key)

LinkedHashMap也没有重写HashMap的remove方法。

HashMap预留给LinkedHashMap的方法

afterNodeRemoval：

// 删除节点的同时，将节点从双向链表中删除
void afterNodeRemoval(Node<K,V> e) { // unlink
    LinkedHashMap.Entry<K,V> p =
        (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
    // 设置删除节点的前后节点都为null
    p.before = p.after = null;
    // 如果前一个节点为null，就将后一个节点设置为头节点
    if (b == null)
        head = a;
    // 如果前一个节点不为null，就将后一个节点设置为前一个节点的下一个节点
    else
        b.after = a;
    // 如果后一个节点为null，就将前一个节点设置为尾节点
    if (a == null)
        tail = b;
    // 如果后一个节点不为null，就将前一个节点设置为后一个基点的上一个节点
    else
        a.before = b;
}

entrySet()

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

• LinkedEntrySet

  final class LinkedEntrySet extends AbstractSet<Map.Entry<K,V>> {
      // 省略部分方法
      public final Iterator<Map.Entry<K,V>> iterator() {
          return new LinkedEntryIterator();
      }
  }

• LinkedEntryIterator

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

• LinkedHashIterator

  abstract class LinkedHashIterator {
      // 下一个节点
      LinkedHashMap.Entry<K,V> next;
      // 当前节点
      LinkedHashMap.Entry<K,V> current;
      // 预期的操作次数
      int expectedModCount;
  
      LinkedHashIterator() {
          // 初始化时，next为LinkedHashMap内部维护的双向链表的表头
          next = head;
          // 记录当前modCount，以满足fail-fast
          expectedModCount = modCount;
          // 当前节点为null
          current = null;
      }
  
      // 判断是否还有下一个
      public final boolean hasNext() {
          // 就是判断下一个是否为null
          return next != null;
      }
  
      // 可以看出，迭代LinkedHashMap是从内部维护的双链表的表头开始循环输出
      // 初始LinkedHashMap的容量对遍历没有影响
      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 = 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;
      }
  }

总结

LinkedHashMap相对于HashMap的源码比起来简单很多，只是重写了部分方法。不过由于其内部维护了一个双向链表，所以在数据结构上比HashMap要复杂一点。

欢迎关注博主其他的文章。