全面解析Java HashMap类

川长思鸟来 2022-04-04 05:18 263阅读 0赞

HashMap也是一个常用的Java集合框架类，它涉及大量的知识，包括数组、链表、红黑树等，以及一些高效而巧妙的计算，并且这个类已经被改进了几个版本，不同版本之间也有一些差异，这里都是基于JDK8的源代码。像通常的源代码翻译一样，看看能否回答以下问题？（有些地方真的很难翻译，看看就知道了。）

**问题 1：HashMap 中的 initCapacity、size、threshold、loadFactor、bin 的理解？**

HashMap 存放的是键值对，但并不是简单的一个萝卜一个坑。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NkMDkwNDQ5MDFndWlj_size_16_color_FFFFFF_t_70][]

1、在HashMap的参数构造函数中，我们指定init.，但是取大于或等于这个数目的2的幂作为表数组的初始容量。使用tableSizeFor(int)方法，如tableSizeFor(10)=16(2的4次幂)，tableSizeFor(20)=32(2的5次幂)，也就是说，表数组的长度总是2次幂。

2、Size记录保存在HashMap中的键值对的数量。

3、阈值用于存储当前容量中可以存储的密钥对的最大数量，或者HashMap扩展的临界值。当size>=.old时，HashMap将展开。Thres.=.（表数组的长度）\*loadFactor，但是当指定的initCapability没有密钥对时，阈值暂时等于容量值。

4、负载因子是负载因子。负载因子越小，阵列空间的浪费就越大。密钥对的分布越均匀，搜索速度就越快。反过来，负载因子越大，阵列空间的利用率越高，密钥对的分布越不均匀，搜索越慢。因此，应根据实际情况，在时间和空间上作出选择。

5、Bin在HashMap注释中多次出现，但是单词不容易翻译。存储在表数组的每个位置（可能多于一个）中的元素组成bin。阵列的每个位置可以被视为容器或桶，其中存储一个或多个元素。

因为HashMap只开辟了获取大小参数的途径，如果您想查看其他参数的值，一般的方法是不可行的，您可以使用反射来获取上述参数的值，编写代码来验证，我的测试代码。

**问题 2：HashMap 内部是怎么存放数据的？**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NkMDkwNDQ5MDFndWlj_size_16_color_FFFFFF_t_70 1][]

HashMap由数组+链表+红黑树实现。计算公式是index=(n-1)&hash(n是表数组的长度)。散列由键的hashCode和hash=key计算。hashCode^（键。hashCode>16)。Node保存键-值对的键和值以及计算的散列值，以及下一个Node的引用（如果没有下一个Node，next=null），它对应于数组位置的单向列表。当链表的长度超过树结构的阈值时，将链表转换为红黑树，以提高搜索速度。

**问题 3：HashMap 扩容的方法？**

当HashMap中的size>=.old时，将扩展HashMap。与ArrayList一样，HashMap也是一个动态增长的数组。HashMap扩展使用.ze()方法计算表数组的新容量和节点在新数组中的新位置，并将旧数组的值复制到新数组中，从而实现自动扩展。

1、当一个空的HashMap实例添加元素时，它用默认容量16扩展表数组的长度，当阈值=16\*0.75=12时。

2、当向空HashMap实例添加新元素的容量不足时，它将被扩展为旧容量的2倍。当然，扩张的规模也是有限的。扩容后的新容量应小于或等于规定的最大容量。通过使用新的容量创建新的表数组，然后复制数组元素Node。计算节点位置的方法是index=(n-1)&hash，这是计算节点位置的方法。计算的优点是节点在新数组中的位置没有改变，或者原始位置加上旧数组的容量值。新数组中的位置是可预测的（规则的），并且列表上的Node的顺序不会改变（JDK7中的HashMap方法将改变Node的顺序）。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NkMDkwNDQ5MDFndWlj_size_16_color_FFFFFF_t_70 2][]

**问题 4：HashMap put 方法详解？**

put 方法内部调用的是 putVal() 方法，所以对 put 方法的分析也是对 putVal 方法的分析，整个过程比较复杂，流程图如下：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NkMDkwNDQ5MDFndWlj_size_16_color_FFFFFF_t_70 3][]

1、确定数组表的键值是空还是空，以及是否调用.ze()方法展开它

2、如果表\[index\]==null，则表明此位置没有节点。新节点直接添加到此位置并转到7。如果表\[index\]不是空的，则转到3。

3、 如果表\[index\]的第一个节点直接覆盖值，则确定该节点是否与key相同，否则转到4，其中相同的节点引用key。hashCode和equals键方法。

4、 所选的表\[index\]是树节点，是表\[index\]的位置是红树，是红黑树，是红黑树，是目录中的树中的键值，并返回到5；

5、 遍历表\[索引\]以确定链接列表的长度是否大于8，如果大于8，则将链接列表转换为红黑树，并在红黑树中执行插入操作，否则执行链接列表的插入操作；

6、在遍历过程中，如果发现键直接覆盖该值，则可以进行遍历。

7、 在成功插入之后，确定大小键的实际数量是否超过最大容量阈值，如果超过，则展开大小。

**问题 5：HashMap 数组的长度为什么是2的次幂？**

其主要原因是便于计算节点在阵列中的位置索引，提高计算速度。理想情况下，HashMap中的表数组只存储一个节点，即不存在哈希冲突，因此访问效率最高。但事实上，碰撞是很难避免的。我们需要做的是在表数组中尽可能均匀地分布数据。传统的方法是使用散列%.=index来计算节点在数组中的位置。这个公式可以用index=hash-（hash/.）\*length代替，但是这个计算更加复杂。我们用十进制来计算节点的位置。计算机使用二进制系统。2的幂用二进制表示。例如(16)10=10000)2.更巧妙的是，当.=2的幂时，hash%.=hash&(.-1)。位操作在计算机中非常有效。这里.-1也是非常规则的，如(15)10=0111)2、任何散列值和0111。对结果进行位运算的范围是00000-01111（0-15），这正是数组的索引。当HashMap展开时，表数组是原来的两倍长，或者是2的幂，所以它总是可以非常快速地计算数组中Node的位置索引。

**问题 6：几种 Map 集合类的对比？**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NkMDkwNDQ5MDFndWlj_size_16_color_FFFFFF_t_70 4][]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NkMDkwNDQ5MDFndWlj_size_16_color_FFFFFF_t_70]: /images/20220404/1a1d4bf094da489899350966e2631523.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NkMDkwNDQ5MDFndWlj_size_16_color_FFFFFF_t_70 1]: /images/20220404/add19dbf8789461b8baf8c507cc1e02a.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NkMDkwNDQ5MDFndWlj_size_16_color_FFFFFF_t_70 2]: /images/20220404/440dd4c0c14d4cc99ed04420b78b9cc1.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NkMDkwNDQ5MDFndWlj_size_16_color_FFFFFF_t_70 3]: /images/20220404/30cd4ebdf3a04ffa8fea7cb384d617cb.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NkMDkwNDQ5MDFndWlj_size_16_color_FFFFFF_t_70 4]: /images/20220404/d451b5968f824c97bb65eab263a47bc3.png