ArrayList源码分析jdk1.8版本

ArrayList感觉是在做项目中遇到最多的，先从添加元素开始讲起，请跟随我的思路
1.add(E e)，最常用的，其他添加元素的方法和这个方法的实现都差不多

 public boolean add(E e) {
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        elementData[size++] = e;
        return true;
    }

在添加元素之前，所有方法都会进行一次检查，是否需要进行扩容，如果在指定位置添加元素，则会调用rangeCheckForAdd(index)对index进行检查，是否越界
重点看一下ensureCapacityInternal(size + 1)方法

 private void ensureCapacityInternal(int minCapacity) {
        //这个判断是针对默认构造函数
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            //在小于10之前最大值一直都是DEFAULT_CAPACITY
            minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
        }

        ensureExplicitCapacity(minCapacity);
    }

为什么说那个if判断是针对默认构造函数的呢

默认构造函数：

 public ArrayList() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }

而Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {}
其实默认构造函数并没有对elementData进行初始化
而非默认构造函数，比如：

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);
        }
    }

是直接对elementData进行了一个初始化的
ensureCapacityInternal(int minCapacity)方法会调用ensureExplicitCapacity(minCapacity)方法

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

        // overflow-conscious code
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }

modCount记录的是对数据结构进行修改的次数
如果添加了一个数组元素以后会导致数组溢出，就会进行扩容，真正进行扩容操作的是grow()函数

private void grow(int minCapacity) {
        // overflow-conscious code
        int oldCapacity = elementData.length;
       //扩大为原来的1.5倍
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        //超过容器允许的最大值
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        // 进行数组拷贝
        elementData = Arrays.copyOf(elementData, newCapacity);
    }

所以对于调用默认构造函数时，数组的初始化是在第一次添加元素的时候调用grow()函数进行初始化的，对于已经初始化的容器，扩容以后扩大为原容器的1.5倍，而对于没有进行初始化的容器（即调用默认构造函数）初始化为10。如果扩容以后超过最大值将调用hugeCapacity(int minCapacity)方法

 private static int hugeCapacity(int minCapacity) {
        if (minCapacity < 0) // overflow
            throw new OutOfMemoryError();
        return (minCapacity > MAX_ARRAY_SIZE) ?
            Integer.MAX_VALUE :
            MAX_ARRAY_SIZE;
    }

超过最大值以后（扩容1.5被），则只能扩容为最大值的大小

还是有必要讲讲 add(int index, E element)方法的，因为这里暴露出了ArrayList的缺陷

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(E e)相同，就不累述了。在指定位置上添加元素时，会进行数组拷贝
2.get(int index)

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

        return elementData(index);
    }

方法非常简单易懂，不多说，因为是基于数组查找到所需元素，查找速度非常快

3.remove(int index)也是一个非常基本的方法

public E remove(int index) {
        //越界检查
        rangeCheck(index);
       //会对表结构进行修改，modCount进行加1操作
        modCount++;
        //获得指定位置上的元素
        E oldValue = elementData(index);
       //因为移除一个元素以后会对数组位置进行移动，这里计算了需
      要移动的距离
        int numMoved = size - index - 1;
        //数组的拷贝
        if (numMoved > 0)
            System.arraycopy(elementData, index+1, elementData, index,numMoved);
       //标记为null，不可达，让垃圾收集器进行回收
        elementData[--size] = null; 
        //返回旧值
        return oldValue;
    }

因为remove操作会修改数组的结构，所以会对modCount进行加1操作。数组上的删除操作是非常慢的，因为需要进行数组拷贝。所以ArrayList适合读多写少的场景

remove(Object o)方法

public boolean remove(Object o) {
        if (o == null) {
            for (int index = 0; index < size; index++)
                if (elementData[index] == null) {
                    fastRemove(index);
                    return true;
                }
        } else {
            for (int index = 0; index < size; index++)
                if (o.equals(elementData[index])) {
                    fastRemove(index);
                    return true;
                }
        }
        return false;
    }

这个方法就是首先找到o元素在数组中的位置，然后调用fastRemove(index)移除指定位置上的元素

private void fastRemove(int index) {
        modCount++;
        int numMoved = size - index - 1;
        if (numMoved > 0)
            System.arraycopy(elementData, index+1, elementData, index,
                             numMoved);
        elementData[--size] = null; // clear to let GC do its work
    }

为什么是fastRemove呢，就是少了一次对index的check，得瑟死了。因为你在数组中找到那个元素的位置肯定是合法的，所以不需要进行检查
从这里也可以看出，ArrayList中可以添加null值，写个测试demo
AddNull.java

public class AddNull {
    public static void main(String[] args) {
        ArrayList arrayList = new ArrayList();
        arrayList.add(null);
        System.out.println("size: " + arrayList.size());
        Object o = arrayList.get(0);
        System.out.println("o: " + o);
    }
}

运行结果：

size: 1
o: null

果然添加成功了

4.对ArrayList集合进行不正确操作可能引起的fail-fast
什么是fail-fast:
java集合中的一种错误机制。当多个线程对同一个集合的内容进行操作时，就可能会产生fail-fast事件。例如：当某一个线程A通过iterator去遍历某集合的过程中，若该集合的结构被其他线程所改变了，那么线程A访问集合时，就会抛出
ConcurrentModificationException异常，产生fail-fast事件
测试代码：TestFailFast.java

public class TestFailFast {
    public static void main(String[] args) {
        List<String> list = new ArrayList<>();
        list.add("A");
        list.add("B");
        list.add("C");
        list.add("D");

        System.out.println("没删除元素之前进行一次遍历");
        for (String s: list) {
            System.out.println(s);
        }

        //使用foreach就相当于使用迭代器
//        for (String s : list) {
//            if (s.equals("B")) {
//                list.remove(s);
//            }
//        }


        Iterator<String> iterator = list.iterator();
        while (iterator.hasNext()) {
            String s = iterator.next();
            if (s.equals("B")) {
                list.remove(s);  
            }
        }

        //删除B元素进行一次遍历
        System.out.println("删除B元素以后进行一次遍历");
        for (String s: list) {
            System.out.println(s);
        }
    }
}

程序运行结果：

没删除元素之前进行一次遍历
Exception in thread "main" java.util.ConcurrentModificationException
A
B
    at java.util.ArrayList$Itr.checkForComodification(ArrayList.java:901)
C
D
    at java.util.ArrayList$Itr.next(ArrayList.java:851)
    at TestFailFast.main(TestFailFast.java:32)

而对内容的修改是不会引起fail-fast的，对上述代码进行了修改，修改的部分代码如下：

Iterator<String> iterator = list.iterator();
        while (iterator.hasNext()) {
            String s = iterator.next();
            if (s.equals("B")) {
                list.set(1, "test");  //该方法只适用于remove方法，且是在单线程环境下
            }
        }

程序运行结果：

没删除元素之前进行一次遍历
A
B
C
D
删除B元素以后进行一次遍历
A
test
C
D

没有引起fail-fast

出现fail-fast的源码分析：
出现这个问题的原因是迭代器Iterator，Iterator是一个接口，ArrayList中Itr类实现了这个接口，这个类中的一个next()方法

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()方法，这个方法中将会抛出异常

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

当modCount != expectedModCount不等时就会抛出异常，而Itr类中的expectedModCount值等于集合未发生修改时的modCount值，Itr类中的代码：int expectedModCount = modCount;
如果此时你对集合的结构（比如调用了add(xxx)、remove(xxx)这类方法）进行了修改引起了modCount的变化，就会使两个值不相等，当调用迭代器的next()方法时就会抛出异常
在单线程的情况下，可以通过调用迭代器的remove()或add(E e)方法，对集合的结构进行修改，因为此时expectedModCount会被重新赋值，以remove()方法为例：

public void remove() {
            if (lastRet < 0)
                throw new IllegalStateException();
            checkForComodification();

            try {
                AbstractList.this.remove(lastRet);
                if (lastRet < cursor)
                    cursor--;
                lastRet = -1;
                expectedModCount = modCount;
            } catch (IndexOutOfBoundsException e) {
                throw new ConcurrentModificationException();
            }
        }

AbstractList.this.remove(lastRet)方法会调用集合的add方法
expectedModCount = modCount;重新赋值
但是这个方法有个缺陷，只适合在单线程下，多线程下避免这种情况应该使用CopyOnWriteArrayList

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