美文网首页
HashMap面试问题整理

HashMap面试问题整理

作者: 小甲说 | 来源:发表于2018-10-18 19:05 被阅读0次

    1.HashMap底层原理 数据结构
        底层使用哈希表(数组+链表进行存储),在jdk1.8后 当链表长度大于等于8时 将链表转为红黑树 ,时间复杂度由O(n)变为O(logn)

    2.HashMap的put过程

        (1)对key计算hash值 求下标

        (2)如果没有发生hash碰撞,直接放入桶中

        (3)如果发生碰撞,放在链表的后面 并计算链表长度 大于8转为红黑树

        (4)如果节点已经存在进行覆盖

        (5)如果长度大于(长度*负载因子0.75) 进行扩容resize

    3.HashMap中的hash函数是怎么实现的

        (1)高16bit不变 低16bit和高16bit做了一个异或(^)

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

    4.扩容过程是什么样的,原来某位置的元素,移动到了新数组,位置怎么确定

        (1)扩容为原来的2倍,对每个节点重新计算hash值

        (2)可能的位置是原来的位置 或者是(原下标+原容量)的位置

    5.hash冲突还有那些解决办法

        开放定址法(线性探测) 链地址法 再哈希法

    6.链表查找某个元素的时间复杂度是O(n),怎么优化

        单向链表 无法优化 一种是hashMap实现的红黑树 另一种是可以通过双向链表来实现 这样就可以使用折半查找 但是因为要保存上一个元素的地址 更加耗费内存空间

    相关文章

      网友评论

          本文标题:HashMap面试问题整理

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