HashMap源码详细解析

妖狐艹你老母 2022-11-30 01:48 185阅读 0赞

### HashMap源码详细解析 ###

*   *  1、重新认识HashMap
     *   *  1.1、什么是HashMap？
         *  1.2、长啥样？
         *  1.3、HashMap特点
     *  2、 知其所以然----撸源码
     *   *  2.1、 从类注释开始，能够掌握整个HashMap大致框架
         *  2.2、初始化
         *   *  2.1.1、构造方法解析
             *  2.2.2、负载因子、阈值深度解析
         *  2.3、新增
         *   *  2.3.1、新增源码分析：
             *  2.3.2、扩容
             *  2.3.3、链表树化
             *  2.3.4、红黑树拆分、链化
         *  2.4、删除
         *  2.5、查找
         *  2.6、遍历

## 1、重新认识HashMap ##

### 1.1、什么是HashMap？ ###

HashMap底层基于散列（Hash）算法，采用hash表实现键值对集合，继承了AbstractMap，实现了Map接口。最早出现在jdk1.2，允许null键和null值，null键的哈希值为0。需要注意的是HashMap不保证键值对顺序，同时非线程安全。

### 1.2、长啥样？ ###

散列算法分为散列再探测和拉链式，HashMap采用的是拉链式，并在jdk1.8后使用红黑树优化长度大于等于8的链表。也就是说，目前HashMap底层数据结构为：数组+链表+红黑树。  
数据结构如下图：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM0ODk2NzMw_size_16_color_FFFFFF_t_70_pic_center]  
如上图所示，HashMap的数据结构采用数组和单链表（或者红黑树）组成，在进行增删改查时首先根据要查找元素的hash值定位到元素所在的数组下标（也称为桶），然后再根据这个桶所存储的元素的类型（单个node，单链表或红黑树）来找到该元素。  
当单链表长度大于等于8时，转化为红黑树；当红黑树长度小于6时红黑树转化为链表。

### 1.3、HashMap特点 ###

1.  可以接受null键和null值，null键的hash值是0；
2.  元素无序，可以序列化，线程不安全；
3.  添加，查询的时间复杂度基本都是O(1);
4.  存储元素时，根据键的hash值找到对应的桶。如果出现不同的对象计算出来的hash值相同，也就是hash冲突。为了解决这个问题，使用单链表存储相同hash值的HashMap，数组中存放的相当于头节点；
5.  当单链表长度大于等于8就会转化为红黑树，当红黑树长度小于等于6，就会转化为单链表（为什么是8？后面源码会解释这个问题）

## 2、 知其所以然----撸源码 ##

### 2.1、 从类注释开始，能够掌握整个HashMap大致框架 ###

首先需要了解一些变量的含义：

//初始容量是16
    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; 
    //最大容量
    static final int MAXIMUM_CAPACITY = 1 << 30;
    //负载因子默认值0.75
    static final float DEFAULT_LOAD_FACTOR = 0.75f;
    //链表长度大于等于8时，链表转化成红黑树
    static final int TREEIFY_THRESHOLD = 8;
    
    //红黑树长度小于等于6时，红黑树转化成链表
    static final int UNTREEIFY_THRESHOLD = 6;
    
    //容量最小64时才会转会成红黑树
    static final int MIN_TREEIFY_CAPACITY = 64;
    
    //用于fail-fast的，记录HashMap结构发生变化(数量变化或rehash)的数目
    transient int modCount;
    
    //HashMap 的实际大小，不一定准确(因为当你拿到这个值的时候，可能又发生了变化)
    transient int size;
    
    // 阈值，当前HashMap所能容纳键值对数量的最大值，超过这个值，就需要扩容
    // 计算方式：
    // 阈值大小 = 数组容量 * 负载因子
    int threshold;
    
    //存放数据的数组
    transient Node<K,V>[] table;
    //链表的节点
    static class Node<K,V> implements Map.Entry<K,V> {
        }
    //红黑树的节点
    static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V>{
        }

把类注释简单进行翻译和总结如下：

*  实现 Map 接口，允许 null 值，不同于 HashTable，是线程不安全的；
 *  get和put 的实现达到了常数的时间复杂度，不过要达到好的迭代效果，initialCapacity 不要太高，loadFactor 不要太低；
 *  loadFactor 默认值 0.75，是均衡了时间和空间损耗算出来的值，较高的值会减少空间开销(扩容减少)，但增加了查找成本(hash冲突增加，链表长度变长），不扩容的条件：数组容量> 需要的数组大小 / loadFactor；
 *  如果有很多数据需要储存到 HashMap 中，建议 HashMap 的容量一开始就设置成足够的大小，这样可以防止在put过程中不断的扩容，影响性能；
 *  HashMap 是非线程安全的，为了解决多线程安全问题，我们可以自己在外部加锁，或者通过Collections\#synchronizedMap（在每个方法上加上了 synchronized 锁）来实现，注释里还举了个例子：Map m = Collections.synchronizedMap(new HashMap(…));
 *  在迭代过程中，如果 HashMap 的结构被修改，会快速失败。

### 2.2、初始化 ###

#### 2.1.1、构造方法解析 ####

// 构造方法一：指定初始容量和负载因子
    public HashMap(int initialCapacity, float loadFactor) {
        
      if (initialCapacity < 0)
        throw new IllegalArgumentException("Illegal initial capacity: " +
                                           initialCapacity);
      if (initialCapacity > MAXIMUM_CAPACITY)
        initialCapacity = MAXIMUM_CAPACITY;
      if (loadFactor <= 0 || Float.isNaN(loadFactor))
        throw new IllegalArgumentException("Illegal load factor: " +
                                           loadFactor);
      this.loadFactor = loadFactor;
      this.threshold = tableSizeFor(initialCapacity);
    }
    
    // 构造方法二：指定初始容量，此时负载因子使用默认值0.75
    public HashMap(int initialCapacity) {
        
      this(initialCapacity, DEFAULT_LOAD_FACTOR);
    }
    // 构造方法三：无参构造函数，初始容量是16，负载因子0.75，常用
    public HashMap() {
        
      this.loadFactor = DEFAULT_LOAD_FACTOR; 
    }
    
    // 构造方法四：拷贝传入的Map，并且负载因子是默认值0.75
    public HashMap(Map<? extends K, ? extends V> m) {
        
      this.loadFactor = DEFAULT_LOAD_FACTOR;
      putMapEntries(m, false);
    }

通过查看上面的源码我们会发现HashMap的构造方法一共有4个，主要是对initialCapacity，loadFactor和threshold进行初始化，并没有涉及到数据结构的初始化，这部分是延迟到在插入数据时候才会进行。  
当我们对时间和空间复杂度有要求的时候，可能就会采用第一种传入初始容量和负载因子的构造方式，这两个参数可以计算得出阈值，我们在上一节的类注释的变量的含义里说明了阈值的计算方式有两种，下面让我们深入分析一下，初始容量、负载因子、阈值之间的关系。

#### 2.2.2、负载因子、阈值深度解析 ####

**阈值threshold：**  
首先默认情况下，初始容量是16，负载因子是0.75，而没有默认的阈值，这是因为数组的初始化是延迟放在了put方法中进行，而阈值也是在扩容的时候根据公式阈值大小 = 数组容量 \* 负载因子来计算。  
那么为什么在构造方法1和2里，也就是传入了自定义初始容量的情况下，threshold不是按照这个公式计算呢，难得有特殊情况？显然不是的，这样计算出来的阈值是为了在后面扩容的时候用来变换出自定义的capacity，这部分逻辑我们后面查看扩容源码的时候会说明，下面我们需要先看下tableSizeFor方法：

/**
     * Returns a power of two size for the given target capacity.
     */
    static final int tableSizeFor(int cap) {
        
      int n = cap - 1;
      //将n无符号右移1位，并将结果与右移前的n做按位或操作，结果赋给n；
      n |= n >>> 1;
      n |= n >>> 2;
      n |= n >>> 4;
      n |= n >>> 8;
      n |= n >>> 16;
      //中间过程的目的就是使n的二进制数的低位全部变为1，比如10，11变为
      //11，100，101，110，111变为111；
      return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
    }

关于这个tableSizeFor方法可以用一句话来概括，返回大于等于cap的最小2的幂，比如传入的cap是10，那就会返回16；因为2的3次方小于10，只有返回大于且最小的2的4次方，也就是16；  
**负载因子loadFactor：**  
**loadFactor反应了HashMap桶数组的使用情况**， 当我们调低负载因子时，HashMap 所能容纳的键值对数量变少。扩容时，重新将键值对存储新的桶数组里，键的键之间产生的碰撞会下降，链表长度变短。此时，HashMap 的增删改查等操作的效率将会变高，这里是典型的拿空间换时间。相反，如果增加负载因子（负载因子可以大于1），HashMap 所能容纳的键值对数量变多，空间利用率高，但碰撞率也高。这意味着链表长度变长，效率也随之降低，这种情况是拿时间换空间。我们可以根据实际场景来调节负载因子，一般情况默认即可。

### 2.3、新增 ###

**整体概括：**  
首先我们整体上简单概括HashMap的put步骤，首先计算key的hash值，然后定位到这个hash值属于数组的哪个桶，然后判断桶是否为空，如果为空就将键值对存入即可。如果不为空，就根据那个桶的类型，决定是链表添加数据还是红黑树添加数据，最后还要根据key判断是否覆盖。在整个过程中还要时刻判断是否需要扩容，如果需要就要进行扩容操作。  
**详细流程图：**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM0ODk2NzMw_size_16_color_FFFFFF_t_70_pic_center 1]

#### 2.3.1、新增源码分析： ####

public V put(K key, V value) {
        
      // put方法实际上调用了putVal方法
      return putVal(hash(key), key, value, false, true);
    }
    // putVal方法
    // 参数：
    // hash ：通过hash算法计算出来的值
    // onlyIfAbsent：默认为false，false表示如果key存在就用新值覆盖
    final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
        
      //n 表示数组的长度，i 为数组索引下标，p 为 i 下标位置的 Node 值
      Node<K,V>[] tab; Node<K,V> p; int n, i;
      //如果数组为空，调用resize初始化（数组被延长到插入新数据时再进行初始化）
      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);
      // 如果当前索引上有值，则表示hash冲突，
      else {
        
        //e是当前节点的临时变量
        Node<K,V> e; K k;
        // 如果key的hash和值都相等，直接把当前下标位置的 Node 值赋值给临时变量
        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) {
        
            // e = p.next 表示从头开始，遍历链表
            // p.next == null 表明 p 是链表的尾节点
            //链表不包含要插入的键值对节点时，则将该节点接入到链表的最后
            if ((e = p.next) == null) {
        
              //e和p.next都是持有对null的引用,即使p.next后来赋予了值只是改变了p.next指向的引用，和e没有关系
              p.next = newNode(hash, key, value, null);
              //新增时，当链表的长度大于等于树化阈值（8）时，调用treeifyBin进行树化
              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再遍历过程中，一直往后移动
            p = e;
          }
        }
        //判断要插入的键值对是否存在HashMap中
        if (e != null) {
        
          V oldValue = e.value;
          //onlyIfAbsent 表示是否仅在oldValue为null的情况下更新键值对的值
          if (!onlyIfAbsent || oldValue == null)
            e.value = value;
          // 当前节点移动到队尾
          afterNodeAccess(e);
          // 返回老值
          return oldValue;
        }
      }
      // 为了fail-fast，记录HashMap的数据结构变化
      ++modCount;
      //键值对数量大于阈值时，开始扩容
      if (++size > threshold)
        resize();
      // 删除不经常使用的元素
      afterNodeInsertion(evict);
      return null;
    }

以上就是put的整体源码解析，相信对照着流程图已经很清晰了，这里面还有扩容，链表树化和拆分方法，下面我们一一解析。

#### 2.3.2、扩容 ####

首先要知道几个HashMap扩容的概念：

*  数组的长度均是2的幂；
 *  阈值大小 = 容量（数组长度） \* 负载因子；
 *  当HashMap中的键值对数量超过阈值时进行扩容；
 *  扩容后，数组和阈值变为原来的2倍（如果计算过程中，阈值溢出归零，则按阈值公式重新计算）；
 *  扩容之后，要重新计算键值对的位置，然后把它们移动到合适的位置上。  
    下面，我们查看源码的实现：

final Node<K,V>[] resize() {
        
    Node<K,V>[] oldTab = table;
     int oldCap = (oldTab == null) ? 0 : oldTab.length;
     int oldThr = threshold;
     int newCap, newThr = 0;
    // 如果数组不为空（已经初始化过）
     if (oldCap > 0) {
        
         //老数组大小大于等于容量最大值，不扩容
         if (oldCap >= MAXIMUM_CAPACITY) {
        
             threshold = Integer.MAX_VALUE;
             return oldTab;
         }
         //判断老数组大小2倍是否在最小值和最大值之间，如果是就可以扩容
         else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                  oldCap >= DEFAULT_INITIAL_CAPACITY)
             newThr = oldThr << 1; // double threshold
     }
     else if (oldThr > 0) // initial capacity was placed in threshold
       // 之前指定初始容量的构造函数使用threshold暂时保存initialCapacity 参数的值
       // 初始化时，将 threshold 的值赋值给 newCap
         newCap = oldThr;
     else {
        
         // zero initial threshold signifies using defaults
         //这部分为无参构造方法，数组容量为默认值
         newCap = DEFAULT_INITIAL_CAPACITY;
       	//计算阈值
         newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
     }
    // newThr 为 0 时，按阈值计算公式进行计算
     if (newThr == 0) {
        
         float ft = (float)newCap * loadFactor;
         newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                   (int)ft : Integer.MAX_VALUE);
     }
     threshold = newThr;
    // 创建新的数组，数组的初始化也是在这里完成的
     Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
     table = newTab;
     if (oldTab != null) {
        
       	// 如果旧的数组不为空，则遍历数组，并将键值对映射到新的数组中
         for (int j = 0; j < oldCap; ++j) {
        
             Node<K,V> e;
             if ((e = oldTab[j]) != null) {
        
                 oldTab[j] = null;
                 //节点只有一个值，直接计算索引位置赋值
                 if (e.next == null)
                     newTab[e.hash & (newCap - 1)] = e;
                 //红黑树
                 else if (e instanceof TreeNode)
                   	// 重新映射时，需要对红黑树进行拆分
                     ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                 //规避了8版本以下的成环问题
                 else {
         // preserve order
                     // loHead 表示老值,老值的意思是扩容后，该链表中计算出索引位置不变的元素
                     // hiHead 表示新值，新值的意思是扩容后，计算出索引位置发生变化的元素
                     // 举个例子，数组大小是 8 ，在数组索引位置是 1 的地方挂着两个值，两个值的 hashcode 是9和33。
                     // 当数组发生扩容时，新数组的大小是 16，此时 hashcode 是 33 的值计算出来的数组索引位置仍然是 1，我们称为老值
                     // hashcode 是 9 的值计算出来的数组索引位置是 9，就发生了变化，我们称为新值。
                     Node<K,V> loHead = null, loTail = null;
                     Node<K,V> hiHead = null, hiTail = null;
                     Node<K,V> next;
                     // java 7 是在 while 循环里面，单个计算好数组索引位置后，单个的插入数组中，在多线程情况下，会有成环问题
                     // java 8 是等链表整个 while 循环结束后，才给数组赋值，所以多线程情况下，也不会成环
                   // 遍历链表，并将链表节点按原顺序进行分组
                     do {
        
                         next = e.next;
                         // (e.hash & oldCap) == 0 表示老值链表
                         if ((e.hash & oldCap) == 0) {
        
                             if (loTail == null)
                                 loHead = e;
                             else
                                 loTail.next = e;
                             loTail = e;
                         }
                         // (e.hash & oldCap) == 0 表示新值链表
                         else {
        
                             if (hiTail == null)
                                 hiHead = e;
                             else
                                 hiTail.next = e;
                             hiTail = e;
                         }
                     } while ((e = next) != null);
                     // 将分组后的链表映射到新桶中
                     if (loTail != null) {
        
                         loTail.next = null;
                         newTab[j] = loHead;
                     }
                     // 新值链表赋值到新的数组索引位置
                     if (hiTail != null) {
        
                         hiTail.next = null;
                         newTab[j + oldCap] = hiHead;
                     }
                 }
             }
         }
     }
     return newTab;
    }

小结一下扩容：

*  计算新数组的容量 newCap 和新阈值 newThr；
 *  根据计算出的 newCap 创建新的数组，数组 table 也是延迟在这里进行初始化的；
 *  将键值对节点重新映射到新的数组里。如果节点是 TreeNode 类型，则需要拆分红黑树。如果是普通节点，则节点按原顺序进行分组。

#### 2.3.3、链表树化 ####

链表的树化其实就是为了解决链表过长后查询效率低下的问题，因此在jdk1.8之后引入了红黑树来处理频繁的hash冲突。

//首先看HashMap里红黑树的定义：
    static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
        
    TreeNode<K,V> parent;  // red-black tree links 红黑树父节点
    TreeNode<K,V> left;//左节点
    TreeNode<K,V> right;//右节点
    TreeNode<K,V> prev;    // needed to unlink next upon deletion
    boolean red;
    TreeNode(int hash, K key, V val, Node<K,V> next) {
        
      super(hash, key, val, next);
    }
    
    //找到红黑树的根节点，根据根节点没有父节点来判断
    final TreeNode<K,V> root() {
        
      for (TreeNode<K,V> r = this, p;;) {
        
          if ((p = r.parent) == null)
              return r;
          r = p;
      }
    }
    
    //把给定的root放到根节点上去
    static <K,V> void moveRootToFront(Node<K,V>[] tab, TreeNode<K,V> root) {
        
      int n;
      if (root != null && tab != null && (n = tab.length) > 0) {
        
          int index = (n - 1) & root.hash;
          TreeNode<K,V> first = (TreeNode<K,V>)tab[index];//找到当前树的根节点
          //如果root不是根节点，就把root放到根节点上去，分成2步
          //1:解决root下面节点的问题
          //2:把root放到当前根节点first的左边去
          if (root != first) {
        
              Node<K,V> rn;
              tab[index] = root;
              TreeNode<K,V> rp = root.prev;
              //下面的两个if是为了解决步骤1。
              // 把root的next挂在自己prev的后面即可
              // 就是把自己摘掉，后面一位和前面一位连接起来
              if ((rn = root.next) != null)
                  ((TreeNode<K,V>)rn).prev = rp;
              if (rp != null)
                  rp.next = rn;
              //这个if解决了步骤2 把root当作根节点，并且设置prev为null
              if (first != null)
                  first.prev = root;
              root.next = first;
              root.prev = null;
          }
          assert checkInvariants(root);
      }
    }

下面我们需要知道两个变量：

*  当链表长度大于等于TREEIFY\_THRESHOLD时调用树化方法，但是注意，此时不一定树化；
 *  在树化代码里会进行判断，只有当数组容量大于MIN\_TREEIFY\_CAPACITY时，才会树化，否则只会进行扩容。

static final int TREEIFY_THRESHOLD = 8;
    static final int MIN_TREEIFY_CAPACITY = 64;

接下来我们分析链表树化方法treefyBin的源码：

final void treeifyBin(Node<K,V>[] tab, int hash) {
        
      int n, index; Node<K,V> e;
      // 如果数组容量小于MIN_TREEIFY_CAPACITY，优先进行扩容，不进行树化
      if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
        resize();
      else if ((e = tab[index = (n - 1) & hash]) != null) {
        
        // hd：头节点head
        // tl：尾节点tail
        TreeNode<K,V> hd = null, tl = null;
        do {
        
          // 将普通节点替换成树形节点
          TreeNode<K,V> p = replacementTreeNode(e, null);
          if (tl == null)
            hd = p;
          else {
        
            p.prev = tl;
            tl.next = p;
          }
          tl = p;
        } while ((e = e.next) != null); // 普通链表转化成树形节点链表
        if ((tab[index] = hd) != null)
          // 调用treeify方法把树形节点链表转化成红黑树
          hd.treeify(tab);
      }
    }

通过上面的源码和解释，可以发现在扩容过程中，树化需要同时满足两个条件：**链表长度大于等于TREEIFY\_THRESHOLD也就是默认的8，数组容量大于等于MIN\_TREEIFY\_CAPACITY也就是默认的64。**  
那么，为什么链表长度大于等于8时，容量大于等于64才会进行树化呢？其实源码类注释里已经告诉了我们答案：

* Because TreeNodes are about twice the size of regular nodes, we
     * use them only when bins contain enough nodes to warrant use
     * (see TREEIFY_THRESHOLD). And when they become too small (due to
     * removal or resizing) they are converted back to plain bins.  In
     * usages with well-distributed user hashCodes, tree bins are
     * rarely used.  Ideally, under random hashCodes, the frequency of
     * nodes in bins follows a Poisson distribution
     * (http://en.wikipedia.org/wiki/Poisson_distribution) with a
     * parameter of about 0.5 on average for the default resizing
     * threshold of 0.75, although with a large variance because of
     * resizing granularity. Ignoring variance, the expected
     * occurrences of list size k are (exp(-0.5) * pow(0.5, k) /
     * factorial(k)). The first values are:
     *
     * 0:    0.60653066
     * 1:    0.30326533
     * 2:    0.07581633
     * 3:    0.01263606
     * 4:    0.00157952
     * 5:    0.00015795
     * 6:    0.00001316
     * 7:    0.00000094
     * 8:    0.00000006
     * more: less than 1 in ten million

总结一下这段解释：  
同样的数据下，红黑树需要占用的空间是链表的2倍，但是在链表数据不多的时候，使用链表进行遍历也很快（链表查询的时间复杂度是 O (n)，红黑树的查询复杂度是 O (log (n))）。因此综合考虑转化时间和空间的损耗，这里参考了泊松分布概率函数，在随机hashCodes下，链表的各个长度的命中概率分别为：

* 0:    0.60653066
         * 1:    0.30326533
         * 2:    0.07581633
         * 3:    0.01263606
         * 4:    0.00157952
         * 5:    0.00015795
         * 6:    0.00001316
         * 7:    0.00000094
         * 8:    0.00000006

当链表长度大于等于8时，概率不到千万分之一。也就是说正常情况下写代码，是不会触发链表转红黑树的，除非在特定情况下hash算法出现了问题，很多节点碰撞到了一起，这时候为了保持HashMap的查询性能，就会把考虑链表转化成红黑树。  
至于为什么数组容量较小时要进行扩容而不是树化，这是因为数组容量小是较高hash碰撞的主因，当数组的容量大了，自然同样数据量的碰撞率也会下降。因此当数组容量较小时，优先考虑扩容而不是树化，这样可以根本上来解决效率问题。

#### 2.3.4、红黑树拆分、链化 ####

在扩容之后，节点的数据需要重新映射，这里HashMap很巧妙的通过两个额外的引用next和pre，保留了之前原链表的节点顺序。因此不需要把红黑树转化成链表，而是直接按照之前映射链表的方式进行映射就可以了。  
下面我们看一下红黑树拆分的源码实现：

final void split(HashMap<K,V> map, Node<K,V>[] tab, int index, int bit) {
        
        TreeNode<K,V> b = this;
        TreeNode<K,V> loHead = null, loTail = null;
        TreeNode<K,V> hiHead = null, hiTail = null;
        int lc = 0, hc = 0;
        /* 
         * 红黑树节点仍然保留了 next 引用，故仍可以按链表方式遍历红黑树。
         * 下面的循环是对红黑树节点进行分组，与上面类似
         */
        for (TreeNode<K,V> e = b, next; e != null; e = next) {
        
            next = (TreeNode<K,V>)e.next;
            e.next = null;
            if ((e.hash & bit) == 0) {
        
                if ((e.prev = loTail) == null)
                    loHead = e;
                else
                    loTail.next = e;
                loTail = e;
                ++lc;
            }
            else {
        
                if ((e.prev = hiTail) == null)
                    hiHead = e;
                else
                    hiTail.next = e;
                hiTail = e;
                ++hc;
            }
        }
    
        if (loHead != null) {
        
            // 如果 loHead 不为空，且链表长度小于等于 6，则将红黑树转成链表
            if (lc <= UNTREEIFY_THRESHOLD)
                tab[index] = loHead.untreeify(map);
            else {
        
                tab[index] = loHead;
                /* 
                 * hiHead == null 时，表明扩容后，
                 * 所有节点仍在原位置，树结构不变，无需重新树化
                 */
                if (hiHead != null) 
                    loHead.treeify(tab);
            }
        }
        // 与上面类似
        if (hiHead != null) {
        
            if (hc <= UNTREEIFY_THRESHOLD)
                tab[index + bit] = hiHead.untreeify(map);
            else {
        
                tab[index + bit] = hiHead;
                if (loHead != null)
                    hiHead.treeify(tab);
            }
        }
    }

通过以上源码，我们发现映射红黑树的逻辑和重新映射链表的逻辑类似，只是重新映射后红黑树会被拆分成两条树节点的链表。这个时候如果链表长度小于UNTREEIFY\_THRESHOLD也就是默认的6，则将树节点链表转换成普通单链表，否则根据条件重新将树节点链表树化。  
**接着，我们看一下红黑树链化的源码：**

final Node<K,V> untreeify(HashMap<K,V> map) {
        
        Node<K,V> hd = null, tl = null;
        // 遍历 TreeNode 链表，并用 Node 替换
        for (Node<K,V> q = this; q != null; q = q.next) {
        
            // 替换节点类型
            Node<K,V> p = map.replacementNode(q, null);
            if (tl == null)
                hd = p;
            else
                tl.next = p;
            tl = p;
        }
        return hd;
    }

### 2.4、删除 ###

HashMap的删除操作是比较简单的：

1.  根据要删除的键的hash来定位数组下标位置；
2.  遍历链表或红黑树找到键值相等的节点；
3.  删除节点并修复链表或红黑树即可。  
    下面我们看一下源码：

public V remove(Object key) {
        
      Node<K,V> e;
      // remove方法实际引用的是removeNode方法
      return (e = removeNode(hash(key), key, null, false, true)) == null ?
        null : e.value;
    }
    
    // removeNode
    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;
      // 根据要删除的键的hash来定位数组下标位置
      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) {
        
          // 如果是TreeNode类型，就调用红黑树的查找逻辑来找到要删除的节点
          if (p instanceof TreeNode)
            node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
          else {
        
            // 如果不是TreeNode类型，遍历链表，找到要删除的节点
            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;
    }

### 2.5、查找 ###

HashMap的查找只需要二步就可以了：

1.  根据key的Hash来定位它所在数组的下标位置；
2.  根据找到的节点的类型（有无next节点，有的话是链表类型，没有就是红黑树类型），对链表或者红黑树进行查找即可。  
    下面我们分析一下源码：

public V get(Object key) {
        
        Node<K,V> e;
      	// get方法实际上是调用了getNode方法
      	// 注意：这里get方法引用getNode时，并不是传入的java里面的hashcode计算出的hash值，而是引用了hash方法，重新根据key计算的hash值，这一点后面会详细解释。
        return (e = getNode(hash(key), key)) == null ? null : e.value;
    }
    
    final Node<K,V> getNode(int hash, Object key) {
        
        Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
        // 根据key及hash定位数组的下标位置
        if ((tab = table) != null && (n = tab.length) > 0 &&
            (first = tab[(n - 1) & hash]) != null) {
        
            if (first.hash == hash && // always check first node
                ((k = first.key) == key || (key != null && key.equals(k))))
                return first;
            if ((e = first.next) != null) {
        
                // 如果 first 是 TreeNode 类型，则调用黑红树查找方法
                if (first instanceof TreeNode)
                    return ((TreeNode<K,V>)first).getTreeNode(hash, key);
                    
                // 对链表进行查找
              	// 采用自旋方式从链表中查找 key，e 初始为为链表的头节点
                do {
        
                   // 如果当前节点 hash 等于 key 的 hash，并且 equals 相等，当前节点就是我们要找的节点
        		 // 当 hash 冲突时，同一个 hash 值上是一个链表的时候，我们是通过 equals 方法来比较 key 是否相等的
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        return e;
                  // 否则，把当前节点的下一个节点拿出来继续寻找
                } while ((e = e.next) != null);
            }
        }
          return null;
    }

这里面有个地方需要深入分析一下：

// n是数组的大小
    first = tab[(n - 1) & hash]

首先解释一下这行代码的的作用：**通过(n - 1) & hash可以计算出要查找的键值对在数组的位置。**  
在理解这个之前，我们先要知道HashMap里hash是怎么判断自己在哪个索引位置的？其实很简单，由于HashMap中数组的大小总是以2倍去扩容的，因此永远都是2的幂，并且HashMap采用键的hash对数组长度length取余，这个余数就是hash所在数组的位置。  
几个例子：  
数组的长度是16，某个键getNode里传入的hash是66，那它就应该在66对16取余，也就是下标为2的位置上。  
用(n - 1) & hash计算就是：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM0ODk2NzMw_size_16_color_FFFFFF_t_70_pic_center 2]  
转化为10进制后也是2，而且位运算的效率较高。  
就是传入getNode方法的hash值不是键的hashCode方法产生的hash值，而是调用了一个叫做hash的方法重新进行了计算，那么为什么要这样呢？  
我们先看这里hash的源码：

static final int hash(Object key) {
        
      int h;
      // 通过位运算重新计算hash值
      return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }

**HashMap不直接使用键对象原始hash有两个原因：**

1.  这里主要是对hashCode方法产生的hash的高16位和低16位进行异或，用来加大低位信息的随机性，间接的让高位的数据参与到了计算中；
2.  增加hash的复杂度，为了防止在我们重写hashCode方法后产生分布性不佳的hash，进而造成hash冲突较高的问题。

### 2.6、遍历 ###

在使用HashMap的时候，遍历是非常常用的一个操作。遍历的过程中会出现一个奇怪的问题，就是数据输出的顺序大部分情况下都和输入顺序不一样，但是每次输出的顺序都是一致的，这是怎么回事呢？  
当我们使用如下方式遍历HashMap时：

for(Object key :hashMap.keySet()){
        }

虽然我们使用的是增强for循环来遍历，但是编译器最终会转化成迭代器遍历：

Iterator var2 = hashMap.keySet().iterator();
    while(var2.hasNext()) {
        
        Object key = var2.next();
    }

那么我们带着问题，去源码里查找答案：

public Set<K> keySet() {
        
        Set<K> ks = keySet;
        if (ks == null) {
        
            ks = new KeySet();
            keySet = ks;
        }
        return ks;
    }
    // KeySet
      final class KeySet extends AbstractSet<K> {
        
          public final int size(){
         return size; }
          public final void clear(){
         HashMap.this.clear(); }
          public final Iterator<K> iterator(){
         return new KeyIterator(); }
          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 new KeySpliterator<>(HashMap.this, 0, -1, 0, 0);
          }
          public final void forEach(Consumer<? super K> action) {
        
              Node<K,V>[] tab;
              if (action == null)
                  throw new NullPointerException();
              if (size > 0 && (tab = table) != null) {
        
                  int mc = modCount;
                  for (int i = 0; i < tab.length; ++i) {
        
                      for (Node<K,V> e = tab[i]; e != null; e = e.next)
                          action.accept(e.key);
                  }
                  if (modCount != mc)
                      throw new ConcurrentModificationException();
              }
          }
      }
    
    // KeyIterator
    final class KeyIterator extends HashIterator 
      implements Iterator<K> {
        
      public final K next() {
         return nextNode().key; }
    }
    
    abstract class HashIterator {
        
      Node<K,V> next;        // next entry to return
      Node<K,V> current;     // current entry
      int expectedModCount;  // for fast-fail
      int index;             // current slot
    
      HashIterator() {
        
          expectedModCount = modCount;
          Node<K,V>[] t = table;
          current = next = null;
          index = 0;
          if (t != null && size > 0) {
         // advance to first entry 
              // 寻找第一个包含链表节点引用的索引位置
              do {
        } while (index < t.length && (next = t[index++]) == null);
          }
      }
    
      public final boolean hasNext() {
        
          return next != null;
      }
    
      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;
      }
      //下面代码不重要，省略
    }

**那么到这里我们就能得出结论了，以KeySet方式为例，HashMap遍历的原理：**

1.  首先获取键集合keySet对象；
2.  然后通过迭代器KeyIterator进行遍历（KeyIterator 类继承自HashIterator类）；
3.  HashIterator初始化时先从数组中找到所有包含链表节点引用的索引位置；
4.  从第一个位置开始，对它指向的链表进行遍历，遍历完成后，再从下一个位置开始遍历下一个指向的链表；
5.  找不到下一个索引位置，结束遍历。  
    那么到这里我们可以举一个例子加深理解：  
    为了便于计算，我们新增6个键值对到HashMap，它们的key分别是：

// key为Integer类型，value不重要，比如可以取String类型，传入“”即可
    5，9，16，6，21，19

我们如果按照以上顺序把这些键值对存入HashMap，根据我们前面学到的源码知识，这时候数组长度是16，这6个元素分别对应的数组索引位置为：

5->5
    9->9
    16->0
    6->6
    21->5
    19->3

那根据我们分析的遍历源码，可知，最终输出的结果顺序是：

16 -> 19 -> 5 -> 21 ->6 ->9

下面我们验证一下：

import java.util.HashMap;
    
    public class TestHashMap {
        
        public static void main(String[] args) {
        
            HashMap<Integer,String> hashMap = new HashMap<>();
            hashMap.put(5,"");
            hashMap.put(9,"");
            hashMap.put(16,"");
            hashMap.put(6,"");
            hashMap.put(21,"");
            hashMap.put(19,"");
    
            for(Object key :hashMap.keySet()){
        
                System.out.print(key +"->");
            }
        }
    }

运行后，结果为：  
![在这里插入图片描述][20200823100335120.png_pic_center]  
**和我们计算的顺序完全一致！**

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM0ODk2NzMw_size_16_color_FFFFFF_t_70_pic_center]: /images/20221124/778f0ad395cc4ff7ace41c5ff3973bc5.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM0ODk2NzMw_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221124/241c55ccdc61426e9a2e03eef8697935.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM0ODk2NzMw_size_16_color_FFFFFF_t_70_pic_center 2]: /images/20221124/e0d5424a626746588eba38906345917f.png
[20200823100335120.png_pic_center]: /images/20221124/00e220d6590449958eb577bcb9a842a5.png