HashMap高频面试题---速成版

本人根据自己网上学习和查阅书籍总结下来的HashMap的高频问题，以及面试官最喜欢问到的问题进行的总结，本文是给突击面试的朋友准备，如果想了解更深层的源码还需要读者自行去了解其他资料。

HashMap的底层数据结构是什么？

1.7数组+链表 1.8数组+链表+红黑树

Map中的key:无序的、不可重复的，使用Set存储所的key Map中的value:无序的、可重复的，使用Collection存储所的value 一个键值对：key-value构成了一个Entry对象。 Map中的entry:无序的、不可重复的，使用Set存储所的entry

key能否为null？作为key的对象有什么要求？

①HashMap 、LinkedHashMap 的 key 和 value 都允许为 null

②作为key对象，必须重写equals和hashcode，并且key的内容不能修改

为什么二次hash要高低位异或？或者问为什么要二次hash？

因为hashcode是32位的，并且hashmap的散列表长度一般不会很大，让hashcode右移16位后再进行异或运算的值就能让hashcode的高16位也参与运算，最后再用二次hash的值计算桶下标的时候能够为了让哈希分布更均匀，更合理的避免hash冲突。

就能让高16位也参与到和数组容量-1进行按位与运算

怎么实现二次hash？

对任何一个对象调用hashcode()得到原始hash值

然后和原始hash值右移16位后进行异或运算

索引（桶下标）如何计算？

对任何一个对象调用hashcode()得到原始hash值

然后调用hashmap中的hash()进行二次hash，再把这个值按位与数组容量-1（和数组容量取模)运算得到索引

HashMap 的长度为什么是2的幂次方

因为在hashMap的长度等于2的n次方的时候，才会有hash%length==hash&(length-1)；哈希算法的目的是为了加快哈希计算以及减少哈希冲突，所以此时&操作更合适，所以在length等于2的幂次方的时候，可以使用&操作加快操作且减少冲突，所以hashMap长度是2的幂次方

HashMap的默认加载因子为什么是0.75？

在空间占用和查询时间上获得了较好的权衡

大于了 空间小 冲突多了

小于了 空间大了 冲突少了

为什么HashMap扩容是原来的两倍？

因为计算桶下标的时候需要保证n是2的n次方，位运算时可以充分散列，避免不必要的哈希冲突。

如何解决hash冲突？

开放地址法和单独链表法

其实，Java中的HashMap采用的hash冲突解决方案就是单独链表法，也就是在hash表节点使用链表存储hash值相同的值。

链表过长会怎么样？

会影响搜索性能

怎么解决链表过长问题？

数组扩容或红黑树

扩容：当原始hash码不同的时候，可以通过扩大数组长度（原来的2倍）来解决链表过长（求模）

树化：满足条件：链表长度超过树化阈值8并且数组容量大于64

红黑树：父节点左侧都是比它小的，右侧都比他大

扩容过后如果链表需要移动怎么移动？

用链表上的元素的原始hash值和原始容量进行按位与

如果结果是0，扩容以后就不移动

如果结果不是0，扩容以后位置=原始位置+原始容量

put方法流程？

1.8中：

①首次调用put()才创建数组（懒加载）长度为16

②计算索引

③如果索引处为空，那么就创建Node占位然后返回

④如果索引处有元素

1.已经是TreeNode走红黑树的添加或更新逻辑

2.是普通的Node，走链表的添加或更新逻辑，如果链表长度超过树化阈值，走树化逻辑

添加或更新逻辑：

如果key1的哈希值与已经存在的数据的哈希值都不相同，此时用尾插法插入将key1-value1添加到链表后面。

如果key1的哈希值和已经存在的某一个数据(key2-value2)的哈希值相同调用key1所在类的equals(key2)方法

1.如果equals()返回false，此时key1-value1添加成功

2.如果equals()返回true:使用value1替换value2

⑤返回前检查元素个数是否超过阈值（数组长度的3/4），一旦超过就扩容

1.7和1.8不同？

1.7头插，1.8尾插

1.7大于等于阈值没有空位才扩容，1.8大于阈值就扩容

为什么1.8要把头插法改为尾插法？或者是HashMap 多线程操作为什么会死循环？

1.7的时候比如在扩容的时候，链表扩容的位置不变，所以就直接进行迁移就行了，

e变量指向当前元素，next变量指向下一个元素，每次移动的时候就把e迁移到新数组的位置上去。

但是在多线程的扩容迁移中，有t1和t2两个线程，链表上有a，b两个元素（e指向a，next指向b）

如果t2先执行后，顺序就变成了b，a（但是t1还是 e指向a，next指向b）

再次切换到t1后，顺序变成了a，b（本来应该是a->b 但是变成了a->b->a形成了循环）

HashMap中并发操作为什么会丢失数据？

当线程t1和线程t2放入两个hash值一样的数据(\"a\"和1按位与16-1都是一个位置)，他们两个会在同一个位置上。

t1在放入之前，t2先把数据放入到了桶中，按理说应该是会调用equals方法判断后，把t1插入的数加在t2的后面形成链表

但是结果是在t1放入过后直接就把t2给覆盖掉了（因为t1进入的时候还没把数据放入到相应的位置上（只过了判断 但是桶里位置为null），t2进入的时候以及把元素放在了桶里，所以就直接t1就直接覆盖掉了t2的元素）

为什么引入红黑树？

解决hash冲突 导致链化严重时的查询效率低的问题，散列表本身o（1），冲突严重o（n），红黑树查询是o（logn）

红黑树的插入原理?

TreeNode是红黑树的实现，在Node的基础上添加了parent、left、rigtht、red，红黑树满足二叉排序树的性质

插入：找到插入的父节点，每次向下查找一层就可以排除掉一半的数据（left小于当前节点、right大于当前节点），

如果一直向下查找到叶子节点为null，就没找到要和要插入的数一样的TreeNode的key，但是可以找到插入的父节点所在，然后把待插入的值插入到插入父节点的左边或右边，然后因为打破了平衡，所以需要一个红黑树的平衡算法。

如果一直向下查找到了TreeNode的key，直接就替换元素value字段即可。

红黑树的性质？

性质1: 每个节点要么是红色，要么是黑色。

性质2:根节点永远是黑色的。

性质3:所有的叶子节点都是空节点(即null)，并且是黑色的。

性质4: 每个红色节点的两个子节点都是黑色。( 从每个叶子到根的路径上不会有两个连续

的红色节点)

性质5:从任一节点到其子树中每个叶子节点的路径都包含相同数量的黑色节点。

为什么不一上来就树化？

链表短的情况下，性能比红黑树好，并且链表底层是Node而红黑树是TreeNode内存占用高

树化阈值为什么是8？

红黑树是用来避免DOS攻击的，防止恶意使用相同hash值的数据使得链表超长性能下降，在负载因子为0.75的情况下，超过8的概率是1e分支6，选择8就是让树化概率足够小，如果到8还是树化了的话，说明那么小的概率都发生了hash冲突后面一定还会继续发生hash冲突，就需要变成红黑树。

何时红黑树退化为链表？

扩容的时候2如果拆分了红黑树，树的元素个数<=6会退化为链表

remove树节点的时候，如果根节点，左右孩子，左孙子有一个为null，则会退化为链表