10 分钟拿下 HashMap

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

1、什么是 HashMap？什么时候用到 HashMap？

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

2.1 数据结构

2.2 工作原理

3、为什么选择 HashMap？HashMap 和 HashTable 的异同？

4、如何优化 HashMap？

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

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

打个比方：

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

图示：

​

★ 问题：

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

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

2.1 数据结构

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

一张图带你看懂：

​

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

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 方法，为什么呢，我摘出了该方法的源码如下：

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

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

捡知识：

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

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

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

答：HashMap 中 equals 相同的两个 key， 容器中只会保留后进来的 key 的 value。进入问题中即：我先存储了 Lucy 的信息，后来又有一个 Lucy，这个时候再存储 Lucy，容器中保留的是第二个 Lucy 的信息，这种情况，我们可以考虑使用 List 作为 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

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

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