文档章节

JAVA集合之ArrayList

木木匠
 木木匠
发布于 2018/09/24 10:03
字数 2221
阅读 44
收藏 19

一、前言

Java 集合类提供了一套设计良好的支持对一组对象进行操作的接口和类,JAVA常用的集合接口有4类,分别是:

  • Collection:代表一组对象,每一个对象都是它的子元素
  • Set:不包含重复元素的 Collection
  • List:有顺序的 collection,并且可以包含重复元素
  • Map:可以把键(key)映射到值(value)的对象,键不能重复。

JAVA集合的类关系可以用图表示如下:

类图说明:

  • 实线边框是实现类,比如:ArrayList,LinkedList,HashMap等。
  • 折线边框是抽象类,比如:AbstractCollection,AbstractList,AbstractMap等。
  • 点线边框的是接口,比如:Collection,Iterator,List等
  • 带颜色框的是工具类,比如:Collections,Arrays。

通过类图我们知道,所有的集合都继承了Iterator接口,也就是说,所有的集合都具有迭代器,可以通过迭代器去循环,事实上,很多集合的功能都是依托于迭代器去实现的。

二、ArrayList常用方法

方法名功能
size()返回当前集合的元素个数
isEmpty()判断当前集合是否是空元素
contains(Object o)判断当前集合是否包含某个对象
indexOf(Object o)获取某个对象位于集合的索引位置
lastIndexOf(Object o)获取最后一个位于集合的索引位置
get(int index)获取指定位置的集合对象
set(int index, E element)覆盖集合某个位置的对象
add(E e)添加对象进入集合
add(int index, E element)添加对象进入集合指定位置
remove(int index)移除索引位置的元素
remove(Object o)移除某个元素

我们一般使用ArrayList最常用的方法无非就是添加,查询和删除。我们接下来从源码层面上分析下ArrayList是如何进行添加,查询和删除的。

ArrayList源码属性

//默认容量长度
private static final int DEFAULT_CAPACITY = 10;
//空元素数组
private static final Object[] EMPTY_ELEMENTDATA = {};
//默认容量的空元素数组
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
//存储对象的数组
transient Object[] elementData;
//集合的大小
private int size;

ArrayList构造方法

//指定容量构造方法
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);
        }
    }
//默认无参数构造方法
 public ArrayList() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }

//指定集合构造方法
 public ArrayList(Collection<? extends E> c) {
        elementData = c.toArray();
        if ((size = elementData.length) != 0) {
            // c.toArray might (incorrectly) not return Object[] (see 6260652)
            //官方的一个bug,c.toArray()可能不是一个object数组,所以需要通过Arrays.copyOf创建1个Object[]数组,这样数组中就可以存放任意对象了
            if (elementData.getClass() != Object[].class)
                elementData = Arrays.copyOf(elementData, size, Object[].class);
        } else {
            // replace with empty array.
            this.elementData = EMPTY_ELEMENTDATA;
        }
    }    

通过上面ArrayList的构造方法我们知道,ArrayList可以创建指定长度的list,也可以指定一个集合创建list,而默认的创建list是一个长度为10 的空数组。

ArrayList的add()方法


 public boolean add(E e) {
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        elementData[size++] = e;
        return true;
    }
    
// 确认能否装得下size+1的对象
 private void ensureCapacityInternal(int minCapacity) {
        ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
    }
//计算容量
 private static int calculateCapacity(Object[] elementData, int minCapacity) {
        //如果是默认长度,就比较默认长度和size+1,取最大值
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            return Math.max(DEFAULT_CAPACITY, minCapacity);
        }
        return minCapacity;
    }

 private void ensureExplicitCapacity(int minCapacity) {
        modCount++;

        // overflow-conscious code
        //如果容量大于数组的长度
        if (minCapacity - elementData.length > 0)
            //扩容
            grow(minCapacity);
    }
private void grow(int minCapacity) {
        //取数组的长度
        int oldCapacity = elementData.length;
        //计算新长度,新长度=旧长度+旧长度/2
        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的实际默认容量直到调用add()方法才会真正扩容到10,这里通过new ArrayList()在内存分配的是一个空数组,并没有直接new Object[10],这样设计是很巧妙的,可以节省很多空间。

ArrayList的add(int index, E element)方法

 public void add(int index, E element) {
    //判断是否越界
        rangeCheckForAdd(index);

        ensureCapacityInternal(size + 1);  // Increments modCount!!
    // 重新复制数组,把index+1位置往后的对象全部后移
        System.arraycopy(elementData, index, elementData, index + 1,
                         size - index);
        //覆盖index位置的对象                 
        elementData[index] = element;
        size++;
    }

ArrayList的指定位置添加对象方法,需要把指定位置后面的全部对象后移,所以这样也是ArrayList相对于linkList添加耗时的地方。

ArrayList的get(int index)方法

   public E get(int index) {
        rangeCheck(index);

        return elementData(index);
    }

ArrayList的get(int index) 方法比较简单,只有两步,第一,检查是否越界,第二,返回数组索引位置的数据。

ArrayList的remove(int index)方法

  public E remove(int index) {
        rangeCheck(index);
        
        //父类的属性,用来记录list修改的次数,后续迭代器中会用到
        modCount++;
        E oldValue = elementData(index);

        int numMoved = size - index - 1;
        if (numMoved > 0)
        //把index位置后面的元素左移
            System.arraycopy(elementData, index+1, elementData, index,
                             numMoved);
        elementData[--size] = null; // clear to let GC do its work

        return oldValue;
    }

ArrayList 的remove(int index)方法主要分为 3步,第一步,判断下标是否越界,第二步,记录修改次数,并左移index位置后面的元素,第三,把最后位置赋值为null,用于快速垃圾回收。

ArrayList在循环中使用remove方法需要注意的问题

  • for循环
   List<Integer> integers = new ArrayList<>(5);
        integers.add(1);
        integers.add(2);
        integers.add(3);
        integers.add(4);
        integers.add(5);

        for (int i = 0; i < integers.size(); i++) {
            integers.remove(i);
        }
        System.out.println(integers.size());


这里首先申明一个长度为5的ArrayList的集合,然后添加五个元素,最后通过循环遍历删除,理论结果输出0,但是输出的结果却是2,为什么呢?之前分析remove源码我们知道,ArrayList每删除一次就会把后面的全部元素左移,以这5个元素为例,第一个正常删除没问题,删除后,元素就只剩下[2,3,4,5],这个时候remove(1),还剩[2,4,5],再remove(2),剩下[2,4],后面再remove没有元素了,所以最后size为2。

  • foreach循环
  List<Integer> integers = new ArrayList<>(5);
        integers.add(1);
        integers.add(2);
        integers.add(3);
        integers.add(4);
        integers.add(5);

        for (Integer integer : integers) {
            integers.remove(integer);
        }
        System.out.println(integers.size());

这段代码只是在上面的代码上面把for循环改成了foreach循环,这里理论结果也是输出0,但是最后却报错了,报错信息:

Exception in thread "main" java.util.ConcurrentModificationException
	at java.util.ArrayList$Itr.checkForComodification(ArrayList.java:909)
	at java.util.ArrayList$Itr.next(ArrayList.java:859)

这里我们发现是ArrayList的迭代器方法,ArrayList$Itr说明是ArrayList的内部类Itr中checkForComodification出问题了,我查看下源码,

//这是Itr内部的属性,初始化等于ArrayList中的modCount
int expectedModCount = modCount;

final void checkForComodification() {
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();
        }

看到这里我们应该清楚了,我们调用ArrayList的remove方法,modCount的值修改了,但是迭代器中expectedModCount值没有修改,所以就抛出异常了。这时候肯定有人说,你这个是骗人的,我写的foreach删除就不会报错!恩,对!有一种情况是不会报错的,就是list中只有两个元素时,比如这样:

   List<Integer> integers = new ArrayList<>(5);
        integers.add(1);
        integers.add(2);

        for (Integer integer : integers) {
            integers.remove(integer);
        }
        System.out.println(integers.size());
    }

这时候输出结果为1,没有报错,为什么呢?我们知道foreach是for循环的增强,内部是通过迭代器实现的,看到刚刚报错的代码也证实了我们的猜想,所以,迭代器删除,过程是这样的,先判断iterator.hasNext(),迭代器有没有下一个元素,如果有就遍历,遍历就会调用iterator.next(),该源码如下:

 public boolean hasNext() {
            return cursor != size;
        }

  public E next() {
            checkForComodification();
            int i = cursor;
            if (i >= size)
                throw new NoSuchElementException();
            Object[] elementData = ArrayList.this.elementData;
            if (i >= elementData.length)
                throw new ConcurrentModificationException();
            cursor = i + 1;
            return (E) elementData[lastRet = i];
        }

我们查看源码发现,以上过程只有调用next()会进行 checkForComodification(),当我们删除了第一个元素时候,进入循环判断,hasNext这个时候为false,不会调用next(),所以也就不会执行checkForComodification(),所以就能输出1。

三、总结

  • ArrayList可以指定容量实例化,也可以指定一个集合内容初始化,默认初始化长度是10(在执行add方法后才会给真正的空间),
  • ArrayList指定位置添加和删除,都会改变该位置之后的元素位置。
  • ArrayList在循环中进行remove时候需要注意报错和下标的问题,建议用迭代器删除是最好的

推荐阅读

Java锁之ReentrantLock(一)

Java锁之ReentrantLock(二)

Java锁之ReentrantReadWriteLock

JAVA NIO编程入门(一)

JAVA NIO 编程入门(二)

JAVA NIO 编程入门(三)

© 著作权归作者所有

木木匠
粉丝 105
博文 30
码字总数 65486
作品 0
广州
高级程序员
私信 提问
从 Java 代码到 Java 堆

从 Java 代码到 Java 堆 分析是一种美德,PS原文地址:http://www.ibm.com/developerworks/cn/java/j-codetoheap/ 理解和优化您的应用程序的内存使用 本文将为您提供 Java™ 代码内存使用情况...

北极之北
2016/03/10
736
3
一份关于 Java、Kotlin 与 Android 的学习笔记

JavaKotlinAndroidLearn 这是一份关于 Java 、Kotlin 、Android 的学习笔记,既包含对基础知识点的介绍,也包含对一些重要知识点的源码解析,笔记的大纲如下所示: Java 重拾Java(0)-基础知...

叶应是叶
2018/08/08
0
0
[Java] 从Java内核看性能分析与设计

引言 Java语言自90年代出现以来,因为它的安全性和跨平台性(即所谓的”Write Once,Run Anywhere”)等特点,深得广大程序员的青睐,但是同时,Java程序的运行效率问题也是程序员的心病。Jav...

长平狐
2012/11/19
285
0
【转】115个Java面试题和答案——终极列表

本文我们将要讨论Java面试中的各种不同类型的面试题,它们可以让雇主测试应聘者的Java和通用的面向对象编程的能力。下面的章节分为上下两篇,第一篇将要讨论面向对象编程和它的特点,关于Jav...

一只死笨死笨的猪
2014/09/30
109
0
折腾Java设计模式之迭代器模式

迭代器模式 Provide a way to access the elements of an aggregate object sequentially without exposing its underlying representation. 提供一种不公示其底层细节(结构)的情况下能顺序访......

大萌小路
03/08
18
0

没有更多内容

加载失败,请刷新页面

加载更多

rime设置为默认简体

转载 https://github.com/ModerRAS/ModerRAS.github.io/blob/master/_posts/2018-11-07-rime%E8%AE%BE%E7%BD%AE%E4%B8%BA%E9%BB%98%E8%AE%A4%E7%AE%80%E4%BD%93.md 写在开始 我的Arch Linux上......

zhenruyan
今天
5
0
简述TCP的流量控制与拥塞控制

1. TCP流量控制 流量控制就是让发送方的发送速率不要太快,要让接收方来的及接收。 原理是通过确认报文中窗口字段来控制发送方的发送速率,发送方的发送窗口大小不能超过接收方给出窗口大小。...

鏡花水月
今天
10
0
OSChina 周日乱弹 —— 别问,问就是没空

Osc乱弹歌单(2019)请戳(这里) 【今日歌曲】 @tom_tdhzz :#今日歌曲推荐# 分享容祖儿/彭羚的单曲《心淡》: 《心淡》- 容祖儿/彭羚 手机党少年们想听歌,请使劲儿戳(这里) @wqp0010 :周...

小小编辑
今天
1K
11
golang微服务框架go-micro 入门笔记2.1 micro工具之micro api

micro api micro 功能非常强大,本文将详细阐述micro api 命令行的功能 重要的事情说3次 本文全部代码https://idea.techidea8.com/open/idea.shtml?id=6 本文全部代码https://idea.techidea8....

非正式解决方案
今天
5
0
Spring Context 你真的懂了吗

今天介绍一下大家常见的一个单词 context 应该怎么去理解,正确的理解它有助于我们学习 spring 以及计算机系统中的其他知识。 1. context 是什么 我们经常在编程中见到 context 这个单词,当...

Java知其所以然
昨天
9
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部