JDK源码系列（三）—— HashMap深度源码解析-CSDN博客

本文链接：https://blog.csdn.net/LYS00Q/article/details/143317034

$\huge{\color{red}{更好的阅读体验}}$

HashMap 类

基础概念

定义

Hash 表也称为散列表，也有直接译作哈希表，Hash表是一种根据关键字值（key - value）而直接进行访问的数据结构。

哈希表，它是通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做**散列表，**只需要 O(1) 的时间级

HashMap的实现不是同步的，这意味着它不是线程安全的。它的key、value都可以为null，但 HashMap 中的映射不是有序的。

注意：

散列函数可能存在冲突，解决冲突有两种方法
开放寻址法：从冲突的位置开始，向后查找第一个可以插入的位置
拉链法：在冲突的位置后面追加节点使之成为链表

由于开放寻址法可能造成二次冲突，因此大多情况下采用拉链法解决

版本对比

JDK1.8 前 HashMap 的数据结构

JDK 8 以前 HashMap 的实现是 数组+链表，即使哈希函数取得再好，也很难达到元素百分百均匀分布。
当 HashMap 中有大量的元素都存放到同一个桶中时，这个桶下有一条长长的链表，极端情况HashMap 就相当于一个单链表，假如单链表有 n 个元素，遍历的时间复杂度就是 O(n)，完全失去了它的优势。

JDK1.8 后 HashMap 的数据结构

JDK 8 后 HashMap 的实现是 数组+链表+红黑树
桶中的结构可能是链表，也可能是红黑树，当链表长度大于阈值(或者红黑树的边界值，默认为8)并且当前数组的长度大于64时，此时此索引位置上的所有数据改为使用红黑树存储。

类构造器

public class HashMap<K,V> extends AbstractMap<K,V>
    implements Map<K,V>, Cloneable, Serializable {

JDK 为我们提供了一个抽象类 AbstractMap ，该抽象类继承 Map 接口，所以如果我们不想实现所有的 Map 接口方法，就可以选择继承抽象类 AbstractMap 。

HashMap 集合实现了 Cloneable 接口以及 Serializable 接口，分别用来进行对象克隆以及将对象进行序列化。

注意：HashMap 类即继承了 AbstractMap 接口，也实现了 Map 接口，这样做难道不是多此一举？

据 java 集合框架的创始人 Josh Bloch 描述，这样的写法是一个失误。在java集合框架中，类似这样的写法很多，最开始写java集合框架的时候，他认为这样写，在某些地方可能是有价值的，直到他意识到错了。显然的，JDK 的维护者，后来不认为这个小小的失误值得去修改，所以就这样存在下来了。

字段属性

//序列化和反序列化时，通过该字段进行版本一致性验证
private static final long serialVersionUID = 362498820763181265L;
//默认 HashMap 集合初始容量为16（必须是 2 的倍数）
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
//集合的最大容量，如果通过带参构造指定的最大容量超过此数，默认还是使用此数
static final int MAXIMUM_CAPACITY = 1 << 30;
//默认的填充因子
static final float DEFAULT_LOAD_FACTOR = 0.75f;
//当桶(bucket)上的结点数大于这个值时会转成红黑树(JDK1.8新增)
static final int TREEIFY_THRESHOLD = 8;
//当桶(bucket)上的节点数小于这个值时会转成链表(JDK1.8新增)
static final int UNTREEIFY_THRESHOLD = 6;
/**(JDK1.8新增)
* 当集合中的容量大于这个值时，表中的桶才能进行树形化 ，否则桶内元素太多时会扩容，
* 而不是树形化 为了避免进行扩容、树形化选择的冲突，这个值不能小于 4 * TREEIFY_THRESHOLD
*/
static final int MIN_TREEIFY_CAPACITY = 64;

/**
* 初始化使用，长度总是 2的幂
*/
transient Node<K,V>[] table;

/**
* 保存缓存的entrySet（）
*/
transient Set<Map.Entry<K,V>> entrySet;

/**
* 此映射中包含的键值映射的数量。（集合存储键值对的数量）
*/
transient int size;

/**
* 跟前面ArrayList和LinkedList集合中的字段modCount一样，记录集合被修改的次数
* 主要用于迭代器中的快速失败
*/
transient int modCount;

/**
* 调整大小的下一个大小值（容量*加载因子）。capacity * load factor
*/
int threshold;

/**
* 散列表的加载因子。
*/
final float loadFactor;

下面我们重点介绍上面几个字段：

Node<K,V>[] table：
- 我们说 HashMap 是由数组 + 链表 + 红黑树组成，这里的数组就是 table 字段
- 初始化长度默认是 DEFAULT_INITIAL_CAPACITY= 16，且 JDK 声明数组的长度总是 2的 n 次方(一定是合数)
size：
- 集合中存放 key-value 的实时对数
loadFactor：
- 装载因子，是用来衡量 HashMap 满的程度
- 计算HashMap的实时装载因子的方法为：size/capacity，而不是占用桶的数量去除以capacity
- capacity 是桶的数量，也就是 table 的长度length
- 默认的负载因子0.75 是对空间和时间效率的一个平衡选择，建议不要修改，除非在时间和空间比较特殊的情况下，如果内存空间很多而又对时间效率要求很高，可以降低负载因子loadFactor 的值；相反，如果内存空间紧张而对时间效率要求不高，可以增加负载因子 loadFactor 的值，这个值可以大于1
threshold：
- 计算公式：capacity * loadFactor
- 这个值是当前已占用数组长度的最大值。过这个数目就重新resize(扩容)，扩容后的 HashMap 容量是之前容量的两倍

构造函数

默认无参构造函数

/**
* 默认构造函数，初始化加载因子loadFactor = 0.75
*/
public HashMap() {
   
    this.loadFactor = DEFAULT_LOAD_FACTOR; 
}

指定初始容量的构造函数

/**
*
* @param initialCapacity 指定初始化容量
* @param loadFactor 加载因子 0.75
*/
public HashMap(int initialCapacity, float loadFactor) {
   
    //初始化容量不能小于 0 ，否则抛出异常
    if (initialCapacity < 0)
        throw new IllegalArgumentException("Illegal initial capacity: " +
                                           initialCapacity);
    //如果初始化容量大于2的30次方，则初始化容量都为2的30次方
    if (initialCapacity > MAXIMUM_CAPACITY)
        initialCapacity = MAXIMUM_CAPACITY;
    //如果加载因子小于0，或者加载因子是一个非数值，抛出异常
    if (loadFactor <= 0 || Float.isNaN(loadFactor))
        throw new IllegalArgumentException("Illegal load factor: " +
                                           loadFactor);
    this.loadFactor = loadFactor;
    this.threshold = tableSizeFor(initialCapacity);
}
// 返回大于等于initialCapacity的最小的二次幂数值。
// >>> 操作符表示无符号右移，高位取0。
// | 按位或运算
static final int tableSizeFor(int cap) {
   
    int n = cap - 1