10分钟拿下 HashMap

深藏阁楼爱情的钟 2022-12-24 13:55 193阅读 0赞

> **请相信我，你一定会更优秀！**

备注：jdk版本为 1.7，初识 HashMap（后续会继续带你拿下 1.8+的HashMap）

**目录**

[1、什么是 HashMap，什么时候选择 HashMap？][1_ HashMap_HashMap]

[2、HashMap 数据结构及其工作原理？][2_HashMap]

[2.1 数据结构][2.1]

[2.2 工作原理][2.2]

[3、HashMap和HashTable 的异同？][3_HashMap_HashTable]

[4、如何优化 HashMap？][4_ HashMap]

--------------------

## 1、什么是 HashMap，什么时候选择 HashMap？ ##

说到容器，你肯定会想到 Java中对象存储容器还有ArrayList，LinkedList，HashSet等，HashMap 相对这些容器来说，可以理解为多了一层指向关系，可以用指定Key找到指定Value。

**打个比方**：

现在有一个Java Bean 用于存储职员的信息，字段包括（职员姓名，职员年龄，职员身高，职员体重，职员教育程度 ... 等等），我是一名人力资源管理，我需要将员工信息整理好发给老板。

**图示：**

![70][]

★ **问题：**

这个时候你必须要想到，如果两个人名字一样可咋办，查到的到底是谁的信息呢？前者信息会被覆盖吗？带着问题来学习一下HashMap数据结构及其工作原理。

## 2、HashMap 数据结构及其工作原理？ ##

### 2.1 数据结构 ###

**HashMap 数据结构为 数组+链表，其中：链表的节点存储的是一个 Entry 对象，每个Entry 对象存储四个属性（hash，key，value，next）**

**一张图带你看懂：**

![by zhanghaolin][]

**三句话，说清它的数据结构：**

1.  整体是一个数组；
2.  数组每个位置是一个链表；
3.  链表每个节点中的Value即我们存储的Object；

### 2.2 工作原理 ###

首先，初始化 HashMap，提供了有参构造和无参构造，无参构造中，容器默认的数组大小** **initialCapacity 为 16，加载因子loadFactor 为0.75。容器的阈(yu)值为 initialCapacity \* loadFactor，默认情况下阈值为 16 \* 0.75 = 12; 后面会讲到阈值有啥用。

然后，这里我们拿 **PUT**** **方法来做研究：

**第一步：**通过 HashMap 自己提供的hash 算法算出当前 key 的hash 值

**第二步：**通过计算出的hash 值去调用 indexFor 方法计算当前对象应该存储在数组的几号位置

**第三步：**判断size 是否已经达到了当前阈值，如果没有，继续；如果已经达到阈值，则先进行数组扩容，将数组长度扩容为原来的2倍。

**> 请注意**：size 是当前容器中已有 Entry 的数量，不是数组长度。

**第四步：**将当前对应的 hash，key，value封装成一个 Entry，去数组中查找当前位置有没有元素，如果没有，放在这个位置上；如果此位置上已经存在链表，那么遍历链表，如果链表上某个节点的 key 与当前key 进行 equals 比较后结果为 true，则把原来节点上的value 返回，将当前新的 value替换掉原来的value，如果遍历完链表，没有找到key 与当前 key equals为 true的，就把刚才封装的新的 Entry中next 指向当前链表的始节点，也就是说当前节点现在在链表的第一个位置，简单来说即，先来的往后退**。**

**OK！**现在，我们已经将当前的 key-value 存储到了容器中。

为什么我选择聊 **PUT **方法？

因为 **PUT** 是操作HashMap的最基础操作，了解了** PUT **的机制后，再去看 API其他方法源码的时候你会有所眉目，你可以带着这种初知去探究 HashMap 的其他方法，你一定会豁然开朗。

**扩容机制：**

HashMap 使用 “懒扩容” ，只会在 **PUT** 的时候才进行判断，然后进行扩容。

1.  将数组长度扩容为原来的2 倍
2.  将原来数组中的元素进行重新放到新数组中

需要注意的是，每次扩容之后，都要重新计算原来的 Entry 在新数组中的位置，为什么数组扩容了，Entry 在数组中的位置发生变化了呢？所以我们会想到计算位置的 indexFor 方法，为什么呢，我摘出了该方法的源码如下：

1.  `static int indexFor(int h, int length) { // h 为key 的 hash值；length 是数组长度`
2.  `return h & (length-1);`
3.  `}`

由源码得知，元素所在位置是和数组长度是有关系的，既然扩容后数组长度发生了变化，那么元素位置肯定是要发生变化了。HashMap 计算元素位置采用的是 &运算，不了解此运算的我在这里给个简单的例子：

**高能：为什么 HashMap使用这种方式计算在数组中位置呢？**

按照我们的潜意识，取模就可以了。hashMap 用与运算主要是提升计算性能。这又带来一个新问题，为什么与运算要用 length -1 呢，回看 hashmap初始化的时候，数组长度 length必须是2的整次幂（如果手动传参数组长度为奇数n，hashMap会自动转换长度为距离n最近的2的整次幂数），**只有这样， h & (length-1) 的值才会和 h % length 计算的结果是一样的。这就是它的原因所在。另外，当length是2的整次幂的时候，length-1的结果都是低位全部是1，为后面的扩容做了很好的准备，这里先不扯这个，先理解一下这个意思。**

我们来写个单元测试验证下：

1.  `public static void main(String[] args) {`
2.   
3.  `/**`
4.  `* 定义数组长度为2的整次幂，2^4`
5.  `*/`
6.  `int length = 16;`
7.   
8.  `/**`
9.  `* 定义key，并计算k的hash值`
10. `*/`
11. `String k = "China";`
12. `int h = k.hashCode();`
13.  
14. `/**`
15. `* 分别使用两种方式计算在数组中的位置`
16. `*/`
17. `int index1 = h % length;`
18. `int index2 = h & (length - 1);`
19.  
20. `/**`
21. `* 验证结果`
22. `*/`
23. `System.out.println(index1 == index2);`
24.  
25. `/**`
26. `* 结果为 true`
27. `*/`
28. `}`

1.  `public static void main(String[] args) {`
2.   
3.  `/**`
4.  `* 假设数组长度不是2的整次幂，2^4-1`
5.  `*/`
6.  `int length = 15;`
7.   
8.  `/**`
9.  `* 定义key，并计算k的hash值`
10. `*/`
11. `String k = "China";`
12. `int h = k.hashCode();`
13.  
14. `/**`
15. `* 分别使用两种方式计算在数组中的位置`
16. `*/`
17. `int index1 = h % length;`
18. `int index2 = h & (length - 1);`
19.  
20. `/**`
21. `* 验证结果`
22. `*/`
23. `System.out.println(index1 == index2);`
24.  
25. `/**`
26. `* 打印结果：false`
27. `*/`
28.  
29. `}`

**捡知识：**

计算 8 & 6 = 0的过程如下：

1.  `1 0 0 0 // 8的二进制数`
2.  `& 0 1 1 0 // 6的二进制数`
3.  `___________ // 运算规则：该位置上有一个是0 结果就是0`
4.  `0 0 0 0 // 二进制数计算结果`

**还记得我们(1)中提到的问题了吗？知道答案了吗？**

答：HashMap 中equals 相同的两个key， 容器中只会保留后进来的key 的value。进入问题中即：我先存储了 Lucy的信息，后来又有一个 Lucy，这个时候再存储 Lucy，容器中保留的是第二个 Lucy 的信息，这种情况，我们可以考虑使用 List<T> 作为 value，把相同名字的职员信息存在 list 中；或者给相同名字的职员编号，使得每个key 都是唯一的。

## 3、**HashMap和HashTable 的异同？** ##

1.  二者的存储结构和解决冲突的方法都是**相同**的。
2.  HashTable在不指定容量的情况下的默认容量为**11**，而HashMap为**16**，Hashtable不要求底层数组的容量一定要为2的整数次幂，而HashMap则要求一定为2的整数次幂。
3.  HashTable 中 key和 value**都不允许**为 null，而HashMap中key和value**都允许**为 null（key只能有一个为null，而value则可以有多个为 null）。但是如果在 Hashtable中有类似 put( null, null)的操作，编译同样可以通过，因为 key和 value都是Object类型，但运行时会抛出 NullPointerException异常。
4.  Hashtable扩容时，将容量变为原来的**2倍+1**，而HashMap扩容时，将容量变为原来的**2倍**。
5.  Hashtable计算hash值，直接用key的hashCode()，而HashMap重新计算了key的hash值，Hashtable在计算hash值对应的位置索引时，用 **%**运算，而 HashMap在求位置索引时，则用 **&**运算。

## 4、如何优化 HashMap？ ##

初始化 HashMap 的时候，我们可以自定义**数组容量**及**加载因子**的大小。所以，优化 HashMap 从这两个属性入手，但是，如果你不能准确的判别你的业务所需的大小，请使用默认值，否则，一旦手动配置的不合适，效果将适得其反。

**threshold = (int)( capacity \* loadFactor );**

**阈值 = 容量 X 负载因子**；

初始容量默认为16,负载因子(loadFactor)默认是0.75; map扩容后，要重新计算阈值；当元素个数 大于新的阈值时，map再自动扩容；以默认值为例，阈值=16\*0.75=12，当元素个数大于12时就要扩容；那剩下的4个数组位置还没有放置对象就要扩容，造成空间浪费，所以要进行时间和空间的折中考虑；

loadFactor**过大**时，map内的数组使用率高了，内部极有可能形成Entry链，影响查找速度；

loadFactor**过小**时，map内的数组使用率较低，不过内部不会生成Entry链，或者生成的Entry链很短，由此提高了查找速度，不过会占用更多的内存；所以可以根据实际硬件环境和程序的运行状态来调节loadFactor；

**所以，务必合理的初始化 HashMap**

>  **努力改变自己和身边人的生活。**

特别希望本文可以对您有所帮助，转载请注明出处。感谢大家留言讨论交流。

[1_ HashMap_HashMap]: https://blog.csdn.net/weixin_35586546/article/details/81153793?ops_request_misc=%257B%2522request%255Fid%2522%253A%2522160655940819725271029059%2522%252C%2522scm%2522%253A%252220140713.130102334..%2522%257D&request_id=160655940819725271029059&biz_id=0&utm_medium=distribute.pc_search_result.none-task-blog-2~all~top_click~default-1-81153793.pc_first_rank_v2_rank_v28&utm_term=hashmap&spm=1018.2118.3001.4449#1%E3%80%81%E4%BB%80%E4%B9%88%E6%98%AF%20HashMap%EF%BC%9F
[2_HashMap]: https://blog.csdn.net/weixin_35586546/article/details/81153793?ops_request_misc=%257B%2522request%255Fid%2522%253A%2522160655940819725271029059%2522%252C%2522scm%2522%253A%252220140713.130102334..%2522%257D&request_id=160655940819725271029059&biz_id=0&utm_medium=distribute.pc_search_result.none-task-blog-2~all~top_click~default-1-81153793.pc_first_rank_v2_rank_v28&utm_term=hashmap&spm=1018.2118.3001.4449#2%E3%80%81HashMap%20%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E5%8F%8A%E5%85%B6%E5%B7%A5%E4%BD%9C%E5%8E%9F%E7%90%86%EF%BC%9F
[2.1]: https://blog.csdn.net/weixin_35586546/article/details/81153793?ops_request_misc=%257B%2522request%255Fid%2522%253A%2522160655940819725271029059%2522%252C%2522scm%2522%253A%252220140713.130102334..%2522%257D&request_id=160655940819725271029059&biz_id=0&utm_medium=distribute.pc_search_result.none-task-blog-2~all~top_click~default-1-81153793.pc_first_rank_v2_rank_v28&utm_term=hashmap&spm=1018.2118.3001.4449#2.1%20%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84
[2.2]: https://blog.csdn.net/weixin_35586546/article/details/81153793?ops_request_misc=%257B%2522request%255Fid%2522%253A%2522160655940819725271029059%2522%252C%2522scm%2522%253A%252220140713.130102334..%2522%257D&request_id=160655940819725271029059&biz_id=0&utm_medium=distribute.pc_search_result.none-task-blog-2~all~top_click~default-1-81153793.pc_first_rank_v2_rank_v28&utm_term=hashmap&spm=1018.2118.3001.4449#2.2%20%E5%B7%A5%E4%BD%9C%E5%8E%9F%E7%90%86
[3_HashMap_HashTable]: https://blog.csdn.net/weixin_35586546/article/details/81153793?ops_request_misc=%257B%2522request%255Fid%2522%253A%2522160655940819725271029059%2522%252C%2522scm%2522%253A%252220140713.130102334..%2522%257D&request_id=160655940819725271029059&biz_id=0&utm_medium=distribute.pc_search_result.none-task-blog-2~all~top_click~default-1-81153793.pc_first_rank_v2_rank_v28&utm_term=hashmap&spm=1018.2118.3001.4449#3%E3%80%81%E4%B8%BA%E4%BB%80%E4%B9%88%E9%80%89%E6%8B%A9%20HashMap%EF%BC%9F
[4_ HashMap]: https://blog.csdn.net/weixin_35586546/article/details/81153793?ops_request_misc=%257B%2522request%255Fid%2522%253A%2522160655940819725271029059%2522%252C%2522scm%2522%253A%252220140713.130102334..%2522%257D&request_id=160655940819725271029059&biz_id=0&utm_medium=distribute.pc_search_result.none-task-blog-2~all~top_click~default-1-81153793.pc_first_rank_v2_rank_v28&utm_term=hashmap&spm=1018.2118.3001.4449#4%E3%80%81%E6%80%8E%E6%A0%B7%E4%BC%98%E5%8C%96%20HashMap%EF%BC%9F
[70]: /images/20221120/4ca9fc49ddbd46de9a91b25e9c85cb0a.png
[by zhanghaolin]: /images/20221120/62f039b5f7454c45a05beb0e89d3d7ef.png