一、底层实现原理
1.1 底层数据结构
HashMap 的底层数据结构是一个由数组和链表实现的类似字典的结构，或者是红黑树的结构。在 HashMap 的长度小于 8 时是前者，大于或等于 8 时是后者。这也就意味着，HashMap 不仅仅会扩容，还可以“缩容”。
1.1.1 在 JDK1.8 之前
在这之前，HashMap 还没有被优化，底层的数据结构只可能是 数组 + 链表 的方式，不存在 HashMap 长度大于等于 8 后数据结构转变为红黑树的情况。那么，是怎么个 数组 + 链表的结构呢？如下图：
数组 + 链表
通过上面的图，我们可以很清晰地看懂 HashMap 的 数组 + 链表 结构，其中，数组中的元素是每个链表的头节点。
1.1.2 在 JDK1.8 及 1.8 之后
JDK1.8 之后，HashMap 被极大地优化了，在长度小于 8 时没有太大变化，但跟以往不同，在存储的数据特别大的情况下（长度至少大于等于 8），HashMap 的性能有了明显的改善，这要得益于数据结构转变成了红黑树。关于数据结构 —— 红黑树，我们这里不做详细的说明，具体参见：【红黑树】。
红黑树具有良好的性能，加速了 HashMap 一些操作的速度。此时 HashMap 的底层数据结构大致像下面这样：
数组 + 链表 + 红黑树
1.2 put 方法
put 是 HashMap 的一个方法，它可以往 HashMap 中添加或者修改一个键值对，它的具体过程如下：
在不考虑 HashMap 的长度达到 8 时结构由链表转变为红黑树的这种情况下，put 一个键值对 <key, value>，首先 key 和 value 会首先被实例化为一个实现了 Map.Entry<key, value> 接口的 Node 对象，然后调用 key 的 hashCode 方法得到 key 的哈希值，并与 HashMap 中已有的键的哈希值进行比较，如果在 HashMap 中没有出现这个哈希值，那么这个 Node 对象就会被视为一个新的键值对，并被添加到 HashMap 中去，如果出现了相同的哈希值，则会再次调用 key 的 equals 方法对 HashMap 中原有的这个键进行比较，若不同，则说明此时发生了哈希冲突，并将这个键值对添加到 HashMap 中去，若没有出现上述过程，则说明 HashMap 中已经有这个键值对了，那么就用 value 替换对应 key 的值。
下面用一张图展示了这个过程：
put 方法执行过程
当然，若是添加之后，HashMap 的长度大于或等于 8，那么在添加的时候还有将 HashMap 底层数据由链表转换为红黑树这一过程。这一部分在后续的“扩容机制”一节中将具体讲解。
二、扩容机制
2.1 负载因子（loadFactor）
HashMap 的负载因子是一个用来计算扩容阈值的数，计算公式是：
阈值（threshold）= 负载因子（loadFactor）× 容量（capacity）
当 HashMap 存储的数据个数达到阈值时，HashMap 将会自动进行容量扩充，负载因子的值默认为 0.75。
那么，为什么要有负载因子的存在呢？像 ArrayList 那样，当容量不够的时候再进行扩容难道不行吗？实际上，不是不行，只是不好。由于 HashMap 的增删改查或多或少涉及到哈希相关算法，若是像 ArrayList 那样，容量不够的时候再进行扩容，很容易导致出现“哈希碰撞”的情况，而出现“哈希碰撞”时就需要调用 equals 方法来解决这一问题，而 equals 方法的性能并不高，为了提高 HashMap 的性能，就需要适当地提前进行扩容。但是，又不能扩容非常多，因为扩容太多，而数据存储量并没有那么多的话，就会耗费过多内存空间，于是就有了负载因子的存在。
HashMap 的扩容本质上就是一个对时间和空间权衡的问题，想要时间少，那么空间就要耗费多，反之，想要空间耗费小，那么时间就要消耗多。只有一个不大不小的值，才能权衡这二者之间的利弊。
但是，这个值为 0.75 是怎么计算出来的呢？
首先，负载因子不能太大，也不能太小，我们可以大致估计出它在 0.5 ~ 1 之间最为合适，其中间值 0.75 是个不错的选择。其次，我们要知道，HashMap 每次扩容与 ArrayList 扩容 1.5 倍不同，HashMap 每次直接翻倍，而 HashMap 初始化后的默认容量是 16（24），因此 HashMap 的容量一般来说都是 2 的指数幂，而 0.75（3/4）与任何大于等于 4 的 2 指数次幂相乘的结果都是整数，正好，HashMap 的默认容量 16 是满足这个条件的，这样就避免了分数的麻烦。
2.2 默认容量
HashMap 初始化后的默认容量是 16，那么为什么是 16，而不像 ArrayList 那样，初始为 0，要添加的时候再进行扩容呢？
实际上这个值也是通过对时间和空间的权衡利弊得到的。我们可以简单分析一下，根据上面负载因子的值及扩容相关知识，我们可以知道，初始容量应该为 2 的指数次幂才可以保证 HashMap 的容量始终是 2 的指数次幂。很显然，当默认容量取得太大时，会有很多空间不一定利用，导致了空间的浪费，而当默认容量太小时，稍微让 HashMap 存储多一点的数据，它就需要多次调用扩容相关的代码，一次只扩容一倍，非常耗时。通过权衡时间和空间的利弊，HashMap 的默认容量就被定为了 16。
2.3 缩容
一般情况下，是不建议对 HashMap 进行缩容的，但是，这并不代表 HashMap 无法进行缩容了，它只是不会自动地缩容，要想缩容，必要手动进行。
2.3.1 不缩容的理由
我们不妨想想，缩容是通过时间来空间的操作，如果是在空间充足的情况下，这只会消耗时间，就算是空间不太充足的情况下，既然你扩容到了这么大，那么说明你确实有这么多的数据要存储，那又为什么要缩容呢？所以，一般来说，是没必要缩容的，除非真的在某一刻程序急需内存来处理某些棘手的问题，这个时候才需要缩容来腾出空间给其他程序使用，但这样对于空间不足的问题治标不治本，更好的方法是升级硬件配置或者改善程序来增加可用内存空间。
2.3.2 如何缩容
很简单的一种方法，实例化一个新的 HashMap，然后把原来 HashMap 的数据搬过来，再释放原来 HashMap 的内存空间，以达到“缩容”的目的。但是，这显然不是真正的缩容，实际上，Java 是不支持直接对一个 HashMap 对象进行真正意义上缩容的，从之前“不缩容的理由”一节中就可以看出，这样做，真的不是一个好的做法。
总结一句话就是，HashMap 缩容，没有必要。
