HashMap面试题

1、HashMap的原理，内部数据结构？

底层使用哈希表(数组 + 链表)，当链表过长会将链表转成红黑树以实现O(logn)的时间复杂度内查找

2、讲一下HashMap中put方法过程？

①、对key求Hash值，然后再计算下标
②、如果没有发生碰撞，直接放入桶中
③、如果发生碰撞了，则以链表的方式链接在后面
④、如果链表长度超过了阈值(TREEIFY_THRESHOLD=8)，就把链表转成红黑树
⑤、如果节点已经存在，就替换旧值
⑥、如果桶满了，即桶的大小 > （容量 * 加载因子），就需要进行resize 

3、HashMap中Hash函数怎么实现的？还有哪些hash的实现方式？

①、高16位不变，低16位和高16位做了异或
②、然后 (n - 1) & hash ，得到下标 。 【其中n是数组的容量】

4、HashMap怎么解决冲突，讲一下扩容过程，假如一个值在原数组中，现在移动了新数组，位置肯定改变了，那是什么定位到这个新在新数组中的位置？

● 将新节点加到链表后
● 容量扩大到原来的2倍，然后对每个结点重新计算哈希值
● 这个值只可能在两个地方，一个是原下标的位置，另一个是下标为 [原下标 + 原容量] 的位置

5、抛开 HashMap，hash冲突有哪些解决办法？

 ● 开放地址法
 ● 链地址法

6、针对 HashMap中某个Entry链太长，查找时间复杂度可能达到O(n)，怎么优化？

 ● JDK1.8已经实现，将链表转为红黑树