原创

3秒搞定ArrayList

jdk8

总结

  1. 扩容和删除

ArrayList 就是一个实现了List接口的可自动扩容的数组,**当添加元素的时候它会尝试扩容,扩容的标准是变为原来的1.5倍**,当删除元素的时候,它会左移元素,避免数组出现"空位"

  1. 容量

new ArrayList<>() 初始化容量为0,等到第一次add的时候再初始化为10

  1. 有序集合
  2. 可以存储重复值和null值

示例:

    public static void main(String[] args) {
        List<String> a=new ArrayList<>();
        a.add(null);
        a.add(null);
        a.add(null);
        System.out.println(a.size());
    }
    输出:
    3
  1. ArrayList 是快速失败的,在遍历的同时当集合被修改后会抛出ConcurrentModificationException,可以使用Iterator 的删除方法来避免这个问题
  2. 非线程安全的,如果你想在多线程环境中使用,可以使用Vector 或者它的线程安全包装类
  3. 扩展

操作系统的局部性原理,数组的连续存储空间的特性充分使用了局部性原理,也就是说硬件的高速缓存加速了数组的访问

<a name="Nd2QS"></a>

性能

  1. Adding an element- 如果你使用的是  add(E e) 方法添加一个元素到ArrayList末尾 ,它的时间复杂度 O(1);但是当空间不足引发扩容的时候,会导致新建数组然后拷贝数据,这个时候它的时间复杂度 O(n) ;当你使用 add(int index, E element)的时候它的算法复杂度是 O(n - index) 也就是 O(n)
  2. Retrieving an element- 当你使用get(int index) 的时候,它的时间复杂度是 O(1),因为数组可以直接根据下标进行定位
  3. Removing an element- 当你使用 remove(int index) 它的时间复杂度是 O(n - index) ,因为它涉及到移动元素
  4. Traverse - 遍历的时间时间复杂度是O(n),也就是依赖于Capacity 的大小,如果你比较重视遍历的性能,就请不要不要给它设置一个很大的初始容量

UML

d70acba1-7f88-4ff9-8266-a67b7ae90f4e.png

底层是一个Object[],添加到ArrayList中的数据保存在了elementData属性中。

  1. 当调用new ArrayList<>()时,将一个空数组 DEFAULTCAPACITY_EMPTY_ELEMENTDATA  赋值给了elementData,这个时候集合的长度size为默认长度0
  2. 例如当调用new ArrayList<>(100)时,根据传入的长度,new一个Object100赋值给elementData,当然如果玩儿的话,传了一个0,那么将一个空数组 EMPTY_ELEMENTDATA 赋值给了elementData
  3. 例如当调用new ArrayList<>(new HashSet())时,根据源码,我们可知,可以传递任何实现了Collection接口的类,将传递的集合调用toArray()方法转为数组内赋值给elementData

构造方法

无参构造

创建一个空的使用默认容量的list(默认是0,第一次add会初始化为10)

//默认创建一个ArrayList集合
List<String> list = new ArrayList<>();
/**
 * Constructs an empty list with an initial capacity of ten.
 */
public ArrayList() {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

指定初始容量

创建一个空的指定容量的list

//创建一个初始化长度为100的ArrayList集合
List<String> initlist = new ArrayList<>(100);

public ArrayList(int initialCapacity) {
    if (initialCapacity > 0) {
        this.elementData = new Object[initialCapacity];
    } else if (initialCapacity == 0) {
        this.elementData = EMPTY_ELEMENTDATA;
    } else {
        throw new IllegalArgumentException("Illegal Capacity: "+ initialCapacity);
    }
}

其他集合作为参数

//将其他类型的集合转为ArrayList
List<String> setList = new ArrayList<>(new HashSet());

/**
 * Constructs a list containing the elements of the specified
 * collection, in the order they are returned by the collection's
 * iterator.
 *
 * @param c the collection whose elements are to be placed into this list
 * @throws NullPointerException if the specified collection is null
 */
public ArrayList(Collection<? extends E> c) {
    elementData = c.toArray();
    if ((size = elementData.length) != 0) {
        // c.toArray might (incorrectly) not return Object[] (see 6260652)
        if (elementData.getClass() != Object[].class)
            elementData = Arrays.copyOf(elementData, size, Object[].class);
    } else {
        // replace with empty array.
        this.elementData = EMPTY_ELEMENTDATA;
    }
}

构造一个包含指定集合元素的列表,其顺序由集合的迭代器返回。当传入的集合参数为空的话,抛出NullPointerException,因为它会调用该集合的toArray 方法,和HashTable 里面调用key 的hashcode 方法的原理一样

当集合是一个空的集合的话,elementData = EMPTY_ELEMENTDATA和指定0是initialCapacity的效果一样

注意:在传入集合的ArrayList的构造方法中,有这样一个判断

if (elementData.getClass() != Object[].class), 给出的注释是:c.toArray might (incorrectly) not return Object,即调用toArray方法返回的不一定是Object[]类型,查看Collection接口的定义

Object[] toArray();

我们发现返回的确实是Object[],那么为什么还会有这样的判断呢? 如果有一个类CustomList继承了ArrayList,然后重写了toArray()方法呢。。

public class CustomList<E> extends ArrayList {
    @Override
    public Integer [] toArray() {
        return new Integer[]{1,2};
    };
    
    public static void main(String[] args) {
        Object[] elementData = new CustomList<Integer>().toArray();
        System.out.println(elementData.getClass());
        System.out.println(Object[].class);
        System.out.println(elementData.getClass() == Object[].class);
    }
}

执行结果:

class [Ljava.lang.Integer;
class [Ljava.lang.Object;
false

接着说,如果传入的集合类型和我们定义用来保存添加到集合中值的Object[]类型不一致时,ArrayList做了什么处理?读源码看到,调用了 Arrays.copyOf(elementData, size, Object[].class);

public static <T,U> T[] copyOf(U[] original, int newLength, Class<? extends T[]> newType) {    
    T[] copy = ((Object)newType == (Object)Object[].class)
        ? (T[]) new Object[newLength]
        : (T[]) Array.newInstance(newType.getComponentType(), newLength); 
    System.arraycopy(original, 0, copy, 0, Math.min(original.length, newLength));
    return copy;
}

我们发现定义了一个新的数组,将原数组的数据拷贝到了新的数组中去。

思考

    我们在查看 ArrayList 的实现类源码时,你会发现对象数组 elementData 使用了 transient 修饰,我们知道 transient 关键字修饰该属性,则表示该属性不会被序列化,然而我们并没有看到文档中说明 ArrayList 不能被序列化,这是为什么?<br />

ArrayList 属性主要由数组长度 size、对象数组 elementData、初始化容量 default_capacity 等组成, 其中初始化容量默认大小为 10。

// 默认初始化容量
private static final int DEFAULT_CAPACITY = 10;
// 对象数组
transient Object[] elementData; 
// 数组长度
private int size;

从 ArrayList 属性来看,它没有被任何的多线程关键字修饰,但 elementData 被关键字 transient 修饰了。这就是我在上面提到的第一道测试题:transient 关键字修饰该字段则表示该属性不会被序列化,但 ArrayList 其实是实现了序列化接口,这到底是怎么回事呢? 这还得从"ArrayList 是基于数组实现"开始说起,由于 ArrayList 的数组是基于动态扩增的,所以并不是所有被分配的内存空间都存储了数据。 如果采用外部序列化法实现数组的序列化,会序列化整个数组。ArrayList 为了避免这些没有存储数据的内存空间被序列化,内部提供了两个私有方法 writeObject 以及 readObject 来自我完成序列化与反序列化,从而在序列化与反序列化数组时节省了空间和时间。因此使用 transient 修饰数组,是防止对象数组被其他外部方法序列化


                                 看到这里就点个赞吧👇分享更多技术文章,去帮助更多的人,这里有我所有知识库哟~ 🐌

                                              https://www.yuque.com/yingwenerjie  

原创声明,本文系作者授权云+社区发表,未经许可,不得转载。

如有侵权,请联系 yunjia_community@tencent.com 删除。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 3秒搞定ConcurrentHashMap

    1、ConcurrentHashMap,是Java并发包中自JDK1.5后提供的一个线程安全且高效的HashMap实现,可以用来替代HashTable。直接实现...

    老兵程序员
  • 3秒种搞定HashMap

    老兵程序员
  • Spring Boot 启动,1 秒搞定!

    原文: dev.to 翻译: ImportNew.com - 唐尤华 译文: http://www.importnew.com/30647.html

    Java技术栈
  • 【译文】epoll() 3步搞定

    并不久远之前,设置单个Web服务器以支持10,000个并发连接还是一项伟大的壮举。有许多因素使开发这样的Web服务器成为可能,例如nginx,它比以前的服务器可...

    袁承兴
  • 3个案例秒懂,大数据是如何搞定用户交易画像的

    如何构建用户交易画像? 基于交易行为,我们可以依据 3 个关键指标进行用户分群。 1. 流失风险。看每个用户上一次交易距今的时间,上次交易距今时间越远流失风险越...

    BestSDK
  • 3. 搞定收工,PropertyEditor就到这

    上篇文章介绍了PropertyEditor在类型转换里的作用,以及举例说明了Spring内置实现的PropertyEditor们,它们各司其职完成 String...

    YourBatman
  • 3分钟搞定图片懒加载

    图片的懒加载就是在页面打开的时候,不要一次性全部显示页面所有的图片,而是只显示当前视口内的图片,一般在移动端使用(PC端主要是前端分页或者后端分页)。

    Daotin
  • 3步搞定GWAS中的Gene Set Analysis

    GWAS中的Gene Set Analysis, 简称GSA分析,是从基因或者通路水平来进行关联分析,是建立在SNP水平的的GWAS分析结果基础上的,在更高的层...

    生信修炼手册
  • 3步轻松搞定Spring Boot缓存

    本次内容主要介绍基于Ehcache 3.0来快速实现Spring Boot应用程序的数据缓存功能。在Spring Boot应用程序中,我们可以通过Spring ...

    程序员追风
  • 索尼大法好,224秒在ImageNet上搞定ResNet-50

    随着数据集和深度学习模型的规模持续增长,训练模型所需的时间也不断增加,大规模分布式深度学习结合数据并行化是大幅减少训练时间的明智选择。然而,在大规模 GPU 集...

    机器之心
  • 初体验Spring Boot 2支持的HikariCP连接池

    Hikari,没错,听着就不像英文,是一句日语,最初是由一个居住在日本的老外开发的一款数据库连接池。 (这单词怎么读呢?hi·ka·'lē。注意最后的ri读成l...

    ImportSource
  • Java总结之容器家族--Collection

    Set的操作比较少,基本上也就是Collection传下来的方法 Set一般基于Map来实现:HashSet、LinkedHashSet、TreeSet的特性...

    张风捷特烈
  • 杂篇-从整理文件发起的杂谈[-File-]

    张风捷特烈
  • 数据结构之Array、ArrayList、List、LinkedList对比分析

    在c#数据结构中,集合的应用非常广泛,无论是做BS架构还是CS架构开发,都离不开集合的使用,比如我们常见的集合包括:Array、ArrayList、List、...

    小小许
  • Java 8 ArrayList hugeCapacity 函数与 MAX_ARRAY_SIZE

    今天有一个朋友问到一个为什么 ArrayList 源码扩容方法中,数组长度最大值是 MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8...

    明明如月学长
  • xml解析---Java解析xml文件

    dom4j解析xml文件、之前用下面的方法,90M的xml,500万行,解析完插入数据库,单线程,不到1小时搞定,而只是解析数据,只用了7秒。

    IT云清
  • Spring Boot入门系列(八)整合定时任务Task,一秒搞定定时任务

    今天主要讲解Springboot整合定时任务。在SpringMvc中也会用到很多的定时任务,主要是通过Quartz实现。但是在Spring MVC中使用这些插件...

    架构师精进
  • Day 3:从尾到头打印链表

    思路1: 1、先构造一个链表 2、定义一个栈,将链表元素放入到栈中 3、利用栈的先进后出,实现从尾到头返回 4、取出栈中元素放入到ArrayList,然...

    一计之长
  • 2 分钟搞定 3 个现代 CSS 特性

    Clip Paths 能把元素元素“裁剪”成特定形状,使用 CSS 提供的 polygon、circle、ellipse 等这些函数实现。举个例子:

    Javanx

扫码关注云+社区

领取腾讯云代金券