一个 ArrayList 就能让你面试到哭!

JAVA herman 88浏览

一个 ArrayList 就能让你面试到哭!我觉得这句话一点也不夸张。阅读本文让你彻底了解 ArrayList 吧!

在开始之前,我们先来简单的回顾一下 ArrayList 吧!

Java ArrayList

ArrayList

ArrayList 实现于 List、RandomAccess 接口。可以插入空数据,也支持随机访问。

ArrayList相当于动态数据,其中最重要的两个属性分别是: elementData 数组,以及 size 大小。 在调用 add() 方法的时候:

public boolean add(E e) {
    ensureCapacityInternal(size + 1);  // 进行扩容校验
    elementData[size++] = e;
    return true;
}

添加元素主要做的功能就是进行扩容校验,将插入的值放到尾部,并将 size + 1。

如果是调用 add(index,e) 在指定位置添加的话:

public void add(int index, E element) {
    rangeCheckForAdd(index);

    ensureCapacityInternal(size + 1);  // 扩容校验
    //复制,向后移动
    System.arraycopy(elementData, index, elementData, index + 1,
                     size - index);
    elementData[index] = element;
    size++;
}

同样的也需要扩容校验,接着对数据进行复制,目的是把 index 位置空出来放本次插入的数据,并将后面的数据向后移动一个位置。

最终的扩容代码如下:

private void grow(int minCapacity) {
    // overflow-conscious code
    int oldCapacity = elementData.length;
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    // minCapacity is usually close to size, so this is a win:
    elementData = Arrays.copyOf(elementData, newCapacity);
}

其实就是判断元素能发装下,装不下就进行扩容,扩容就是数组复制的过程。由此可见 ArrayList 的主要消耗是数组扩容以及在指定位置添加数据,在日常使用时最好是指定大小,尽量减少扩容。更要减少在指定位置插入数据的操作。

对 ArrayList 有所了解后,现在我来面试你,你来回答,看你能回答出几个问题!

ArrayList 中 elementData 为什么使用 transient 修饰?

transient Object[] elementData;

由于 ArrayList 是基于动态数组实现的,所以并不是所有的空间都被使用。因此使用了 transient 修饰,可以防止被自动序列化。

因此 ArrayList 自定义了序列化与反序列化,具体可以看 writeObject 和 readObject 两个方法。

需要注意的一点是,当对象中自定义了 writeObject 和 readObject 方法时,JVM 会调用这两个自定义方法来实现序列化与反序列化。

ArrayList 的插入删除一定慢么?

取决于你删除的元素离数组末端有多远,ArrayList拿来作为堆栈来用还是挺合适的,push和pop操作完全不涉及数据移动操作。

ArrayList 的默认数组大小为什么是10?

据说是因为sun的程序员对一系列广泛使用的程序代码进行了调研,结果就是10这个长度的数组是最常用的最有效率的。也有说就是随便起的一个数字,8个12个都没什么区别,只是因为10这个数组比较的圆满而已。

ArrayList 做队列合适么?

队列一般是FIFO的,如果用ArrayList做队列,就需要在数组尾部追加数据,数组头部删除数组,反过来也可以。但是无论如何总会有一个操作会涉及到数组的数据搬迁,这个是比较耗费性能的。

这个回答是错误的!

ArrayList固然不适合做队列,但是数组是非常合适的。比如ArrayBlockingQueue内部实现就是一个环形队列,它是一个定长队列,内部是用一个定长数组来实现的。另外著名的Disruptor开源Library也是用环形数组来实现的超高性能队列,具体原理不做解释,比较复杂。简单点说就是使用两个偏移量来标记数组的读位置和写位置,如果超过长度就折回到数组开头,前提是它们是定长数组。

ArrayList 中的 elementData 为什么是 Object 而不是泛型 E ?

Java 中泛型运用的目的就是实现对象的重用,泛型T和Object类其实在编写时没有太大区别,只是JVM中没有T这个概念,T只是存在于编写时,进入虚拟机运行时,虚拟机会对泛型标志进行擦除,也就是替换T会限定类型替换(根据运行时类型),如果没有限定就会用Object替换。同时Object可以new Object(),就是说可以实例化,而T则不能实例化。在反射方面来说,从运行时,返回一个T的实例时,不需要经过强制转换,然后Object则需要经过转换才能得到。

ArrayList list = new ArrayList(20); 中的list扩充几次?

默认ArrayList的长度是10个,所以如果你要往list里添加20个元素肯定要扩充一次(newCapacity 扩充为原来的1.5倍,但和输入的minCapacity相比发现小于minCapacity,于是 newCapacity = minCapacity,所以只扩容一次,具体见扩容里的grow方法),但是这里显示指明了需要多少空间,所以就一次性为你分配这么多空间,也就是不需要扩充了!

ArrayList 底层实现就是数组,访问速度本身就很快,为何还要实现 RandomAccess ?

RandomAccess是一个空的接口, 空接口一般只是作为一个标识, 如Serializable接口. JDK文档说明RandomAccess是一个标记接口(Marker interface), 被用于List接口的实现类, 表明这个实现类支持快速随机访问功能(如ArrayList). 当程序在遍历这中List的实现类时, 可以根据这个标识来选择更高效的遍历方式。

其实上面的回答并没有明确回答为什么要实现 RandomAccess 接口。后面我单独来写文章详细的来解释为什么要实现 RandomAccess!

参考资料

业余草公众号

最后,欢迎关注我的个人微信公众号:业余草(yyucao)!可加QQ1群:135430763(2000人群已满),QQ2群:454796847,QQ3群:187424846。QQ群进群密码:xttblog,想加微信群的朋友,可以微信搜索:xmtxtt,备注:“xttblog”,添加助理微信拉你进群。备注错误不会同意好友申请。再次感谢您的关注!后续有精彩内容会第一时间发给您!原创文章投稿请发送至532009913@qq.com邮箱。商务合作可添加助理微信进行沟通!

本文原文出处:业余草: » 一个 ArrayList 就能让你面试到哭!