集合面试题汇总

时间:2022-11-30 08:08:38

我们会在这里介绍我所涉及到的集合相关的面试题内容,本篇内容持续更新

我们会介绍下述集合的相关面试点:

  • 迭代器
  • ArrayList
  • LinkedList
  • HashMap

迭代器

这里我们来介绍一下迭代器的面试点

迭代器中断处理机制

迭代器是操作集合的工具,当我们已经创建了一个迭代器之后,我们就不能再对原集合进行修改,否则可能报错出现问题

实际上迭代器对于中途修改集合的操作给出了两个处理方式:

  • fail-fast:一旦发现遍历的同时其他人来修改,则立即抛出异常
  • fail-safe:发现遍历的同时其他人来修改,应当有对应的应对策略,如牺牲一致性来让整个遍历循环结束

fail-fast

我们首先来介绍fail-fast:

  • 集合出现修改情况,迭代器遍历直接报错

我们直接从底层方法讲起:

/*Itr迭代器通常使用fail-fast中断处理机制*/
    
/*判断如何发生其他进程修改集合*/

private class Itr implements Iterator<E> {
        
        int cursor = 0;

        int lastRet = -1;

    	// 这里是核心:modCount是当前集合的修改次数,expectedModCount用于迭代器记录当前修改次数
        int expectedModCount = modCount;

    	// 我们会使用hasNext和next方法进行迭代器foreach
        public boolean hasNext() {
            return cursor != size();
        }

        public E next() {
            checkForComodification();
            try {
                int i = cursor;
                E next = get(i);
                lastRet = i;
                cursor = i + 1;
                return next;
            } catch (IndexOutOfBoundsException e) {
                // 注意:我们在每次处理时,都会调用一次checkForComodification()来判断expectedModCount = modCount?
                checkForComodification();
                throw new NoSuchElementException();
            }
        }

    	// 当modCount != expectedModCount就说明有集合发生了变化,我们就会直接抛出异常
        final void checkForComodification() {
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();
        }
    }

fail-safe

我们再来介绍一下fail-safe:

  • 集合出现修改情况,我们采用牺牲一致性的方法来完成迭代器遍历

我们同样从底层代码查看:

/*COWIterator迭代器采用的fail-safe处理方法*/

static final class COWIterator<E> implements ListIterator<E> {
        
    	// 这里就是核心:snapshot用于储存当前集合的所有元素
        private final Object[] snapshot;

        private COWIterator(Object[] elements, int initialCursor) {
            cursor = initialCursor;
            snapshot = elements;
        }
    
    	// 源码我没有找到,大致意思就是:
    	/*
    	COWIterator对应集合当进行add添加时
    	我们首先直接采用getArray获得snapshot里面的元素,采用geiSize获得原集合的大小
    	然后根据size直接创建一个新的集合,并将snapshot的元素复制进去,再将修改内容修改到新集合中
    	同时COWIterator遍历旧集合,两者之间互不影响
    	*/
    }

ArrayList

这里我们来介绍一下ArrayList的面试点

ArrayList扩容问题

ArrayList最常见的就是底层扩容问题,我们在这里将ArrayList的全部知识进行总结:

/*ArrayList底层*/

ArrayList底层是采用数组完成的

/*ArrayList创建*/

当无参创建时,ArrayList会默认创建一个长度为0的数组
    
当有参创建时,ArrayList会默认创建一个长度为10的数组
    
/*ArrayList扩容阈值add*/
    
ArrayList的第一个阈值为10,每次扩容就会扩容当前阈值的1.5倍
    
扩容值计算:首先将当前阈值位运算向右一次,然后将当前阈值加上刚刚运算的数即可
    
当无参构建时,长度默认为0,当add第一个元素后,会自动扩容到第一个阈值10
    
当超过阈值10时,这时会默认扩容到第二个阈值15
    
/*ArrayList扩容阈值addAll*/
    
addAll方法会一次添加多个数据
    
当采用addAll时的扩容阈值更新规则如下:
    - 每次扩容,都会选择下一个阈值点或者该集合存储数据的数量的最大值
    - Math.max(ArrayList.nextInt,ArrayList.capticy)
    
我们给出一个简单例子;
    - 当无参构造:addAll(1,2,3)这时阈值更新为下一个阈值10
    - 当无参构造:addAll(1,2,3,4,5,6,7,8,9,10,11),这时阈值更新到添加后集合的最大值11
    
    - 有参构造:目前已有10个元素,addAll(1,2,3),更新到下一个阈值15
    - 有参构造:目前已有10个元素,addAll(1,2,3,4,5,6),更新到添加后最大阈值16
    
/*ArrayList扩容具体步骤*/
    
ArrayList扩容步骤:
	1.首先新创一个新数组,数组大小就是扩容大小
    2.采用Arrays类的CopyOf()方法,将原数据移动到新数组中,再进行新的add或addAll方法

LinkedList

这里我们来介绍一下LinkedList的面试点

LinkedList与ArrayList比较

面试中经常会将两者内容进行对比:

/*ArrayList特点*/

1.基于数组,需要连续空间
2.随机访问快(根据下标访问)
3.尾部插入,删除性能快,其他部分插入删除会移动数据,性能慢
4.可以利用CPU的空间局部性原理,加快速率
    
这里提出一点:ArrayList继承了RandomAccess类,该类只是一个标识类,但当其继承该类后表示可以采用下标进行数据查询
    
/*LinkedList特点*/
    
1.基于双向链表,无需连续空间
2.随机访问慢,需要遍历链表
3.头尾插入速率快
4.占用内存较多

HashMap

这里我们来介绍一下HashMap的面试点

HashMap基础思路

首先我们来介绍一下HashMap的基本思路:

/*HashMap组成*/

首先由一个数组h[]组成
    
每个数组上都是一个链表,链表具有e[],next[]两个数组组成,分别代表当前值,下一个值
    
HashMap的默认长度首先为16,当出现特定情况时就会进行扩容
    
当链表过长时,就会转化为红黑树来优化

/*HashMap操作*/
    
put插入操作:
    1.通过hashCode()获得一次hash
    2.通过hash()获得二次hash
    3.将二次hash & (桶Size - 1) ;其实就是mod然后得到余数
    4.将数据放入即可
    
查找操作:
    1.通过hashCode()获得一次hash
    2.通过hash()获得二次hash
    3.将二次hash & (桶Size - 1) ;其实就是mod然后得到余数
    4.在指定位置进行查询,通过链表查询,通常复杂度O(1)

HashMap面试点

HashMap的面试点相对较多,我们下面一一介绍:

/*HashMap组成结构*/

1.7: 数组 + 链表
    
1.8: 数组 + (链表/红黑树)
    
/*简单问题*/
    
// HashMap扩容条件
    1.当插入数据大于桶Size的0.75时
    2.当链表长度大于8,且桶Size长度小于64时,采用HashMap扩容希望减小链表长度
    
// 红黑树出现条件
	1.当链表长度大于8时,为了减少链表长度进行操作
    2.但是当桶Size < 64,会优先进行HashMap扩容来优化链表长度;当桶Size >= 64时,才会进行红黑树转换
    3.注意:当链表长度为8,再添加时,只会执行上述的一种,倘若桶Size扩充后链表并未分散开,也不会有其他操作
    
// 红黑树退化为链表条件
    1.当进行扩容时,如果拆分树后,该树的节点小于等于6,就会退化
    1.在删除操作前,做判断:该树root,root.left,root.right,root.left.left 任意一个 == null,就转化为链表
    2.注意是操作前:假如我们本次操作删除了root.left.left,并不会导致退化,而是在下次remove操作时才会进行退化
    
/*链表和红黑树问题*/
    
// 为什么要采用红黑树?
	红黑树一般用于避免Dos攻击,防止链表过长性能下降,出现数化为偶然状况
    
// 为什么最开始使用链表,后续才使用红黑树?
	当链表长度较短时,链表查询复杂度为O(1),红黑树查询复杂度为O(log2 n)
	红黑树所占用的内存空间相对而言比较大,耗费过多
    
// 红黑树出现阈值为什么为8?
	因为当hash值较为随机时,hash表按破损分布,当负载因子为0.75时,长度超过8的概率仅有亿分之六,这里是为了让树化几率足够小
    
/*hashCode问题*/
    
// 索引如何计算
    首先我们都需要采用hashCode()获得一次hash,然后采用hash()获得二次hash
    
    1.在我们的视角里:hash值 % 桶Size
    2.在计算机视角里:hash值 & (桶Size - 1)
    
// 采用hashCode()获得后,为什么还需要hash()方法二次计算
    hash方法可以帮助我们综合高位数据,让哈希分布更加均匀
    
    static final int hash(Object key) {
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }

// 数组容量为什么是2的n次幂
	计算索引时,我们可以采用位运算来代替正常mod,来增加速率
    扩容时,我们会根据扩容2倍,这时我们可以根据当前值的hash & oldCap == 0来判断是否需要移动
    若为0不需要移动,若不为0,移动至 旧位置 + oldCap
        
    其次其实前面的hash,hashcode等操作都是为了配合容量为2的n次幂的优化手段
        
/*PUT方法流程版本*/
        
// PUT方法统一流程
	1.HashMap是懒惰创建数组,只有首次使用才会创建数组
    2.计算索引(桶下标)
    3.如果桶下标还没有人占用,创建Node占位返回
    4.如果桶下标已有人占用
        - 已经是TreeNode,走红黑树的添加或更新逻辑
        - 是普通Node,走链表的添加或更新逻辑,若超过树化阈值,走树化逻辑
    5.返回前检查容量是否查过阈值,一旦超过进行扩容(注意:这里是先将数据添加到数组中,然后再进行扩容处理)
        
// 版本不同流程
    1.链表插入节点时:1.7为头插法,1.8为尾插法
    2.对于扩容调价:1.7当大于等于阈值且当前添加点已经存在链表值才会扩容,1.8当大于阈值直接扩容
    3.1.8再扩容计算Node索引时存在优化:就是hash & oldCap == 0来判断是否需要移动
        
/*加载因子问题*/
        
// 加载因子为什么是0.75?
	1.在空间占用与查询时间之间取得较好的平衡
    2.大于这个数,空间节省了,但链表长度就会比较长从而影响性能
    3.小于这个数,效率加快了,但扩容更加频繁,空间占用较多
        
/*多线程下问题*/
        
// 数据缺失问题(1.7,1.8均出现)
    1.当线程1,线程2同时进行putval方法时,可能出现数据缺失
    2.进行putval需要先判断当前节点是否为null,若为空,采用Node占位,然后放入数据
    3.当线程1,检测该节点为null后,转换线程2,线程2也判断该节点为null,然后放入数据
    4.这时线程1重新取得权限,但是已经判断过为null了,然后它也往节点输入数据,就会导致线程2的数据被覆盖
        
// 并发死链问题(1.7头插法导致)
    1.线程1,线程2同时进行扩容操作时
    2.假设原HashMap存在a->b,注意扩容时,仅仅是将数据对象的next数据改变,数据本身不会新创也不会改变
    3.线程1首先获得a,然后切换到线程2执行,线程2进行操作,使其变化为b->a
    4.线程1重新获得操作,然后它会将a继续加入到链表中,变为a->b->a,但其实这时就出现了一个a,b之间的死循环
        
/*key相关问题*/
        
// key是否可以为null?
    HashMap的key可以为null,其他的Map不一定
        
// 作为key,具有什么要求?
    1.必须实现hashCode和equals方法
    2.必须是不可变类型,其内容不能修改,否则可能查询失败导致错误
        
/*hashCode方法问题*/
        
// hashCode为什么每次都乘31?
    1.目的是为了达到较为均匀的散列效果,每个字符串的hashCode足够独特
    2.字符串中的每个字符都可以表现为一个数字,称为Si,其中i的范围是0~n-1
    3.散列公式为:S0 * 31^n-1 + S1 * 31^n-2 + ...... + Sn-1 * 31^0
    4.31带入公式具有较好的散列特性,并且31*h可以优化为:
        32 * h - h
        2^5 * h - h
        h << 5 - h

结束语

目前关于集合的面试点就总结到这里,该篇文章会持续更新~

附录

参考资料:

  1. 黑马Java八股文面试题视频教程:基础篇-32-ArrayList_扩容规则_哔哩哔哩_bilibili