美文网首页
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