HashMap集合超详解(上)

1、HashMap简介

• HashMap 基于哈希表的 Map 接口实现，是以 key-value 存储形式存在，即主要用来存放键值对。HashMap 的实现不是同步的，这意味着它不是线程安全的。它的 key、value 都可以为 null，此外，HashMap 中的映射不是有序的。

底层数据结构

1. jdk1.8 之前 HashMap 由 数组 + 链表 组成，数组是 HashMap 的主体，链表则是主要为了解决哈希冲突（两个对象调用的 hashCode 方法计算的哈希值经哈希函数算出来的地址被别的元素占用）而存在的（“拉链法” 解决冲突）。
2. jdk1.8 以后在解决哈希冲突时有了较大的变化，当链表长度大于阈值（或者红黑树的边界值，默认为 8 ）并且当前数组的长度大于 64 时，此时此索引位置上的所有数据改为使用 红黑树 存储。

⭐注意⭐

• 将链表转换成红黑树前会判断，即便阈值大于 8，但是数组长度小于 64，此时并不会将链表变为红黑树，而是选择逬行数组扩容。
• 这样做的目的是因为数组比较小，尽量避开红黑树结构，这种情况下变为红黑树结构，反而会降低效率，因为红黑树需要逬行左旋，右旋，变色这些操作来保持平衡。同时数组长度小于64时，搜索时间相对要快些。所以结上所述为了提高性能和减少搜索时间，底层阈值大于8并且数组长度大于64时，链表才转换为红黑树，具体可以参考 treeifyBin() 方法。
• 当然虽然增了红黑树作为底层数据结构，结构变得复杂了，但是 阈值大于 8 并且数组长度大于 64 时，链表转换为红黑树 时，效率也变的更高效。

🚀小结🚀

• HashMap的特点

1. 存储无序的。
2. 键和值位置都可以是 null，但是键位置只能存在一个 null。
3. 键位置是唯一的，是底层的数据结构控制的。
4. jdk1.8 前数据结构是链表+数组，jdk1.8 之后是链表+数组+红黑树。
5. 阈值（边界值）> 8 并且数组长度大于 64，才将链表转换为红黑树，变为红黑树的目的是为了高效的查询。

2、HashMap存储数据的过程

• 示例代码：

import java.util.*;

public class Test {
    public static void main(String[] args) {
        HashMap<String,Integer> hm = new HashMap<>();
        hm.put("aa",10);
        hm.put("bb",20);
        hm.put("cc",30);
        hm.put("aa",15);
        System.out.println(hm);
    }
}

• 输出结果：

{aa=15, bb=20, cc=30}

• 存储数据过程分析

1. HashMap<String,Integer> hm = new HashMap<>(); 当创建 HashMap集合对象的时候，在jdk8之前的话，构造方法中会创建一个长度是 16 的 Entry[] table 用来存储键值对数据。在jdk8之后不是在 HashMap 的构造方法底层创建数组，而是在第一次调用的 put 的时候创建的数组，Node[] table 用来存储键值对数据。
2. 假设向哈希表中存储 <aa,10> 数据，根据柳岩调用 String 类中重写之后的 hashCode() 方法计算出值，然后结合数组长度采用某种算法计算出向 Node 数组中存储数据的空间的索引值。如果计算出的索引空间没有数据，则直接将 <aa,10> 存储到数组中。（举例：计算出的索引是 3 ）。

此时举例中 HashMap 中存储情况如下：

1. 向哈希表中存储数据 <bb，20>，假设算出的 hashCode() 方法结合数祖长度计算出的索引值也是3，那么此时数组空间不是 null，此时底层会比较 aa 和 bb 的 hash 值是否一致，如果不一致，则在空间上划出一个结点来存储键值对数据对 <bb,40>，这种方式称为拉链法。

1. 假设向哈希表中存储数据 <aa，15>，那么首先根据 aa 调用 hashCode() 方法结合数组长度计算出索引肯定是 3，此时比较后存储的数据 aa 和已经存在的数据的 hash 值是否相等，如果 hash 值相等，此时发生哈希碰撞。那么底层会调用 aa 所属类 String 中的 equals() 方法比较两个内容是否相等：

相等：将后添加的数据的 value 覆盖之前的 value。

不相等：继续向下和其他的数据的 key 进行比较，如果都不相等，则划出一个结点存储数据，如果结点长度即链表长度大于阈值 8 并且数组长度大于 64 则将链表变为红黑树。

1. 在不断的添加数据的过程中，会涉及到扩容问题，当超出阈值（且要存放的位置非空）时，扩容。默认的扩容方式：扩容为原来容量的 2 倍，并将原有的数据复制过来。
2. 综上描述，当位于一个表中的元素较多，即 hash 值相等但是内容不相等的元素较多 时，通过 key 值依次查找的效率较低。而 jdk1.8 中，哈希表存储采用 数组+链表+红黑树 实现，当链表长度（阈值）超过8且当前数组的长度大于64时，将链表转换为红黑树，这样大大减少了查找时间。

简单的来说，哈希表是由数组+链表+红黑树（JDK1.8增加了红黑树部分）实现的。如下图所示：

1. 引入红黑树的原因：

   • jdk1.8 以前 HashMap 的实现是数组+链表，即使哈希函数取得再好，也很难达到元素百分百均匀分布。当 HashMap 中有大量的元素都存放到同一个桶中时，这个桶下有一条长长的链表，这个时候 HashMap 就相当于一个单链表，假如单链表有n个元素，遍历的时间复杂度就是O(n)，完全失去了它的优势。
   • 针对这种情况，jdk1.8 中引入了红黑树（查找时间复杂度为 O(logn)）来优化这个问题。当链表长度很小的时候，即使遍历，速度也非常快，但是当链表长度不断变长，肯定会对查询性能有一定的影响，所以才需要转成树。
2. HashMap的put方法总结

说明

• size 表示 HashMap 中键值对的实时数量，注意这个不等于数组的长度。
• threshold（临界值）= capacity（容量）* loadFactor（负载因子）。这个值是当前已占用数组长度的最大值。size 超过这个值就重新 resize（扩容），扩容后的 HashMap 容量是之前容量的 两倍。

3、HashMap存储数据过程的常见面试题

1. HashMap 中 hash 函数是怎么实现的？还有哪些hash函数的实现方式？

答：对于 key 的 hashCode 做 hash 操作，无符号右移 16 位 （>>>） 然后做异或 （^） 运算。还有平方取中法，伪随机数法和取余数法。这三种效率都比较低。而无符号右移 16 位异或运算效率是最高的。

1. 当两个对象的 hashCode 相等时会怎么样？

答：会产生哈希碰撞。若 key 值内容相同则替换旧的 value，不然连接到链表后面，如果链表长度超过阈值 8并且数组长度大于64 就转换为红黑树存储。

1. 什么是哈希碰撞，如何解决哈希碰撞？

答：只要两个元素的 key 计算的哈希码值相同就会发生哈希碰撞。jdk8 之前使用链表解决哈希碰撞。jdk8之后使用链表 + 红黑树解决哈希碰撞。

1. 如果两个键的 hashCode 相同，如何存储键值对？

答：通过 equals 比较内容是否相同。

• 相同：则新的 value 覆盖之前的 value。
• 不相同：则将新的键值对添加到哈希表中，如果加入之后满足 链表长度超过阈值 8并且数组长度大于64 就需要转换为红黑树存储，否则就是在链表尾部进行添加。

4、HashMap的继承关系

• HashMap的继承关系图如下图所示：

说明：

1. HashMap实现了Cloneable 接口，表示可以被克隆。
2. HashMap实现了Serializable 序列化接口。属于标记性接口。HashMap 对象可以被序列化和反序列化。
3. HashMap实现了AbstractMap 父类提供了 Map 实现接口。以最大限度地减少实现此接口所需的工作。

补充说明：

通过上述继承关系我们可以发现一个很奇怪的现象就是： HashMap 已经继承了AbstractMap 而 AbstractMap 类实现了Map 接口，那
为什么 HashMap 还要在实现 Map 接口呢？同样在 ArrayList 中 LinkedLis 中都是这种结构。

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

5、HashMap的成员变量

1. serialVersionUID

序列化版本号

private static final long serialVersionUID = 362498820763181265L;

1. DEFAULT_INITIAL_CAPACITY

集合的初始化容量（必须是 2 的 n 次幂）

// 默认的初始容量是16    1 << 4 相当于 1*2的4次方
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;

高频面试问题：为什么必须是 2 的 n 次幂？如果输入值不是 2 的幂比如 10 会怎么样?

我们可以通过HashMap 构造方法指定HashMap集合的初始化容量大小，如下：

// 构造一个带指定初始容量和默认负载因子（0.75)的空 HashMap。
HashMap(int initialCapacity)

根据上述讲解我们已经知道，当向 HashMap 中添加一个元素的时候，需要根据 key 的 hash 值，去确定其在数组中的具体位置。HashMap 为了存取高效，减少碰撞，就是要尽量把数据分配均匀，每个链表长度大致相同，这个实现的关键就在把数据存到哪个链表中的算法。

这个算法实际就是取模，hash % length，计算机中直接求余效率不如位移运算。所以源码中做了优化，使用 hash & ( length - 1) ，而实际上 hash % length 等于 hash & ( length - 1) 的前提是 length 是 2 的 n 次幂。

例如长度为 8 的时候，3 & (8 - 1) = 3，2 & (8 - 1) = 2，不同位置上，不碰撞。

如果是 2 的 n 次幂的话

3 & （8 - 1） = 3
    00000011
&     00000111
--------------
    00000011 (3)
    
2 & (8 - 1)  = 2
    00000010
&     00000111
--------------
    00000010 (2)
    
如果不是 2 的 n 次幂的话，计算出来的索引极其容易相同，从而极其容易产生hash碰撞，导致数组的空间利用率降低
此处我们假设数组长度为 9

3 & （9 - 1） = 0
    00000011
&     00001000
--------------
    00000000 (0)

2 & （9 - 1） = 0
    00000010
&     00001000
--------------
    00000000 (0)

从上述例子可以看出，当数组长度为9(非2 的n次幂)的时候，不同的哈希值hash， hash & (length - 1) 所得到的数组下标相等(很容易出现哈希碰撞)。

总结一下HashMap数组容量使用 2 的 n 次幂的原因：

1. 由上面可以看出，当我们根据 key 的 hash 确定其在数组的位置时，如果数组长度为 2 的 n 次幂，可以保证数据的均匀插入，如果数组长度不是 2 的 n 次幂，可能数组的一些位置永远不会插入数据，浪费数组的空间，hash 冲突的概率增大。
2. 另一方面，一般我们可能会想通过 % 求余数来确定位置，这样也可以，只不过性能不如 & 运算。而且当数组长度是 2 的 n 次幂时：hash % length == hash & ( length - 1)。
3. 因此，HashMap容量为 2 的 n 次幂的原因就是为了数据的均匀分布，减少 hash 冲突，毕竟 hash 冲突越大，代表数组中一个链表的长度越大，这样的话会降低 hashMap 的性能。

那当我们输入的 initialCapacity 不是 2 的 n 次幂的话，那么HashMap会通过 tableSizeFor 方法找到大于等于 initialCapacity 的最小的 2 的幂。

/**
* Returns a power of two size for the given target capacity.
*/
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）、int n = cap - 1;为什么要减去1呢？

防止 cap 已经是 2 的 n 次幂。如果 cap 已经是 2 的n 次幂，又没有这个减 1 操作，则执行完后面的几条无符号操作之后，返回的 capacity 将是这个 cap 的 2 倍(后面还会再举个例子讲这个)。

（2）、最后为什么有个 n + 1 的操作呢？

如果 n 这时为 0 了（经过了cap - 1后），则经过后面的几次无符号右移依然是 0，返回0是肯定不行的，所以最后返回n+1最终得到的 capacity 是1。

（3）、注意

容量最大也就是 32bit 的正数，因此最后 n |= n >>> 16;最多也就 32 个 1（但是这已经是负数了，在执行 tableSizeFor 之前，对 initialCapacity 做了判断，如果大于MAXIMUM_CAPACITY(2 ^ 30)，则取 MAXIMUM_CAPACITY。如果等于MAXIMUM_CAPACITY，会执行位移操作。所以这里面的位移操作之后，最大 30 个 1，不会大于等于 MAXIMUM_CAPACITY。30 个 1，加 1 后得 2 ^ 30）。

• 完整例子：

// 获取到新的容量值之后这个 capacity 却被赋值给了 threshold
this.threshold = tableSizeFor(initialCapacity);

1. DEFAULT_LOAD_FACTOR

默认的负载因子（默认值 0.75）

// 该负载因子和当前数组的容量相乘就是数组扩容的阈值
static final float DEFAULT_LOAD_FACTOR = 0.75f;

1. MAXIMUM_CAPACITY

集合最大容量

static final int MAXIMUM_CAPACITY = 1 << 30; // 2的30次幂

1. TREEIFY_THRESHOLD

当链表的值超过8 （数组容量大于64） 则会转为红黑树（jdk1.8新增）

// 当桶（bucket）上的结点数大于这个值时会转为红黑树
static final int TREEIFY_THRESHOLD = 8;

问题：为什么 Map 桶中结点个数超过 8 才转为红黑树？

8这个阈值定义在HashMap中，针对这个成员变量，在源码的注释中只说明了 8 是 bin（bin就是 bucket 桶）从链表转成树的阈值，但是并没有说明为什么是 8。

在 HashMap 中有一段注释说明：

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:

翻译：因为树结点的大小大约是普通结点的两倍，所以我们只在箱子包含足够的结点时才使用树结点(参见TREEIFY_THRESHOLD)。
当它们变得太小（由于删除或调整大小）时，就会被转换回普通的桶。在使用分布良好的用户 hashCode 时，很少使用树箱。
理想情况下，在随机哈希码下，箱子中结点的频率服从泊松分布
(http://en.wikipedia.org/wiki/Poisson_distribution) ，默认调整阈值为0.75，平均参数约为0.5，尽管由 
于调整粒度的差异很大。忽略方差，列表大小k的预朗出现次数是(exp(-0.5) * pow(0.5, k) / factorial(k))。 
第一个值是：

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

TreeNodes 占用空间是普通 Nodes 的两倍，所以只有当 bin 包含足够多的结点时才会转成 TreeNodes，而是否足够多就是由 TREEIFY_THRESHOLD 的值决定的。当 bin 中结点数变少时，又会转成普通的 bin。并且我们查看源码的时候发现，链表长度达到 8 就转成红黑树，当长度降到 6 就转成普通 bin。

这样就解释了为什么不是一开始就将其转换为 TreeNodes，而是需要一定结点数才转为 TreeNodes，说白了就是权衡空间和时间。

面试答案：hashCode 算法下所有 桶 中链表结点的分布频率会遵循泊松分布，这时一个桶中链表长度超过 8 个元素的槪率非常小，权衡空间和时间复杂度，所以选择 8 这个数宇。

1. UNTREEIFY_THRESHOLD

// 当链表的值小于 6 则会从红黑树转回链表
// 当桶（bucket）上的结点数小于这个值，树转为链表 
static final int UNTREEIFY_THRESHOLD = 6;

1. MIN_TREEIFY_CAPACITY

当 Map 里面的数量超过这个值时，表中的桶才能进行树形化，否则桶内元素太多时会扩容，而不是树形化为了避免进行扩容、树形化选择的冲突，这个值不能小于 4*TREEIFY_THRESHOLD(8)

// 桶中结构转化为红黑树对应的数组长度最小的值 
static final int MIN_TREEIFY_CAPACITY = 64;

1. table

table 用来初始化（必须是二的n次幂）(重点)

// 存储元素的数组 
transient Node<K,V>[] table;

在 jdk1.8 中我们了解到 HashMap 是由数组加链表加红黑树来组成的结构，其中 table 就是 HashMap 中的数组，jdk8 之前数组类型是 Entry<K,V> 类型。从 jdk1.8 之后是 Node<K,V> 类型。只是换了个名字，都实现了一样的接口：Map.Entry<K,V>。负责存储键值对数据的。

1. entrySet

   用来存放缓存

// 存放具体元素的集合
transient Set<Map.Entry<K,V>> entrySet;

1. size

HashMap 中实际存放元素的个数(重点)

// 存放元素的个数，注意这个不等于数组的长度
 transient int size;

size 为 HashMap 中 K-V 的实时数量，不是数组 table 的长度。

1. modCount

用来记录 HashMap 的修改次数

// 每次扩容和更改 map 结构的计数器
 transient int modCount;  

1. threshold

用来调整大小下一个容量的值计算方式为（容量*负载因子）

// 临界值 当实际大小（容量*负载因子）超过临界值时，会进行扩容
int threshold;

1. loadFactor

哈希表的负载因子(重点)

// 负载因子
final float loadFactor;

说明

• loadFactor 是用来衡量 HashMap 满的程度，表示HashMap的疏密程度，影响 hash 操作到同一个数组位置的概率，计算 HashMap 的实时负载因子的方法为：size/capacity，而不是占用桶的数量去除以 capacity。capacity 是桶的数量，也就是 table 的长度 length。
• loadFactor 太大导致查找元素效率低，太小导致数组的利用率低，存放的数据会很分散。loadFactor 的默认值为 0.75f 是官方给出的一个比较好的临界值。
• 当 HashMap 里面容纳的元素已经达到 HashMap 数组长度的 75% 时，表示 HashMap 太挤了，需要扩容，而扩容这个过程涉及到 rehash、复制数据等操作，非常消耗性能。所以开发中尽量减少扩容的次数，可以通过创建 HashMap 集合对象时指定初始容量来尽量避免。
• 在 HashMap 的构造器中可以定制 loadFactor。

// 构造方法，构造一个带指定初始容量和负载因子的空HashMap
HashMap(int initialCapacity, float loadFactor);

• 为什么负载因子设置为0.75，初始化临界值是12？

loadFactor 越趋近于1，那么 数组中存放的数据(entry)也就越多，也就越密，也就是会让链表的长度增加，导致链表长度可能超过阈值，从而使得查找效率降低；loadFactor 越小，也就是趋近于0，数组中存放的数据(entry)也就越少，也就越稀疏，可能导致数组空间大量空闲而使得数组空间浪费。

所以既兼顾数组利用率又考虑链表不要太多，经过大量测试 0.75 是最佳方案。

• threshold 计算公式：capacity(数组长度默认16) * loadFactor(负载因子默认0.75)。

这个值是当前已占用数组长度的最大值。当 Size >= threshold 的时候，那么就要考虑对数组的 resize(扩容)，也就是说，这个的意思就是 衡量数组是否需要扩增的一个标准。 扩容后的 HashMap 容量是之前容量的两倍。