Java基础_LinkedHashMap源码分析

本文主要从如下几点学习LinkedHashMap

• LinkedHashMap是啥
• 代码实操
• 原理分析
• 图的形式展示双向列表

LinkedHashMap是啥

• 继承 HashMap实现了Map接口的散列表，HashMap本身是数组加单向链表

• 数据结构：HashMap+双向链表；HashMap的数据结构是（数组+单向链表+（红黑树））

• 是根据插入或者访问顺序实现有序输出的HashMap，线程不安全的，允许key为null，value为null

代码实操

• put 、get、forEach

   LinkedHashMap<Integer, String> linkedMap = new LinkedHashMap<>();
          linkedMap.put(1, "index1");
          linkedMap.put(3, "index3");
          linkedMap.put(5, "index5");
          linkedMap.put(4, "index4");
  
          System.out.println("key == 3" + linkedMap.get(3));
  
          linkedMap.forEach((k, v) -> {
              System.out.println("k == " + k + ", v == " + v);
          });
  // 运行结果
  key == 3 index3
  k == 1, v == index1
  k == 3, v == index3
  k == 5, v == index5
  k == 4, v == index4
    
     // 构造函数 打开按访问顺序排列
     LinkedHashMap<Integer, String> linkedMap = new LinkedHashMap<>(5,0.75f,true);
     linkedMap.put(1, "index1");
     linkedMap.put(3, "index3");
     linkedMap.put(5, "index5");
     linkedMap.put(4, "index4");
     System.out.println("key == 3" + linkedMap.get(3));
  
      linkedMap.forEach((k, v) -> {
         System.out.println("k == " + k + ", v == " + v);
      });
  
  // 运行结果为
  key == 3 index3
  k == 1, v == index1
  k == 5, v == index5
  k == 4, v == index4
  k == 3, v == index3
  

原理分析

几个全局变量的解释

transient LinkedHashMapEntry<K,V> head;

• 是双向列表的头节点，指向双向列表的头节点。

transient LinkedHashMapEntry<K,V> tail;

• 是双向列表的尾节点，指向双向列表的尾节点。

final boolean accessOrder;

• accessOrder默认在LinkedHashMap的构造函数中赋值为false
• 如果为false，那么在迭代输出节点的时候，会按照插入的顺序进行输出
• 如果为true（使用了这个 new LinkedHashMap<>(5,0.75f,true) 构造函数创建LinkedHashMap），在迭代的时候，会按照节点的访问顺序输出节点，最近使用的放在双向列表的尾部。
• 为true的话，可以符合LRU算法的特性。

LinkedHashMapEntry的介绍

• 继承至HashMap.Node，具有了单向链表的功能。

• 比HashMap的Node多了 befor和after这两个变量，这两个变量是用来维护LinkedHashMap的双向列表。

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

LinkedHashMap的构造函数介绍

• 构造函数如下

  //常规用法
  public LinkedHashMap() {
          super();
          accessOrder = false;
      }
      
   //指定了初始化时数组的容量   
  public LinkedHashMap(int initialCapacity) {
          super(initialCapacity);
          accessOrder = false;
      }
   //指定了初始化时容量和加载因子   
  public LinkedHashMap(int initialCapacity, float loadFactor) {
          super(initialCapacity, loadFactor);
          accessOrder = false;
      }
      
  //指定了容量、加载因子和迭代输出时的顺序
  public LinkedHashMap(int initialCapacity,
                           float loadFactor,
                           boolean accessOrder) {
          super(initialCapacity, loadFactor);
          this.accessOrder = accessOrder;
      }
  // 采用一个Map来构造
   public LinkedHashMap(Map<? extends K, ? extends V> m) {
          super();
          accessOrder = false;
                //批量插入
          putMapEntries(m, false);
      }
  

putI()方法的源码的分析

LinkedHashMap中没有重写put方法，但是在HashMap进行put操作的时候，有如下两点判断

• 当key计算出来的位置，没有数据存在，会调用newNode()方法。
  • 该方法，在LinkedHashMap被重写了
  • 当LinkedHashMap调用put时，此时用到了多态，会调用LinkedHashMap中的newNode()方法
• 当key计算出来的位置，有数据存在；
  • 当key完全相同，进行数据的赋值，然后进行数据的替换。
    • 在数据进行替换的时候，调用了afterNodeAccess(e)方法
    • 该方法在LinkedHashMap有进行重写。
  • 当key所在的位置的数据结构时红黑树，调用了putTreeVal()方法，插入节点
  • 当key所在位置是一个单向链表；
    • 会在内部循环，如果key当前所在位置时存在数据的，那么就会判断p.next是否为null
    • 为null，就会调用newNode()创建一个新的节点插入进去。

还有一个方法，afterNodeInsertion(evict)

• 该方法在LinkedHashMap也进行了重写
• evict默认时true

newNode()方法内部调用了linkNodeLast(p);方法。

• 代码分析如下

  Node<K,V> newNode(int hash, K key, V value, Node<K,V> e) {
          //构造带双向链表属性的LinkedHashMapEntry的对象
          LinkedHashMapEntry<K,V> p =
              new LinkedHashMapEntry<K,V>(hash, key, value, e);
          //双向列表的维护
          linkNodeLast(p);
          return p;
      }
  
  private void linkNodeLast(LinkedHashMapEntry<K,V> p) {
          //首先获取当前链表的最后一个元素
          LinkedHashMapEntry<K,V> last = tail;
          //当前插入的元素定义为最后一个元素
          tail = p;
          //如果之前的最后一个元素是null，说明之前的链表就是空的，所以当前的元素是第一个元素
          if (last == null)
              head = p;
          else {
              //如果之前的链表不是null
              //put前的最后一个元素，设置为当前put元素的前一个
              p.before = last;
              //当前put元素设置为put前最后一个元素的下一个。
              last.after = p;
            //这样就形成了一个双向列表
          }
      }
  

afterNodeAccess(e)方法分析

• 代码分析如下

  // 会将当前访问dao的字点e，移动到双向链表的尾部
  void afterNodeAccess(Node<K,V> e) { // move node to last
      LinkedHashMapEntry<K,V> last;
      //当accessOrder为true，并且链表的尾部节点和 要替换的数据（旧数据）不相等
      if (accessOrder && (last = tail) != e) {
          LinkedHashMapEntry<K,V> p =
              (LinkedHashMapEntry<K,V>)e, 
            //将旧数据中前一个节点的before变量赋给b
          b = p.before, 
            //将旧数据中后一个节点的after变量赋给a
          a = p.after;
            //
          p.after = null;
            // 当b为null，说明p的前置节点为null，p之前时头节点
          if (b == null)
            //p的后置节点设置为链表头部
              head = a;
          else
                //不为null ，将p的后置节点a更新为 p的前置节点的后置节点
              b.after = a;
        
          if (a != null)
                //当 a不为null，将p的前置节点更新为p的后置节点
              a.before = b;
          else
            //如果原本p的后置节点为null，说明p就是链表的尾部节点，那么将p的前置节点数据b设置为链表的尾部数据
              last = b;
        // 当链表尾部为null，就将当前的p设置链表的头部数据
        // 可以这么理解，当现在的key与原有的key发生了hash碰撞，但是原有的key对应的value时null
          if (last == null)
              head = p;
          else {
            //更新当前节点p的前置节点为原尾节点last，last的后置节点为p
              p.before = last;
              last.after = p;
          }
        //尾节点的引用赋值为p
          tail = p;
            //改变modCount
          ++modCount;
      }
  }
  

afterNodeInsertion方法分析

• 代码分析如下

  void afterNodeInsertion(boolean evict) { // possibly remove eldest
          LinkedHashMapEntry<K,V> first;
          // removeEldestEntry 默认是返回false的 所以if内的代码不会去执行
          if (evict && (first = head) != null && removeEldestEntry(first)) {
              K key = first.key;
              //移除链表头部的元素
              removeNode(hash(key), key, null, false, true);
          }
      }
  

get()方法的源码分析

LinkedHashMap重写了HashMap的get方法

• 代码如下

  public V get(Object key) {
          Node<K,V> e;
                //首先根据key的hashCode值查找当前为对应的节点，如果不存就返回null
          if ((e = getNode(hash(key), key)) == null)
              return null;
                //当accessOrder为true的时候，将当前查到的节点e，移动到链表的尾部
          if (accessOrder)
              afterNodeAccess(e);
                //返回查询到节点的中的value
          return e.value;
      }
  

LinkedHashMap的删除操作

LinkedHashMap没有重写remove方法，

我们知道remove方法内部调用了removeNode()方法，removeNode方法内部调用了afterNodeRemoval()

LinkedHashMap内对afterNodeRemoval()方法进行重写

• 代码如下

  //删除节点e的时候，将节点e在双向列表上的前置和后置的节点引用都置空，然后更新前后节点（这里的前后节点对应e的前后节点）的指向。
  void afterNodeRemoval(Node<K,V> e) { // unlink
          LinkedHashMapEntry<K,V> p =
              (LinkedHashMapEntry<K,V>)e;
          b = p.before;
          a = p.after;
                //将待删除节点P的前置和后置节点都置空
          p.before = p.after = null;
                //如果前置节点null，那么将后置节点设置为头部节点
          if (b == null)
              head = a;
          else
            // 前置节点的后置节点 更新为 当前p的后置节点所指向的节点
              b.after = a;
                //当后置节点为null，将前置节点设置为尾部节点
          if (a == null)
              tail = b;
          else
            //将后置节点 与 前置节点的后置节点进行关联
              a.before = b;
      }
  

LinkedHashMap的containsValue()

• 代码如下

  public boolean containsValue(Object value) {
                //从头部节点开始，利用双向列表的特点，每次拿到节点的后置节点 进行循环判断
                //匹配到就返回true，匹配不到就返回false
          for (LinkedHashMapEntry<K,V> e = head; e != null; e = e.after) {
              V v = e.value;
              if (v == value || (value != null && value.equals(v)))
                  return true;
          }
          return false;
      }
  

相比较于HashMap

• 代码如下

  //HashMap采用了嵌套for循环，效率不太行呀
  public boolean containsValue(Object value) {
          Node<K,V>[] tab; V v;
          if ((tab = table) != null && size > 0) {
              for (int i = 0; i < tab.length; ++i) {
                  for (Node<K,V> e = tab[i]; e != null; e = e.next) {
                      if ((v = e.value) == value ||
                          (value != null && value.equals(v)))
                          return true;
                  }
              }
          }
          return false;
      }
  

图的形式展示双向列表

上面讲的又是节点，又是前置节点，又是后置节点

然后什么accessOrder == true的时候，又要移动节点，又要更新前置和后置的引用

下面就以一张图表示一下。

LinkedHashMap_put_get_操作示意图.png