[数据结构与算法]HashMap底层原理面试题

问题1：hashmap底层数据结构，1.7和1.8有何不同？

1.7数组 + 链表，1.8数组 +（链表 | 红黑树）

问题2：为何要用红黑树？为何一上来不树状？树化阈值为何是8？何时会退化为链表？

• 红黑树用来避免Dos攻击，防止链表过长时性能下降，树化应当是偶然情况。
• hash表的查找更新的时间复杂度是O(1)，而红黑树的查找、更新时间复杂度为O(log n）红黑树的数据结构为TreeNode占用空间不普通链表使用的Node的大，如非必要，尽量使用链表。
• hash值如果足够随机，则在hash表内按泊松分布，在负载因子0.75的情况下，长度超过8的链表出现概率是0.00000006，选择8就是为了让树化几率足够小。
• 树化有两个条件：链表长度超过数化阈值；数组容量>=64
• 退化情况1：在扩容时如果拆分树时，树元素个数<=6则会退化成链表。
• 退化情况2：remove树节点时，若root、root.left、root.right、root.left.left有一个为null，也会退化为链表。

问题3：索引如何计算？hashcode都有了，为何还要提供hash()方法？数组容量为何是2的n次幂？

• 计算对象的hashcode，再进行调用hashmap的hash方法进行二次哈希最后&(capacity-1)得到索引。
• 二次hash是为了综合高位数据，让哈希分布更为均匀。
• 计算索引是，如果是2的n次幂可以使用位与运算代替取模，效率更高；扩容时hash&oldCap == 0 的元素留在原来的位置，否则新位置 = 旧位置 + oldCap

问题4：介绍一下put方法流程，1.7和1.8有何不同？

• hashmap是懒惰创建数组的，首次使用才创建数组，计算索引下标，如果桶没有人占用，则创建Node占位返回，如果桶下标有人占用，如果是Node，则走链表的添加和更新逻辑，如果链表过长则树化。如果是TreeNode，则走红黑树添加更新逻辑。返回前检查容量是否超过阈值，一旦超过进行扩容。

不同：

• 链表插入节点时，1.7是头插入，1.8是尾插法

• JDK1.7中，先扩容，再存储。扩容条件：当前数量大于 容量 * 负载因子，并且数组下标的值不为空，即假如新插入的数据位置在一个数组位置而不是链表上，则插入成功而不扩容。而1.8是先存储，后扩容。扩容条件只有大于容量*负载因子。

加载因子为何默认是0.75？

• 在空间占用与查询时间之间取得较好的权衡
• 大于这个值，空间节省了，但链表就会比较长影响性能。
• 小于这个值，冲突减少了，但扩容就会频繁，空间占用多。