文章目录

• 前言
• 一、进入JDK中的源码（InteliJ IDEA为例）
• 二、HashMap的结构
• 三、源码解读
• • 3.1 属性解读
  • 3.2 put方法解读
  • • 3.2.1 HashMap中的hash方法
    • 3.2.2 HashMap中的putVal方法
    • 未完待续

      ---

      前言

      上一篇博主写了一些关于HashMap的前置知识，简单易懂：

      HashMap源码解读（上篇）

      下面将深入HashMap源码，进行解读。

      看源码不是盲目看书，要有的放矢，带着疑问去看。

      本文章将围绕这几个疑问展开：

      1. HashMap的哈希函数是如何设计的？
      2. put方法的逻辑是什么？到底是如何存储元素的？
      3. 当发生冲突时，是如何解决的？
      4. 哈希表冲突比较严重时，如何扩容resize？

      ---

      一、进入JDK中的源码（InteliJ IDEA为例）

      有两种快捷方式：

      1. 双击shift，输入HashMap类名即可。

      2. 直接在使用的类上，ctrl+鼠标左键点进去即可

      二、HashMap的结构

      JDK8之后HashMap的结构图如下：（可先看下面再回来看这个结构图）

      

      JDK8之前的HashMap就是数组+链表，JDK8之后采用数组+链表+红黑树

      冲突严重的链表会被“树化”，将链表转为红黑树，提高冲突严重的链表的查询效率。

      三、源码解读

      3.1 属性解读

      如图所示：

      

      图中有六条属性，下面逐一解释：

      1. static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

      默认初始化的数组大小 (默认的哈希桶数量) ： 16

      注：哈希桶就是哈希表中一个个的数组元素，不包括链表元素

      2.static final int MAXIMUM_CAPACITY = 1 << 30;

      最大的数组容量： 2 30 2^{30} 230

      3.static final float DEFAULT_LOAD_FACTOR = 0.75f;

      默认负载因子，默认时开始保存的元素个数最多为 16 * loadFactor = 12 个

      4.static final int TREEIFY_THRESHOLD = 8;

      树化阈值。某个哈希桶中的链表长度超过8才会触发“树化”操作

      5.static final int UNTREEIFY_THRESHOLD = 6;

      “解树化” 当某个哈希桶中的红黑树结点个数过小，< = 6时，就会将红黑树还原为链表。

      6.static final int MIN_TREEIFY_CAPACITY = 64;

      树化有两个条件：

      1. 此时哈希表的哈希桶个数 >= 64
      2. 单个链表的结点个数 >= 8

      若某个链表长度 >= 8 ,但此时哈希桶的数量不足64，则只是简单的哈希表扩容而已。

      3.2 put方法解读

      如图所示：

      

      内部存储调用的是putVal方法，方法里面参数主要是hash值和key，value值。

      3.2.1 HashMap中的hash方法

      源码如下：

      

      1.首先判断传入的Key值是否为null？ 如果为null，直接放入数组索引为0的哈希桶中。

      2.如果传入的Key值不为null，则将key的hashCode 无符号右移16位，保留高16位 然后和 原hashCode作 异或运算，求得数组索引。

      注意：Key对象所在类的hashCode方法若没有覆写，则默认调用Object提供的hashCode方法。

      

      • 高低16位都参与哈希函数的运算，尽可能保证不同key映射到比较均衡的状态。
      • 原32位的hashCode和只保留高16的数字做异或运算
      • 高低位树都参与hash运算得到的值更加平均
      • 哈希函数设计理念：经过hash运算得到的值尽可能地平均

        此时求出地hash值还不是当前数组的索引，只是经过hash运算得到的一个比较均衡的值,hash值还要经过如下红框的位运算，得到数组索引值：

        

        上一步得到的key的hash值和当前哈希表的长度-1 进行 & 运算就可以得到索引值。（位运算的效率是最高的）

        • 相当于hash % 数组长度取模(n)
        • 前提是n必须为 2^n （初始化的哈希桶数量必须为2 ^ n）。
        • 将任意的正整数转为哈希桶数量之内的小整数 => i 就是当前key求的哈希桶的编号

          3.2.2 HashMap中的putVal方法

          JDK中源码如下

          final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                             boolean evict) {
                  Node[] tab; Node 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 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)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;
              }
          

          代码解读：

          1.首先判断当前哈希表是否为空，若为空，进行默认初始化操作（resize()函数里面包括了扩容、数据搬移和初始化操作）

          

          2.tab[i] = 这个哈希桶的头结点元素，当这个键值对计算出的哈希桶链表为空，直接将当前新元素放入链表的头部。

          

          3. 此时哈希表不为空且对应链表头部已经有元素了

             

             4.链表不为空但是链表的头部元素key和新键值对的key相同（equals相同），hash值也相同，认为是同一个元素，替换头结点。

             

             5.此时这个哈希桶对应的链表已经树化，调用RB的逻辑进行红黑树上的结点插入处理。

          

          6. 链表的插入逻辑，新节点尾插入链表尾部，如果此时链表长度大于树化阈值，则执行treeifyBin()树化处理，注意此时哈希桶对应的还是链表，若哈希桶数量小于64，只是扩容，并不树化。

          

          treeifyBin函数：若哈希桶数量小于64，只是扩容，并不树化。

          

          7.新插入的元素的Key已经存在了，只是更新Value值即可。

          

          8.判断添加元素之后整个的哈希表大小是否超过threshold，若超过则执行resize()扩容

          

          未完待续

          本文解读了HashMap中的属性 以及 Put方法 ，对hashCode和equals 方法进行了一个扩展，以及对HashMap的Key唯一性进行了解释，后篇文章博主将会更新resize方法的解读以及 HashMap的构造方法懒加载等，感谢各位继续关注博主更新~~😀

           
           公司网站注册流程  seo站长  电商平台开发公司  中国建设银行官网主页  搭建网络平台的步骤  照片制作视频