HashMap知识点总结（附源码分析链接）

一、HashMap基础篇

1. 讲下对HashMap的认识
2. HashMap的初始化默认参数
3. HashMap的扩容机制
4. HashMap 在 JDK1.8 中扩容 resize( ) 方法扩容流程（和之前版本的区别）
5. HashMap为什么在JDK1.8为添加了红黑树的数据结构
6. 链表升级成红黑树的条件
7. 红黑树退化成链表的条件
8. 为什么Hashmap的长度必须是2的n次幂
9. HashMap获取的hash值的方法（HashMap可以存key为null的主键吗）
10. HashMap 为什么在获取 hash 值时要进行位运算
11. HaspMap的初始化时数组长度和加载因子的约束范围
12. JDK1.8之前HashMap采用头插法插入元素的隐患
13. HashMap 的 get 方法的流程分析
14. HashMap 的 put 方法的流程分析
15. HashMap 在扩容时为什么通过位运算 (e.hash & oldCap) 得到新数组下标

二、同类数据结构对比

1. HashMap和Hashtable的区别
2. HashMap的三种线程安全集合对比（Hashtable，ConcurrentHashMap，Collections.synchronizedMap() ）

未完待续…

HashMap基础篇

1、讲下对HashMap的认识

HashMap存储的是键值对 key - value，key具有唯一性，是哈希表数据结构在 Java 中的经典体现，采用了链地址法来处理哈希冲突。

1. HashMap底层的数据结构在 JDK1.8 中有了较大的变化，1.8之前采用数组加链表的数据结构，1.8采用数组加链表加红黑树的数据结构。 - HashMap为什么在JDK1.8为添加了红黑树的数据结构
2. 1.8之前采用头插法插入 key - value，1.8采用尾插法。 - JDK1.8之前HashMap采用头插法插入元素的隐患
3. HashMap 是线程不安全的，类似的线程安全的集合有 HashTable 和 ConcurrentHashMap 。 - HashMap 和 HashTable 的比较、 - HashMap 和 ConcurrentHashMap 之间的对比
4. 在 1.8 版本的中 resize( ) 方法也有了很大的改变，提升了扩容性能。 - HashMap 在 JDK1.8 中的扩容流程（源码分析）

2、HashMap的初始化默认参数

1. HashMap的加载因子默认是0.75，Node数组 (桶) 的初始长度为16。
2. 在 HashMap 初始化时可以设置初始长度和加载因子 - HaspMap的初始化时数组长度和加载因子的约束范围，但是数组长度必须满足 2 的 n 次幂（不满足也能初始化成功） - 为什么Hashmap的长度必须是2的n次幂。
3. 临界值 threshold = 加载因子 * 数组长度，默认初始的时候是 16 * 0.75 = 12。
4. 源码中的一些默认参数如下：

//HashMap的默认初始长度16
	static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; 
	
	//HashMap的最大长度2的30次幂
	static final int MAXIMUM_CAPACITY = 1 << 30;
	
	//HashMap的默认加载因子0.75
	static final float DEFAULT_LOAD_FACTOR = 0.75f;
	
	//HashMap链表升级成红黑树的临界值
	static final int TREEIFY_THRESHOLD = 8;
	
	//HashMap红黑树退化成链表的临界值
	static final int UNTREEIFY_THRESHOLD = 6;
	
	//HashMap链表升级成红黑树第二个条件：HashMap数组(桶)的长度大于等于64
	static final int MIN_TREEIFY_CAPACITY = 64;
	
	//HashMap底层Node桶的数组
	transient Node<K,V>[] table;
           

3、HashMap的扩容机制

 扩容的条件是:

1. HashMap元素的个数 size 大于阀值 (threshold) 时。
2. 在链表长度大于8时，且当前 Node 数组的长度小于64时 （取代生成红黑树）。

 每次扩容时 新阀值=旧阀值 << 1，数组新长度 = 旧长度 << 1，因此扩容后的容量是 length * 2，每次扩容一倍，也满足了数组长度是 2 的 n 次幂的条件。 - HashMap 在 JDK1.8 中的扩容流程（源码分析）

4、 HashMap 在 JDK1.8 中扩容 resize( ) 方法扩容流程（和之前版本的区别）

 1.8版本中扩容时会生成 low 和 high 两条链表或两个红黑树，把 low 链表插入到当前数组下标的位置，把 high 链表插入到 新数组中 [当前数组下标 + 旧数组长度] 的位置。元素是插入到 low 还是 high 中是依靠 hash & oldCap == 0 来判断，等于 0 插入 low，否则插入 high。依靠位运算大幅度提高了 resize( ) 的性能。

- HashMap 详细的扩容流程

- HashMap 在扩容时为什么通过位运算 (e.hash & oldCap) 得到新数组下标

5、HashMap为什么在JDK1.8为添加了红黑树的数据结构

 1.8之前采用的是数组加链表的数据结构。这时候可能出现一个Node结点的链表长度很长，如果插入查找删除操作的效率都会变慢，使性能变差，就算用头插法插入元素也需要把要插入的 key 和 链表中每个结点的 key 做一次equals( ) 方法，所以插入也会变慢。

 红黑树本身就是一个相对平衡的二叉树搜索树，他查找元素的时间复杂度和二叉搜索树类似，而且相对平衡不会出现二叉搜索树那样，在极端情况下退化成顺序查找的情况。插入删除和把链表升级成红黑树的操作相对复杂，在自平衡和查找上性能都很优秀，所以采用了红黑树的结构 (个人感觉就是均衡，平庸，不！相比B-Tree， B+Tree, 二叉搜索树，平衡二叉搜索树来说确实每项都很平均且优秀)。HashMap的红黑树的 parent 会指向父结点，所以是双向的。

6、链表升级成红黑树的条件

 链表长度大于8时才会升级成红黑树，隐含条件是 HashMap 的 Node 数组长度大于等于64（不满足则会进行一次扩容替代升级）。

- 相关源码分析

7、红黑树退化成链表的条件

1. 扩容 resize( ) 时，红黑树拆分成的 树的结点数小于等于临界值6个，则退化成链表。
2. 删除元素 remove( ) 时，在 removeTreeNode( ) 方法会检查红黑树是否满足退化条件，与结点数无关。如果红黑树根 root 为空，或者 root 的左子树/右子树为空，root.left.left 根的左子树的左子树为空，都会发生红黑树退化成链表。

- 相关源码分析

8、为什么Hashmap的长度必须是2的n次幂

 源码中获取 key 所对应 Node 数组下标的方法是 (length - 1) & hash，它与我们要求的 hash % length 在 数组长度是 2 的 n 次幂的条件下是等价的，而用这种 & 的位运算的方法相比直接用取余符号进行运算，可以减少性能的损耗。

 但是要明确一点，初始化时设置的长度不符合 2 的 n 次方也能正常初始化成功。

//获取 key 所对应 Node 数组下标 tab[index = (n - 1) & hash]
if ((e = tab[index = (n - 1) & hash]) != null) 
           

9、HashMap获取的Hash值的方法（HashMap可以存key为null的主键吗）

 首先判断 key 是否为 null，为 null 则返回 0 ，所以 key 为空的元素对应的数组坐标一定是 0，而且根据 put 会覆盖相同 key 的逻辑来思考，key 为空的元素最多只有一个。不为 null 则返回 key 的 hashCode异或上它的高16位。 - HashMap 获取 Hash 值时进行位运算的原因

static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
           

10、HashMap 为什么在获取 hash 值时要进行位运算

1. (h >>> 16)是无符号右移16位的运算，右边补0，得到 hashCode 的高16位
2. (h = key.hashCode()) ^ (h >>> 16) 把 hashCode 和它的高16位进行异或运算，可以使得到的 hash 值更加散列，极可能减少哈希冲突，提升性能。
3. 而这么来看 hashCode 被散列 (异或) 的是低16位。原因是获取 key 所对应数组下标的方式是 hash值 % 数组长度。比如 10001 % 101 取余的结果只会看前面二进制数的低三位，其余高位不影响取余结果。而 HashMap 数组长度一般不会超过2的16次幂，那么高16位在大多数情况是用不到的，所以只需要拿 key 的 HashCode 和它的低16位做异或即可让hash值更加散列。

11、HaspMap的初始化时数组长度和加载因子的约束范围

 我们可以看到如果初始化数组长度 initialCapacity 小于 0 的话会跑出 IllegalArgumentException 的异常，initialCapacity 大于 MAXIMUM_CAPACITY 即 2 的 30 次幂的时候最大长度也只会固定在 MAXIMUM_CAPACITY 。

 加载因子小于等于0时，或者加载因子是NaN时 (NaN 实际上就是 Not a Number的简称) 会抛出 IllegalArgumentException 的异常。

 总结: 加载因子 loadFactor > 0，不满足这个条件或者是 NaN 的时候会跑出异常。数组长度 MAXIMUM_CAPACITY > initialCapacity >= 0，当小于 0 时会跑出异常，大于最大值和等于0时不会，大于最大值时会把长度固定在 MAXIMUM_CAPACITY，而等于 0 时经过测试能正常初始化，put 和 get 操作均成功，说明会此时会在 put 前进行一次扩容。

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);
}
           

12、JDK1.8之前HashMap采用头插法插入元素的隐患

 可能会造成 HashMap 扩容 resize( ) 后的链表形成环状链表，陷入死循环，cpu空转短时间内cpu利用率飙升。单线程的情况下是不会出现该情况的，而在极端多线程的情况下可能会出现两个线程同时在做扩容 resize( ) ，cpu时间片分配给第一个线程做扩容时第二个线程已经拿到了链表上的两个值，那么第一个线程扩容完成恰好链表是逆序的 (链表的头插法是很常用的逆转链表的方法)， 第二个线程拿到的值就正好指向了相反的顺序，然后执行扩容就会使链表形成环路。

13、HashMap 的 get 方法的流程分析

 get方法首先根据 hash 方法获取到 key 的 hash 值，然后通过 hash & (length - 1) 的方式获取到 key 所对应的Node数组下标。首先判断此结点是否为空，是否就是要找的值，是则返回，否则进入第二个结点。判断第二个结点是否为空，是则返回空，否则判断此时结点的数据结构，是链表结构就进行遍历查找操作，红黑树结构执行相应的 getTreeNode( ) 查找操作。

- get方法流程的源码分析

14、HashMap 的 put 方法的流程分析

 首先根据 hash 方法获取到 key 的 hash 值，然后通过 hash & (length - 1) 的方式获取到 key 所对应的Node数组下标。看第一个元素是否存在，是否和结点的 key 和要插入元素的 key 相同，相同则覆盖 Value 的值。不是就继续走第二部判断数据结构是哪一种，是链表的话就直接进行遍历，如果发现 key 和某个结点的 key 相同则覆盖掉该结点的 value，遍历到最后直接插到链表尾部，也就是正常的尾插法，此时要注意链表长度是否超过临界值8升级成红黑树。红黑树的话执行红黑树的插入操作。

15、HashMap 在扩容 resize( ) 时为什么能直接通过位运算来得到新的数组下标

• 从下图中我们可以看出，hash % length 的结果只取决于小于数组长度的部分，这个 key 的 hash 值的低四位就是当前所在数组的下标。扩容后 新数组长度 = 旧数组长度 * 2，也就是左移 1 位，而此时 hash % length 的结果只取决于 hash 值的低五位，前后两者之间的差别就差在了第五位上。

  

• 如果第五位是 0，那么只要看低四位 (也就是当前下标)；如果第五位是 1，只要把二进制数 1 0 0 0 0 + 1 1 1 0 ，就可以得到新数组下标。前面的部分刚好等于 旧数组长度 ，后面的部分刚好是 当前的下标 。那么我们就得出来了为什么把 low 插入扩容后 新数组[当前坐标] 的位置，把 high 插入扩容后 新数组[当前坐标 + 旧数组长度] 的位置。
• 那为什么根据 (e.hash & oldCap) == 0 来做判断条件呢？是因为旧数组的长度 length 的二进制数的第五位刚好是 1，hash & length 就可以计算 hash 值的第五位是 0 还是 1。

同类数据结构对比

1、HashMap和Hashtable的区别

• 继承的父类不同。HashMap 继承了 AbstractMap，AbstractMap又实现了 Map 接口，Hashtable 继承了 Dictionary。
• 初始化数组长度，和扩容时的增量不同。HashMap 默认的初始数组长度是 16，默认的加载因子是 0.75，每次扩容变成之前数组的 2 倍长度。Hashtable 默认的初始数组长度是 11，默认的加载因子是 0.75，每次扩容是之前数组的 2 倍长度加 1。
• 是否允许存储空值不同。HashMap 允许value为空，只能有一个key为空。而Hashtable 的 key，value 都不允许为空。
• 获取Hash值和数组下标的方法不同。
• 底层数据结构不同。HashMap 在 JDK1.8 中底层数据结构变成了数组加链表加红黑树。Hashtable 底层采用数组加链表的结构。
• 扩容方法不同。
• 线程安全问题。HashMap 是线程不安全集合，而 Hashtable 是线程安全的。
• 性能存在差距。HashMap 性能强于 Hashtable。

- HashMap与Hashtable的八点区别（源码解析）

2、HashMap的三种线程安全集合对比（Hashtable，ConcurrentHashMap，Collections.synchronizedMap() ）

• Hashtable 和 Collections.synchronizedMap() 方法返回的 SynchronizedMap 都是通过锁住整个对象实例的方法确保线程安全的。
• ConcurrentHashMap 在不发生哈希冲突的情况下尽可能使用 CAS 确保线程安全，在发生哈希冲突情况下采用 synchronized 同步代码块方法锁住当前 Node 结点（只锁当前数组下标的 Node，其余结点不受影响）
• Hashtable 的数据结构是数组加链表
• ConcurrentHashMap在 jdk8 中和 HashMap 一样变成数组，链表加红黑树的结构。在哈希冲突比较激烈（链表长度大于8）会升级成红黑树的结构。
• Collections.synchronizedMap() 方法返回的 SynchronizedMap 底层数据结构根据传入的参数而定，如果传入一个 HashMap，那就和 HashMap 数据结构一致。
• 在考虑线程安全时应该使用 ConcurrentHashMap，不管是在锁的开销上（无哈希冲突用CAS，不然只锁底层数组中当前 Node 结点），还是哈希冲突严重时升级成红黑树都会在性能上更加占据优势。

- HashMap的三种线程安全集合对比（源码解析）