带你走进java集合之ArrayList

image

一、前言

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

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

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

image

类图说明：

  • 实线边框是实现类，比如：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 编程入门（三）》

©著作权归作者所有,转载或内容合作请联系作者
  • 人面猴
    序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
    沈念sama阅读 199,271评论 5赞 466
  • 死咒
    序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
    沈念sama阅读 83,725评论 2赞 376
  • 救了他两次的神仙让他今天三更去死
    文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
    开封第一讲书人阅读 146,252评论 0赞 328
  • 道士缉凶录：失踪的卖姜人
    文/不坏的土叔 我叫张陵，是天一观的道长。 经常有香客问我，道长，这世上最难降的妖魔是什么？ 我笑而不...
    开封第一讲书人阅读 53,634评论 1赞 270
  • 港岛之恋（遗憾婚礼）
    正文 为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
    茶点故事阅读 62,549评论 5赞 359
  • 恶毒庶女顶嫁案：这布局不是一般人想出来的
    文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
    开封第一讲书人阅读 47,985评论 1赞 275
  • 城市分裂传说
    那天，我揣着相机与录音，去河边找鬼。 笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。 我是一名探鬼主播，决...
    沈念sama阅读 37,471评论 3赞 390
  • 双鸳鸯连环套：你想象不到人心有多黑
    文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
    开封第一讲书人阅读 36,128评论 0赞 254
  • 万荣杀人案实录
    序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
    沈念sama阅读 40,257评论 1赞 294
  • 护林员之死
    正文 独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 35,233评论 2赞 317
  • 白月光启示录
    正文 我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 37,235评论 1赞 328
  • 活死人
    序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
    沈念sama阅读 32,940评论 3赞 316
  • 日本核电站爆炸内幕
    正文 年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
    茶点故事阅读 38,528评论 3赞 302
  • 男人毒药：我在死后第九天来索命
    文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 29,623评论 0赞 19
  • 一桩弑父案，背后竟有这般阴谋
    文/苍兰香墨 我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 30,858评论 1赞 255
  • 情欲美人皮
    我被黑心中介骗来泰国打工， 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。 一个月前我还...
    沈念sama阅读 42,245评论 2赞 344
  • 代替公主和亲
    正文 我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
    茶点故事阅读 41,790评论 2赞 339

推荐阅读更多精彩内容