Java集合源码HashMap（JDK1.8）

快来打我* 2022-03-18 08:56 362阅读 0赞

# 一、Java集合源码HashMap（JDK1.8） #

# 一、简介 #

1、继承关系

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

*  1
 *  2
 *  3

**（1）继承了AbstractMap**  
**（2）实现了Map接口，拥有一组Map通用操作**  
**（3）实现了Cloneable接口，可以进行拷贝**  
**（4）实现了Serializable接口，可以将HashMap对象保存至本地**

2、特点

**（1）允许键 / 值为空对象**  
**（2）非线程安全的**  
**（3）HashMap内的元素是无序的**

# 二、底层结构 #

**    在JDK1.7之前，HashMap采用的是数组+链表的结构，其结构图如下：**  
![这里写图片描述][70]  
    左边部分代表Hash表，数组的每一个元素都是一个单链表的头节点，链表是用来解决冲突的，如果不同的key映射到了数组的同一位置处，就将其放入单链表中。  
**    在JDK1.8，HashMap引入了红黑树，其结构图如下：**  
![这里写图片描述][70 1]  
**抛出问题：为什么加入红黑树？加入红黑树有什么作用？**  
    没有加入红黑树时，hash值冲突的时候，就将对应节点以链表形式存储。如果在一个链表中查找一个节点时，将会花费O( n )的查找时间，会有很大的性能损失。到了JDK1.8，当同一个Hash值的节点数大于8时，不再采用单链表形式存储，而是采用红黑树，这样查找节点的时间复杂福降为O( logn )。

# 三、HashMap存储流程 #

![这里写图片描述][70 2]

# 四、重要的字段 #

**HashMap中有几个重要的字段，如下：**  
**1. 默认容量： 必须是2的幂**  
**static final int DEFAULT\_INITIAL\_CAPACITY = 1 << 4;**   
**2. 最大容量： 2的30次方**  
**static final int MAXIMUM\_CAPACITY = 1 << 30;**   
**3. 默认加载因子**  
**static final float DEFAULT\_LOAD\_FACTOR = 0.75f;**  
**4. 实际加载因子**  
**final float loadFactor;**  
**5. 扩容阈值**  
**当哈希表的大小 ≥ 扩容阈值时，就会扩容哈希表（即扩充HashMap的容量）/b>  
（1）扩容 = 对哈希表进行resize操作（即重建内部数据结构），从而哈希表将具有大约两倍的桶数/b>  
（2）扩容阈值 = 容量 x 加载因子  
int threshold;  
6. Hash表结构  
存储数据的Node类型 数组，长度 = 2的幂；数组的每个元素 = 1个单链表**

transient Node <K,V>[] table;

*  1

**7. HashMap大小**  
**transient int size;**  
**与红黑树相关的字段**  
**1. 桶的树化阈值**  
**即 链表转成红黑树的阈值，在存储数据时，当链表长度 > 该值时，则将链表转换成红黑树**  
**static final int TREEIFY\_THRESHOLD = 8;**  
**2. 桶的链表还原阈值**  
**即 红黑树转为链表的阈值，当在扩容（resize（））时（此时HashMap的数据存储位置会重新计算），在重新计算存储位置后，当原有的红黑树内数量 < 6时，则将 红黑树转换成链表**  
**static final int UNTREEIFY\_THRESHOLD = 6;**  
**3. 最小树形化容量阈值**  
**当哈希表中的容量 > 该值时，才允许树形化链表 （即 将链表 转换成红黑树）否则，若桶内元素太多时，则直接扩容，而不是树形化**  
**抛出问题：加载因子的影响？**  
**加载因子大：**  
优点：  
    填满的元素多，空间利用率高。  
缺点：  
    冲突概率变大，链表变长，查找效率变小。   
**加载因子小：**  
优点：  
    冲突概率减小，链表短，查找速率高  
缺点：  
    空间利用率低，频繁扩容耗费性能

# 五、构造函数 #

**申明HashMap对象的方法：**

Map<String,Integer> map = new HashMap<String,Integer>();

*  1

**HashMap一共有4个构造方法，主要的工作就是完成容量和加载因子的赋值。Hash表都是采用的懒加载方式，当第一次插入数据时才会创建。  
（1）构造方法1：**

// 构造函数1：默认构造函数（无参）
    // 加载因子 & 容量 = 默认 = 0.75、16
    public HashMap() {
            this.loadFactor = DEFAULT_LOAD_FACTOR; 
     }

*  1
 *  2
 *  3
 *  4
 *  5

**（2）构造方法2：**

// 构造函数2：指定“容量大小”的构造函数
    // 加载因子 = 默认 = 0.75 、容量 = 指定大小
     public HashMap(int initialCapacity) {
            this(initialCapacity, DEFAULT_LOAD_FACTOR);
     }

*  1
 *  2
 *  3
 *  4
 *  5

**（3）构造方法3：**

// 构造函数3：指定“容量大小”和“加载因子”的构造函数
    // 加载因子 & 容量 = 自己指定
    public HashMap(int initialCapacity, float loadFactor) {
            // 指定初始容量必须非负，否则报错 
            if (initialCapacity < 0)
                  throw new IllegalArgumentException("Illegal initial capacity: " +
                                                   initialCapacity);
            // HashMap的最大容量只能是MAXIMUM_CAPACITY
            if (initialCapacity > MAXIMUM_CAPACITY)
                  initialCapacity = MAXIMUM_CAPACITY;
            // 填充比必须为正 
            if (loadFactor <= 0 || Float.isNaN(loadFactor))
                 throw new IllegalArgumentException("Illegal load factor: " + loadFactor);
            // 设置 加载因子
            this.loadFactor = loadFactor;
            // 设置 扩容阈值
            // 注：此处不是真正的阈值，仅仅只是将传入的容量大小转化为：>传入容量大小的     
            // 最小的2的幂，该阈值后面会重新计算
            this.threshold = tableSizeFor(initialCapacity);
     }

*  1
 *  2
 *  3
 *  4
 *  5
 *  6
 *  7
 *  8
 *  9
 *  10
 *  11
 *  12
 *  13
 *  14
 *  15
 *  16
 *  17
 *  18
 *  19
 *  20

**（4）构造方法4：**

// 构造函数4：包含“子Map”的构造函数
    // 即 构造出来的HashMap包含传入Map的映射关系
    //     加载因子 & 容量 = 默认
     public HashMap(Map<? extends K, ? extends V> m) {
            // 设置容量大小 & 加载因子 = 默认
            this.loadFactor = DEFAULT_LOAD_FACTOR;
            // 将传入的子Map中的全部元素逐个添加到HashMap中
            putMapEntries(m, false);
     }

*  1
 *  2
 *  3
 *  4
 *  5
 *  6
 *  7
 *  8
 *  9

**分析下tableSizeFor函数：**

/**
         * tableSizeFor(initialCapacity)
         * 作用：将传入的容量大小转化为：>传入容量大小的最小的2的幂
         * 与JDK 1.7对比：类似于JDK 1.7 中 inflateTable()里roundUpToPowerOf2(toSize)
     */
        static final int tableSizeFor(int cap) {
         int n = cap - 1;
         n |= n >>> 1;
         n |= n >>> 2;
         n |= n >>> 4;
         n |= n >>> 8;
         n |= n >>> 16;
         return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
    }

*  1
 *  2
 *  3
 *  4
 *  5
 *  6
 *  7
 *  8
 *  9
 *  10
 *  11
 *  12
 *  13
 *  14

**此处仅用于接收初始容量大小（capacity）、加载因子(Load factor)，但仍无真正初始化哈希表，即初始化存储数组table。  
此处先给出结论：真正初始化哈希表（初始化存储数组table）是在第1次添加键值对时，即第1次调用put（）时。下面会详细说明**

# 六、向HashMap添加数据 #

public V put(K key, V value) {
            // 1. 对传入数组的键Key计算Hash值 ->>分析点1
            // 2. 再调用putVal（）添加数据进去 ->>分析点2
            return putVal(hash(key), key, value, false, true);
      }

*  1
 *  2
 *  3
 *  4
 *  5

（1）、hash ( key )

**作用：计算传入数据的哈希码（哈希值、Hash值）  
该函数在JDK 1.7 和 1.8 中的实现不同，但原理一样 = 扰动函数 = 使得根据key生成的哈希码（hash值）分布更加均匀、更具备随机性，避免出现hash值冲突（即指不同key但生成同1个hash值）  
\* JDK 1.7 做了9次扰动处理 = 4次位运算 + 5次异或运算  
\* JDK 1.8 简化了扰动函数 = 只做了2次扰动 = 1次位运算 + 1次异或运算\\**  
**JDK 1.7实现：将 键key 转换成 哈希码（hash值）操作 = 使用hashCode() + 4次位运算 + 5次异或运算（9次扰动）**  
**static final int hash(int h) \{  
     h ^= k.hashCode();  
     h ^= (h >>> 20) ^ (h >>> 12    );  
     return h ^ (h >>> 7) ^ (h >>> 4);  
\}**  
**// JDK 1.8实现：将 键key 转换成 哈希码（hash值）操作 = 使用hashCode() + 1次位运算 + 1次异或运算（2次扰动）  
// 1. 取hashCode值： h = key.hashCode()  
// 2. 高位参与低位的运算：h ^ (h >>> 16)**   
**static final int hash(Object key) \{  
     int h;  
     return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);  
\}**  
**// a. 当key = null时，hash值 = 0，所以HashMap的key 可为null  
// 注：对比HashTable，HashTable对key直接hashCode（），若key为null时，会抛出异常，所以HashTable的key不可为null  
// b. 当key ≠ null时，则通过先计算出 key的 hashCode()（记为h），然后 对哈希码进行 扰动处理： 按位 异或（^） 哈希码自身右移16位后的二进制**

（2）存放在数组 table 中的位置

**h & (length-1);  
// 将对哈希码扰动处理后的结果 与运算(&) （数组长度-1），最终得到存储在数组table的位置（即数组下标、索引）**  
**具体分析一下这个过程：**  
**\* h = key.hashCode()  
根据对象的内存地址，经过算法返回一个哈希码  
\* h ^ h ( h >>> 16 )  
扰动处理：哈希码的高16为不变、低16位 = 低16位 ^ 高16位  
\* h & ( length - 1 )  
扰动处理后的哈希码 & （数组长度 - 1）**   
  
**图片示意流程：**  
![这里写图片描述][70 3]  
**抛出问题：  
（1）为什么不直接采用经过hashCode（）处理的哈希码 作为 存储数组table的下标位置？**  
**        容易出现 哈希码 与 数组大小范围不匹配的情况，即 计算出来的哈希码可能 不在数组大小范围内，从而导致无法匹配存储位置。为了解决 “哈希码与数组大小范围不匹配” 的问题，HashMap给出了解决方案：哈希码 与运算（&） （数组长度-1)**  
**（2）为什么采用 哈希码 与运算(&) （数组长度-1） 计算数组下标？**  
**        根据HashMap的容量大小（数组长度），按需取 哈希码一定数量的低位 作为存储的数组下标位置，从而 解决 “哈希码与数组大小范围不匹配” 的问题。  
        数组的长度为偶数（二进制最后一位为0）。数组的长度-1为奇数（二级制最后一位为1），与哈希码进行&运算之后，可能为奇数也可能为偶数。否则的话会浪费一般的空间。**

（2）putVal(hash(key), key, value, false, true);

**1. 若哈希表的数组tab为空，则 通过resize() 创建  
// 所以，初始化哈希表的时机 = 第1次调用put函数时，即调用resize() 初始化创建  
// 关于resize（）的源码分析将在下面讲解扩容时详细分析，此处先跳过**  
**if ((tab = table) == null || (n = tab.length) == 0)  
     n = (tab = resize()).length;**   
**// 2. 计算插入存储的数组索引i：根据键值key计算的hash值 得到  
// 此处的数组下标计算方式 = i = (n - 1) & hash，同JDK 1.7中的indexFor（），上面已详细描述  
// 3. 插入时，需判断是否存在Hash冲突：  
// 若不存在（即当前table\[i\] == null），则直接在该数组位置新建节点，插入完毕  
// 否则，代表存在Hash冲突，即当前存储位置已存在节点，则依次往下判断：a. 当前位置的key是否与需插入的key相同、b. 判断需插入的数据结构是否为红黑树 or 链表**  
**if ((p = tab\[i = (n - 1) & hash\]) == null)  
    tab\[i\] = newNode(hash, key, value, null);**

> **转载请标明出处，原文地址：[https://blog.csdn.net/weixin\_41835916][https_blog.csdn.net_weixin_41835916]  
> 如果觉得本文对您有帮助，请点击顶支持一下，您的支持是我写作最大的动力，谢谢。**

[70]: /images/20220318/7fcd3ba1349c447095d750617452fb0b.png
[70 1]: /images/20220318/ec38661a62cb4ca584a976f40685c456.png
[70 2]: /images/20220318/70cdb8ba62984714acccdc1a3d0b8d9b.png
[70 3]: /images/20220318/2a0768aaa078479c852a78686d25748f.png
[https_blog.csdn.net_weixin_41835916]: https://blog.csdn.net/weixin_41835916