JDK8 源码解读：HashMap-变量与结构

淡淡的烟草味﹌ 2022-12-23 14:24 170阅读 0赞

### JDK8 源码解读：HashMap-变量与结构 ###

*  前言
 *  源码阅读答疑
 *  阅读计划
 *  静态变量
 *   *  DEFAULT\_INITIAL\_CAPACITY：默认初始化数组大小
     *  MAXIMUM\_CAPACITY：数组的最大容量
     *  DEFAULT\_LOAD\_FACTOR：默认负载因子
     *  TREEIFY\_THRESHOLD：单链表转红黑树阈值
     *  UNTREEIFY\_THRESHOLD：红黑树转单链表阈值
     *  MIN\_TREEIFY\_CAPACITY：最小树容量阈值
 *  变量
 *   *  table：数组部分
     *  size：HashMap 长度
     *  modCount：HashMap 被修改的次数
     *  threshold：扩容阈值
     *  loadFactor：负载因子
 *  结构
 *   *  链表结构
     *  红黑树结构
 *  结尾
 *  源码

# 前言 #

1.  看源码多写注释，方便理解
2.  对于源码中很多命名怪异的变量，一个个注释写上，你这变量命名能不能再简单点？命名规范懂不懂
3.  源码看到后面如果发现前面有什么地方不太理解，或者理解不到位，或者理解有误的，一定要回去反思，多看两遍，因为这时候最容易看出自己理解错在哪，否则后面就忘了
4.  对于实在抽象的代码，可以选择性跳过，尽量不跳吧，这个度需要自己斟酌。但是哪怕跳过，也应该知道，这个代码是干啥的，比如红黑树变色旋转，代码过于抽象，个人认为只要知道原理就好，网上写的好的讲解不少
5.  不好理解的代码，多百度，看看别人怎么说的，自己再结合的理解下

# 源码阅读答疑 #

个人对于学习源码时的体会，以及自己遇到困惑的解答，有问题可以来问  
[源码阅读问答][Link 1]

# 阅读计划 #

1.  静态常量
2.  变量
3.  链表结构
4.  红黑树结构
5.  构造函数
6.  核心方法
7.  模拟构造函数运行（帮助理解，放最后因为会涉及核心方法）

# 静态变量 #

## DEFAULT\_INITIAL\_CAPACITY：默认初始化数组大小 ##

都知道 JDK8 中，HashMap 由数组 + 单链表或者数组 + 红黑树组成  
这个静态变量就是默认的数组部分的初始大小，假设用户没有手动传入初始长度，那么初始的数组容量就是：`1 << 4 = 16`  
PS：HashMap 数组部分的容量大小，必然为 2 的 N 次方

/** * 默认初始化數組大小，初始化大小必须为 2 的 N 次方 * 1 << 4 及 2 的 4 次方為 16 * The default initial capacity - MUST be a power of two. */
    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;

## MAXIMUM\_CAPACITY：数组的最大容量 ##

数组部分的容量上限，就是 int 的最大值，假如初始化超过了这个值，依然按这个最大值处理

/** * 数组的最大容量：2^30 * The maximum capacity, used if a higher value is implicitly specified * by either of the constructors with arguments. * MUST be a power of two <= 1<<30. */
    static final int MAXIMUM_CAPACITY = 1 << 30;

## DEFAULT\_LOAD\_FACTOR：默认负载因子 ##

默认的负载因子大小，值为 0.75

很多没看过源码的人会认为当数组的使用率达到 75% 时进行扩容，至于这个使用率怎么理解，可能每个人还不一样，但都不对

负载因子作用：

1.  初始化 HashMap 时，用于计算出数组的容量大小
2.  初始化 HashMap 时，用于计算出扩容阈值

/** * 负载因子：0.75 * 用于计算初始化时数组的容量大小，最主要用于计算初始的扩容阈值 * The load factor used when none specified in constructor. */
    static final float DEFAULT_LOAD_FACTOR = 0.75f;

## TREEIFY\_THRESHOLD：单链表转红黑树阈值 ##

这个应该不需要解释，当链表的长度达到 8 这个临界值时，转为红黑树

PS：链表长度大于等于 8，只是转红黑树的条件之一。

/** * 链表桶转红黑树临界值：8，即长度大于等于 8 转红黑树 * The bin count threshold for using a tree rather than list for a * bin. Bins are converted to trees when adding an element to a * bin with at least this many nodes. The value must be greater * than 2 and should be at least 8 to mesh with assumptions in * tree removal about conversion back to plain bins upon * shrinkage. */
     static final int TREEIFY_THRESHOLD = 8;

## UNTREEIFY\_THRESHOLD：红黑树转单链表阈值 ##

PS：一般仅在扩容时，才会对节点过少的红黑树修剪为链表。移除节点时，除非红黑树的首节点的左右子节点存在 null 情况下才会转链表

只有在**扩容时候**，假如其中一颗红黑树长度小于等于 6 了，才会被转为单链表。

具体看后面代码解析。

/** * 红黑树转链表桶临界值：6，即长度小于等于 6 转链表 * The bin count threshold for untreeifying a (split) bin during a * resize operation. Should be less than TREEIFY_THRESHOLD, and at * most 6 to mesh with shrinkage detection under removal. */
    static final int UNTREEIFY_THRESHOLD = 6;

## MIN\_TREEIFY\_CAPACITY：最小树容量阈值 ##

PS：链表转红黑树的第二个条件，即单链表要想转为红黑树，除了需要链表长度大于等于 8 以外，**还需要数组的容量达到 64**

也就是说假如单链表长度大于等于 8，但是数组容量没有 64，仅仅只会进行扩容，并不会转红黑树，具体看后面代码解析。

/** * 转变成树的 Table 的最小容量，小于该值则不会进行树化，即如果数组长度小于 64 不会转红黑树 * The smallest table capacity for which bins may be treeified. * (Otherwise the table is resized if too many nodes in a bin.) * Should be at least 4 * TREEIFY_THRESHOLD to avoid conflicts * between resizing and treeification thresholds. */
    static final int MIN_TREEIFY_CAPACITY = 64;

# 变量 #

## table：数组部分 ##

HashMap 的数组部分

transient Node<K,V>[] table;

## size：HashMap 长度 ##

HashMap 长度，换种理解方式就是 HashMap 中键值对数量

transient int size;

## modCount：HashMap 被修改的次数 ##

HashMap 被修改的次数  
由于 HashMap 是非线程安全的  
所以可能出现线程 A 在操作的过程中，线程 B 对 HashMap 进行了修改  
很明显这样的操作是有问题的，这时候可以利用这个属性快速失败，即抛出 ConcurrentModificationException 并发修改异常

PS：可以理解为是乐观锁，在 forEach，repalceAll 等方法中用到

transient int modCount;

## threshold：扩容阈值 ##

扩容阈值，当 HashMap 中的键值对数量达到 threshold 时，进行扩容

int threshold;

## loadFactor：负载因子 ##

如果用户未指定，`loadFactor == DEFAULT_LOAD_FACTOR`

final float loadFactor;

# 结构 #

## 链表结构 ##

HashMap 单链表的结构很简单，父节点都会有个指向下个 hash 冲突的子节点

static class Node<K,V> implements Map.Entry<K,V> { 
    	// 数组节点对应 hash 值
        final int hash;
        final K key;
        V value;
        // hash 冲突形成链表，下个链表节点
        Node<K,V> next;
    
        Node(int hash, K key, V value, Node<K,V> next) { 
            this.hash = hash;
            this.key = key;
            this.value = value;
            this.next = next;
        }
    	// .......
    }

## 红黑树结构 ##

红黑树属性由两组结构组成，红黑树是个树结构的同时，还是个双向链表

红黑树是双向链表的目的：

1.  红黑树转为单链表时，是根据双向链表的顺序
2.  假如 HashMap 被转为 LinkedHashMap 时，根据双向链表有个顺序可循

树结构：

*  parent：指向树形结构的父级节点
 *  left：指向树形结构的左子节点
 *  right：指向树形结构的右子节点
 *  red：为 true 表示节点为红色，false 表示节点为黑色

双向链表结构：

*  prev：指向双向链表的上个节点
 *  next：指向双向链表的下个节点。  
    PS：TreeNode 继承了 LinkedHashMap.Entry，而 LinkedHashMap.Entry 还继承了HashMap.Node，HashMap.Node 是单链表，有 next 属性

static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> { 
        // 红黑树树结构部分属性
        // 红黑树的指针，指向父节点
        TreeNode<K,V> parent;
        // 红黑树的指针，指向左节点
        TreeNode<K,V> left;
        // 红黑树的指针，指向右节点
        TreeNode<K,V> right;
    
        // 红黑树链表部分属性
        // 红黑树链表部分，指向上个节点，与链表的 next 属性组合使用
        TreeNode<K,V> prev;
        // 节点颜色
        boolean red;
        TreeNode(int hash, K key, V val, Node<K,V> next) { 
            super(hash, key, val, next);
        }
    	// .......
    }

# 结尾 #

[JDK8 源码解读：HashMap-变量与结构][JDK8 _HashMap-]

[JDK8 源码解读：HashMap-构造函数][JDK8 _HashMap- 1]

[JDK8 源码解读：HashMap-核心方法][JDK8 _HashMap- 2]

# 源码 #

[JDK 1.8 源码阅读-注释版][JDK 1.8 _-]

[JDK 1.8 源码阅读][JDK 1.8]

[Link 1]: https://linjinp.blog.csdn.net/article/details/109747337/
[JDK8 _HashMap-]: https://linjinp.blog.csdn.net/article/details/110130658/
[JDK8 _HashMap- 1]: https://linjinp.blog.csdn.net/article/details/110196639/
[JDK8 _HashMap- 2]: https://linjinp.blog.csdn.net/article/details/110196734/
[JDK 1.8 _-]: https://gitee.com/linjinp/jdk1.8-leaning/
[JDK 1.8]: https://gitee.com/linjinp/jdk1.8.0_111-src/