JDK8 HashMap面试

原创
2018/05/23 10:16
阅读数 325

1 HashMap的原理,内部数据结构?

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

2 讲一下HashMap中put方法过程?

a 对key求Hash值,然后计算下标

b 如果没有碰撞,直接放入桶中

c 如果碰撞了,以链表的方式链接到后面

d 如果链表长度超过阀值(TREEIFY_THRESHOLD==8),把链表转为红黑树

e 如果节点已存在就替换旧值

f 如果桶满了(容量*加载因子),就需要resize

3 HashMap中hash函数是怎么实现的?还有那些hash实现方式?

a 高16bit不变,低16bit和高16bit做了一个异或

扩展https://www.zhihu.com/question/20733617/answer/111577937

b (n-1)&hash 得到下标

c 还有哪些hash实现方式

4 HashMap 怎样解决冲突,讲一下扩容机制,假如一个值在原数组中,现在移动到了新数组,位置肯定变了,那是什么定位到这个值在新数组中的位置

将新节点加到链表后

容量扩充为原来的两倍,然后对每个节点重新计算哈希值

这个值只可能在两个地方,一种是原下标的位置,另一种是在下标 原下标+原容量 的位置

扩展 https://blog.csdn.net/mgl934973491/article/details/60466487

5 抛开HashMap,hash冲突有哪些解决办法

开放定址 链地址法

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

链表转为红黑树

 

 

 

 

 

 

展开阅读全文
打赏
0
0 收藏
分享
加载中
更多评论
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部