ArrayList源码解析

重点是理解ArrayList的扩容机制、底层数据结构、迭代器与快速失败（fast-fail）

1. ArrayList的成员变量

     /**
     * 默认初始容量
     */
    private static final int DEFAULT_CAPACITY = 10;

    /**
     * 调用有参构造且传参为0时使用此对象数组
     */
    private static final Object[] EMPTY_ELEMENTDATA = {};

    /**
     * 调用无参构造时使用此对象数组
     */
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

    /**
     * 实际存储元素的对象数组
     */
    transient Object[] elementData; // non-public to simplify nested class access

    /**
     * 数组的元素个数，另elementData.length才为容器的实际容量
     * @serial
     */
    public int size;

为什么要用transient修饰符来修饰elementData？

加上了transient修饰符的变量在序列化的时候会被忽略，由于elementData的长度并不等于实际元素的个数，所以如果按照elementData的长度来序列化，就会浪费内存空间；

2. ArrayList构造器

(1).ArrayList的无参构造方法并没有生成容量为10的数组；
(2).elementData对象是ArrayList集合底层保存元素的实现；
(3).size属性记录了ArrayList集合中实际元素的个数；
(4).ArrayList的扩容因子为1，扩容后容量=原容量+原容量>>1；

(1). 指定初始容量的构造方法

public ArrayList(int initialCapacity) {
        if (initialCapacity > 0) {
            this.elementData = new Object[initialCapacity];//赋值给elementData用于存储实际元素
        } else if (initialCapacity == 0) {
            this.elementData = EMPTY_ELEMENTDATA;//initialCapacity为0时
        } else {
            throw new IllegalArgumentException("Illegal Capacity: "+
                    initialCapacity);
        }
    }

(2). 无参构造

public ArrayList() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;//默认空数组，此时elementData.length依然为0
}

(3). 传入Collection的构造方法

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

3. ArrayList的扩容机制

在jdk1.7和1.8中，ArrayList的无参构造并没有生成容量为10的数组，而是在第一次添加元素的时候，会判断ArrayList中的ElementData对象是空数组还是含有元素，如果是空数组则调用ensureExplicitCapacity方法给list进行首次扩容为10，往后只要元素每超过上次设定的最小容量(elementData.length) ，就会扩容，扩容后的容量为：elementData.length + elementData.length>>1

//添加元素e
public boolean add(E e) {
    ensureCapacityInternal(size + 1);//见下详解
    //将对应角标下的元素赋值为e：
    elementData[size++] = e;
    return true;
}
//得到最小扩容量
private void ensureCapacityInternal(int minCapacity) {
    //如果此时ArrayList是空数组,则将最小扩容大小设置为10：
    if (elementData == EMPTY_ELEMENTDATA) {
        minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    //判断是否需要扩容，见下详解
    ensureExplicitCapacity(minCapacity);
}
//判断是否需要扩容
private void ensureExplicitCapacity(int minCapacity) {
    //操作数+1
    modCount++;
    //判断最小扩容容量-数组大小是否大于0：
    if (minCapacity - elementData.length > 0)
        //扩容，见下详解
        grow(minCapacity);
}
//ArrayList动态扩容的核心方法:
private void grow(int minCapacity) {
    //获取现有数组大小：
    int oldCapacity = elementData.length;
    //位运算，得到新的数组容量大小，为原有的1.5倍：
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    //如果新扩容的大小依旧小于传入的容量值，那么将传入的值设为新容器大小：
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;

    //如果新容器大小，大于ArrayList最大长度：
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        //计算出最大容量值：
        newCapacity = hugeCapacity(minCapacity);
    //数组复制：
    elementData = Arrays.copyOf(elementData, newCapacity);
}
//计算ArrayList最大容量：
private static int hugeCapacity(int minCapacity) {
    if (minCapacity < 0)
        throw new OutOfMemoryError();
    //如果新的容量大于MAX_ARRAY_SIZE。将会调用hugeCapacity将int的最大值赋给newCapacity:
    return (minCapacity > MAX_ARRAY_SIZE) ?
            Integer.MAX_VALUE :
            MAX_ARRAY_SIZE;
}

Arrays.copy() 与 System.arraycopy

public static <T,U> T[] copyOf(U[] original, int newLength, Class<? extends T[]> newType) {
        @SuppressWarnings("unchecked")
        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;
    }

其中System.arraycopy：

public static native void arraycopy(Object src:源数组,  int  srcPos:源数组中的起始位置,
                                        Object dest:目标数组, int destPos:目标数据中的起始位置,
                                        int length:要复制的数组元素的数量);

Arrays.copy() 与 System.arraycopy的主要区别在于：Arrays.copy()不仅仅拷贝数组元素，还会新建一个新的数组，而System.arrayCopy方法是将元素拷贝到一个已存在的数组当中。

其中Arrays.copy()的Array.newInstance方法用于创建动态数组，如下示例：

package com.yiibai;
import java.lang.reflect.Array;

public class ArrayDemo {
   public static void main(String[] args) {
      String[] stringArray = (String[]) Array.newInstance(String.class, 3);

      Array.set(stringArray, 0, "Mahesh");
      Array.set(stringArray, 1, "Ramesh");
      Array.set(stringArray, 2, "Suresh");

      System.out.println("stringArray[0] = " + Array.get(stringArray, 0));
      System.out.println("stringArray[1] = " + Array.get(stringArray, 1));
      System.out.println("stringArray[2] = " + Array.get(stringArray, 2));
   }
}

编译并运行上面的程序，将产生以下结果 -

stringArray[0] = Mahesh
stringArray[1] = Ramesh
stringArray[2] = Suresh

4. 迭代器 Iterator

public Iterator<E> iterator() {
    return new Itr();
}
/**
 * An optimized version of AbstractList.Itr
 */
private class Itr implements Iterator<E> {
    int cursor;       // index of next element to return //默认是0
    int lastRet = -1; // index of last element returned; -1 if no such  //上一次返回的元素 (删除的标志位)
    int expectedModCount = modCount; //用于判断集合是否修改过结构的 标志

    public boolean hasNext() {
        return cursor != size;//游标是否移动至尾部
    }

    @SuppressWarnings("unchecked")
    public E next() {
        checkForComodification();
        int i = cursor;
        if (i >= size)//判断是否越界
            throw new NoSuchElementException();
        Object[] elementData = ArrayList.this.elementData;
        if (i >= elementData.length)//再次判断是否越界，在 我们这里的操作时，有异步线程修改了List
            throw new ConcurrentModificationException();
        cursor = i + 1;//游标+1
        return (E) elementData[lastRet = i];//返回元素 ，并设置上一次返回的元素的下标
    }

    public void remove() {//remove 掉 上一次next的元素
        if (lastRet < 0)//先判断是否next过
            throw new IllegalStateException();
        checkForComodification();//判断是否修改过

        try {
            ArrayList.this.remove(lastRet);//删除元素 remove方法内会修改 modCount 所以后面要更新Iterator里的这个标志值
            cursor = lastRet; //要删除的游标
            lastRet = -1; //不能重复删除 所以修改删除的标志位
            expectedModCount = modCount;//更新 判断集合是否修改的标志，
        } catch (IndexOutOfBoundsException ex) {
            throw new ConcurrentModificationException();
        }
    }
    //判断是否修改过了List的结构，如果有修改，抛出异常
    final void checkForComodification() {
        if (modCount != expectedModCount)
            throw new ConcurrentModificationException();
    }
}

二、LinkedList

基础结构

在LinkedList中，内部类Node对象最为重要，它组成了LinkedList集合的整个链表，分别指向上一个点、下一个结点，存储着集合中的元素；每一个元素对应着一个Node对象，这个对象里面有三个成员变量，一个是item，用于存储当前元素；一个是prev用于指向上一个Node，还有一个是next用于指向它下一个Node

add()

LinkedList的添加方法，主要分为2种，一是直接添加一个元素，二是在指定角标下添加一个元素；

  • add(E e)底层调用linkLast(E e)方法，就是在链表的最后面插入一个元素；

  • add(int index, E element)，插入的角标如果==size，则插入到链表最后；否则，按照角标大小调用linkBefore(E e)方法插入到对应位置；

remove()

LinkedList的删除也提供了2种形式，其一是通过角标删除元素，其二就是通过对象删除元素；不过，无论哪种删除，最终调用的都是unlink来实现的，对node的指向进行修改；

set()

set(int index, E element)方法与add(int index,E element)的设计思路基本一致，都是创建新Node节点，插入到对应的角标下，修改前后节点的prev、next属性；在这个方法里面调用了一个node()方法，这个方法根据角标来判断是从前遍历还是从后开始遍历，而每次都至少要遍历半个集合，这也是LinkedList查询慢的原因。

get()

get方法里面也调用了node()方法，这个方法会返回对应节点的item

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