美文网首页
HashMap面试题

HashMap面试题

作者: 紫雨杰 | 来源:发表于2018-06-11 11:24 被阅读0次

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

    相关文章

      网友评论

          本文标题:HashMap面试题

          本文链接:https://www.haomeiwen.com/subject/fxkglftx.html