美文网首页
HashMap面试总结

HashMap面试总结

作者: imclient | 来源:发表于2020-03-01 15:48 被阅读0次

    HashMap原理总结

    问题:

    1.为什么7头部插入,8改成尾部插入?

        7为了提升效率,尾部插入需要遍历链表,同时扩容时链表会反转,存在循环链表问题;

        8引入红黑树,必须知道链表长度才能进行转换,会遍历链表,并直接在尾部插入,同时避免7中扩容引起的循环链表问题;

    2.默认负载因子为什么是0.75?

        提升效率,减少空间浪费的一个折中方案;

    3.为什么初始化容量是2的n次方-1?

        hash & (table.length - 1) 2n次方-1 保证余下来的都是 1111 ,如果有0,hash后无论0、1与运算都为0,桶一直都不会有值,位与运算计 算出下标,保证分布均匀

        位运算:全是1则为1,有0则为0

        计算过程:


        16 - 1 = 15 -> 1111

        1111

        1101 0011 1010 1100 1011

        ------------------------

        1011 -> 11

        所得结果范围在0-15,最后index为11


    4.什么时候扩容?

        扩容条件:size >= threshold && null != table[bucketIndex]

        1.实际元素个数大于等于预期值

        2.目标位置不为null

    5.扩容过程?

        jdk7: transfer():新建长度2倍的数组,循环旧数组,遍历数组上的链表根据hash结果计算下标放到新数组里,从头拿元素,从头插元素,链表倒序插入;

        jdk8: 高低位运算,扩容为原来2倍时,低位不变,高位变化

    6.并发问题?

        多线程问题:jdk7 扩容时,因为是链表需要移到新的桶上,头变尾,链表发生倒序过程,会产生循环链表,线程一直循环;

        jdk8是在尾部插入不会有循环问题,因为顺序和原来的一致,但是多线程会有问题;

    7.jdk8对HashMap的改进?

        1)数组+链表/红黑树

        2)扩容时插入顺序改变

        3)函数forEach等

    Jdk7

    ConcurrentHashMap:

    原理:有一个Segment概念,Segment[] 数组组成,包含多个Segment对象(相当于Enatry对象),每个是一个小的HashMap,都实现了RentrantLock,put时会先tryLock(),finally中会释放锁,初始化时根据并发级别初始Segment[]容量大小,取2的指数幂

    Jdk8

    HashMap:

    Put时判断是TreeNode还是链表,链表会遍历长度,并在尾部插入,如果达到8则转换为链表,jdk7中是在头部插入;

    伪代码:

    if(instanceof TreeNode){

        // 在树中插入

     } else {

        //链表

        for(){

            // 遍历链表长度,并在尾部插入元素

            if(p.next == null){

                p.next = newNode;

                    if(){

                        //最后如果长度大于8转换成红黑树

                        treeifyBin();

                    }

            }

        }

    }

    HashMap:

    哈希表:基于哈希值的桶和链表;

    HashMap创建时不会初始化,在第一次put时初始化

    相关文章

      网友评论

          本文标题:HashMap面试总结

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