[数据结构与算法]HashMap常见问题

JDK1.8 中 HashMap 的底层实现，我相信大家都能说上来个 一二，底层数据结构 数组 + 链表（或红黑树），但是面试过程中通常会问的比较细因为HashMap在开发过程中用的也比较多，所以会问的比较多，做了些总结，例如：

一、table 的初始化时机是什么时候，初始化的 table.length 是多少、阀值（threshold）是多少，实际能容下多少元素？

答：一般情况下，在第一次putt的时候，调用resize方法进行table的初始化。

那么初始化的table.length是多少、阈值多少呢，实际能容下多少呢？

默认情况下，table,lengeth=16；阈值为12，能存放下12个元素，在当存放第13个元素后会进行扩容。

二、那么table的扩容是什么时候触发的呢，扩容完table.length为多少呢，阈值是多少呢？

1.当 size >阈值 (threshold) 的时候进行扩容，扩容之后的 table.length = 之前table.length * 2,
扩容之后的 阈值?= 之前阈值?* 2

三、为什么加载因子为0.75呢

加载因子太小， table 需要不断的扩容，影响 put 效率；太大会导致碰撞越来越多，链表越来越长（转红黑树），影响效率；0.75 是一个比较理想的中间值

四、table 的 length 为什么是 2 的 n 次幂

举例说明：

Map map = new HashMap(1000); 当我们存入多少个元素时会触发map的扩容呢？

• 此时的 table.length = 2^10 = 1024; threshold = 1024 * 0.75 = 768; 所以存入第 769 个元素时进行扩容

Map map1 = new HashMap(10000); 我们存入第 10001个元素时会触发 map1 扩容吗

• 此时的 table.length = 2^14 = 16384; threshold = 16384 * 0.75 = 12288; 所以存入第 10001 个元素时不会进行扩容