面试官问你数组和 ArrayList 怎么答?

面试官问你数组和 ArrayList 怎么答?

我在想每个人在面试的时候都会被问到集合相关的问题,有好大一部分人在回答的时候并没有那么多的逻辑性,通常都是想到哪里说到哪里,这篇文章大概的捋一捋关于集合的相关问题。

在每种编程语言中,都会有循环、数组、流程控制语句,数组是一种线性表数据结构,内存空间是连续的,保存的数据类型也是一致的。

正是因为这两点,数组的随机访问才会非常的高效,这同时也是一把双刃剑,使得数组的其他操作效率变得很低,比如说,增加,删除,为了保持数组里面数据的连续性,就会做大量的消耗性能的数据迁移操作。

针对数组这种类型,java中有容器类,比如ArrayList,ArrayList是对数组的包装,在底层就是数组实现的,因为数组在定义的时候必须是指定的长度,定义之后就无法再增加长度了,就是说不可能在原来的数组上接上一段,所以ArrayList就解决了这个问题,当超过数组容量的时候,ArrayList会进行扩容,扩容之后的容量是之前的1.5倍,然后再把之前数组中的数据复制过来。

接下来,我们看下ArrayList的源码

 private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

源码中数组最大的容量是Integer.MAX_VALUE -8,为什么要减去8 呢,这个是上面的定义上面的注释

 /**     * The maximum size of array to allocate.     * Some VMs reserve some header words in an array.     * Attempts to allocate larger arrays may result in     * OutOfMemoryError: Requested array size exceeds VM limit     */

首先是一些VM在数组中保存的头信息;尝试着去分配更大的数组可能会导致OutOfMemoryError,请求的数组大小超过了VM的限制。

在看这句代码的时候,脑中有没有出现两个大大的问号??

首先,有没有想到为什么这个数组属性需要用 transient修饰?

(想知道这个关键字是干什么的,可以看下我之前的一篇文章: 面试问你java中的序列化怎么答? )

    transient Object[] elementData; // non-private to simplify nested class access

大家可以随便的想一下,如果是面试的时候,你会怎么回答?

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

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

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

第二个问题:这个属性的类型为什么是Object而不是泛型?

这里和大家说下:

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

当我们试图向ArrayList中添加一个元素的时候,java会自动检查,以确保集合中确实还有容量来添加新元素,如果没有,就会自动扩容,下面是核心代码,我已经在代码里加了注释,帮助大家能够更好的理解:

    private void ensureExplicitCapacity(int minCapacity) {        modCount++;        // overflow-conscious code        if (minCapacity - elementData.length > 0)            grow(minCapacity);    }

上面这段代码中有个 变量 modCount++,看到这里的时候确实有些疑惑,我找了下,这个变量是在AbstractList中定义的protected修饰的全局变量,这个变量是记录了结构性改变的次数,结构性改变就是说修改列表大小的操作。

ArrayList是一个线程安全的类,这个变量就是用来保证在多线程环境下使用迭代器的时候,同时又对集合进行了修改,同一时刻只能有一个线程修改集合,如果多于一个,就会抛出ConcurrentModficationException。

    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:
        //接下来,是把原数组d 数据复制到新的数组里
elementData = Arrays.copyOf(elementData, newCapacity);
}

private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
            //当 Integer-8 依然无法满足需求,就会取Integer的最大值
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
}

接下来我们看下,向指定位置添加元素是什么样的:

    public void add(int index, E element) {        rangeCheckForAdd(index);        //扩容校验        ensureCapacityInternal(size + 1);  // Increments modCount!!        System.arraycopy(elementData, index, elementData, index + 1,                         size - index);        elementData[index] = element;        size++;    }

可以看到,当一个集合足够大的时候,add操作向数组的尾部添加元素效率还是非常高的,但是当向指定的位置添加元素的时候,也是需要大量的移动复制操作:System.arraycopy()。

到这里,ArrayList最大的优势是什么呢?我们在平时的开发中涉及到容器的时候为什么会选择List家族的成员,而不直接选择数组呢?大家回想一下自己之前敲代码的经历,答案也就出来了:

ArrayList封装了大部分数组的操作方法,比如插入、删除、搬移数据等等,都在集合内部帮你做好了,还有就是支持动态扩容,这点是数组不能比拟的。

这里需要注意一点,当我们在开始定义集合的时候,如果知道我们需要多大的集合,就应该在一开始就指定集合的大小,因为在集合的内部来进行数据的搬移,复制也是非常耗时的。

那么数组在什么时候会用到呢?

1、java ArrayList无法存储基本类型,int,long,如果保存的话,就需要封装为Integer、Long,而自动的拆装箱,也有性能的消耗,所以总结下这点就是说如果要保存基本类型,同时还特别关注性能,就可以使用数组。

2、如果对数据的数量大小已知,操作也非常简单,也不需要ArrayList中的大部分方法,也是可以直接使用数组的。

如果对本文有任何异议,可以加我好友(有没有问题都欢迎大家加我好友),也可以在下面留言区留言,我会及时修改。希望这篇文章能帮助大家在面试路上乘风破浪。

面试官问你数组和 ArrayList 怎么答?

这样的分享我会一直持续,你的关注、转发和好看是对我最大的支持,感谢。关注我,我们一起成长。

面试官问你数组和 ArrayList 怎么答?

题图:作者实拍

原文 
https://mp.weixin.qq.com/s?__biz=MzU4NTI4ODgxMw==&mid=2247483823&idx=1&sn=81d050eabc8925ce1fbea32b75de079c&chksm=fd8d9cadcafa15bbdfb416966204504f20596782f21cc0a6626a4709200f601b070141f42adf&xtrack=1&scene=90&subscene=93&sessionid=1551763112&clicktime=1551763113&ascene=56&devicetype=android-28&version=2700033a&nettype=WIFI&abtest_cookie=BAABAAoACwASABMABAAjlx4AVpkeAL2ZHgDamR4AAAA=&lang=zh_CN&pass_ticket=Z6N4A1cn/0Yu be lkgxVUcnV14NBBBsDM Qyx6kuoaVF24UnM IBStzyyf4/EoC&wx_header=1

本站部分文章源于互联网,本着传播知识、有益学习和研究的目的进行的转载,为网友免费提供。如有著作权人或出版方提出异议,本站将立即删除。如果您对文章转载有任何疑问请告之我们,以便我们及时纠正。

PS:推荐一个微信公众号: askHarries 或者qq群:474807195,里面会分享一些资深架构师录制的视频录像:有Spring,MyBatis,Netty源码分析,高并发、高性能、分布式、微服务架构的原理,JVM性能优化这些成为架构师必备的知识体系。还能领取免费的学习资源,目前受益良多

转载请注明原文出处:Harries Blog™ » 面试官问你数组和 ArrayList 怎么答?

赞 (0)
分享到:更多 ()

评论 0

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址