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已经实现,将链表转为红黑树
网友评论