ArrayList 源码分析

关于List与ArrayList，在文档中是这么说明的
List：有序集合（也称为序列 ）。 该界面的用户可以精确控制列表中每个元素的插入位置。 用户可以通过整数索引（列表中的位置）访问元素，并搜索列表中的元素。
ArrayList:可调整大小的数组实现List接口。 实现所有可选列表操作，并允许所有元素，包括null 。 除了实现List 接口之外，该类还提供了一些方法来操纵内部使用的存储列表的数组的大小。 （这个类是大致相当于Vector，不同之处在于它是不同步的）。

现在我们从源码来深入了解ArrayList的常用方法（添加，插入，删除，修改，查询），这里分析的代码是基于jdk1.8的.

先来了解一下ArrayList的几种构造方法:

// 不指定长度
public ArrayList() {
    this.elementData = DEFAULTCAPACITY_EMPTY_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);
    }
}

// 构造一个包含指定元素的列表
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 {
        // 用空数组替换
        this.elementData = EMPTY_ELEMENTDATA;
    }
}

这里有个地方挺有意思的: c.toArray might (incorrectly) not return Object[] (see 6260652)
c.toArray可能不返回Object[]，可以看这个if的逻辑也是如果不是Object[]类型则按照Object[]类型生成一个数组并且赋值给elementData。这里有必要提一下为什么需要这么处理，我先贴一段代码跑一遍

Integer[] ags = {123,4545};
List<Integer> a = Arrays.asList(ags);
List<Integer> b = new ArrayList<>(a);
fe9075cac5198faef0a25fc30cf452c.png

再贴一段代码平复下心情 (说再多不如贴代码)

Integer[] ags = {123,4545};
List<Integer> a = Arrays.asList(ags);

List<Integer> b = new ArrayList<>();
b.add(1);

System.out.println(a.toArray().getClass() == Object[].class);    // false
System.out.println(b.toArray().getClass() == Object[].class);    // true

可以看到，同样类型的两个List转成数值获取class后去问Object[]比较，得到的结果竟然是不一样的，这是因为通过Arrays转换成的List，保留了原来的类型，这样子就有问题了啊，我是Integer类型通过Arrays.asList 转成了 List ，那么我通过list.toArray 转回来的时候你特么给我个Object[]类型，那我这时候我存个String类型进去会怎么样？

Integer[] ags = new Integer[5];
ags[0] = 1;
ags[1] = 2;
List<Integer> a = Arrays.asList(ags);
Object[] test= a.toArray().clone();
test[2] = "123";

运行结果：
Exception in thread "main" java.lang.ArrayStoreException: java.lang.String

贴上BUG详情: https://bugs.java.com/bugdatabase/view_bug.do?bug_id=6260652

ArrayList 属性：

private static final int DEFAULT_CAPACITY = 10;       // 默认长度
private static final Object[] EMPTY_ELEMENTDATA = {}; // 用于空实例的共享空数组实例
transient Object[] elementData;        // 存储数据的数组
private int size;                      // 包含的元素的数量

ArrayList 方法(挑几个使用比较多的方法琢磨一下)：

add(E e)方法: 将元素添加到集合的最后面

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

// 确保add操作
private void ensureCapacityInternal(int minCapacity) {
    ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}

// 为空的话 返回默认长度
private static int calculateCapacity(Object[] elementData, int minCapacity) {
     // Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
     if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        return Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    return minCapacity;
}

private void ensureExplicitCapacity(int minCapacity) {
    modCount++;
    // 扩容
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}

// 新长度 = 旧长度 + (旧长度 * 0.5)
private void grow(int minCapacity) {
    // overflow-conscious code
    int oldCapacity = elementData.length;
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    // MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8
    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);
}

// 如果新长度大于List的最大长度
private static int hugeCapacity(int minCapacity) {
    if (minCapacity < 0) // overflow
        throw new OutOfMemoryError();
    return (minCapacity > MAX_ARRAY_SIZE) ?
        Integer.MAX_VALUE :
        MAX_ARRAY_SIZE;
}

先校验我这次add是不是超过了集合的最大长度，如果超过了，则新增一个扩容后的数组，并把原先的数组中的元素拷贝到新集合中，再把新增的元素添加到新数组中。

add[int index,E element]: 将元素添加到指定位置

public void add(int index, E element) {
    // 校验index 是否合法
    rangeCheckForAdd(index);
    // 确保add操作
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    // 如果是往最后添加，则忽略，如果是往中间插入，把index及index往后的元素向后移动
    System.arraycopy(elementData, index, elementData, index + 1,
                     size - index);
    // 赋值
    elementData[index] = element;
    size++;
}

addAll(Collection<? extends E> c)：将指定集合的所有元素，按照顺序追加到集合尾部

public boolean addAll(Collection<? extends E> c) {
    Object[] a = c.toArray();
    int numNew = a.length;
    // 确保添加
    ensureCapacityInternal(size + numNew);  // Increments modCount
    // 讲指定集合的所有元素，拷贝到集合的最后面
    System.arraycopy(a, 0, elementData, size, numNew);
    size += numNew;
    return numNew != 0;
}

remove(int index)：删除指定位置的元素

public E remove(int index) {
    // 校验index是否合法
    rangeCheck(index);
    
    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; // clear to let GC do its work

    return oldValue;
}

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

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
}

这里的逻辑跟remove(int index) 方法其实没什么区别，就加了个循环，object为null的话，就把为匹配到的首个元素给删除，然后根据该被删除元素的索引去进行移动后面元素的操作。

removeAll(Collection<>?> c)：从该列表中移除指定集合中包含的所有元素

public boolean removeAll(Collection<?> c) {
    // 校验是否为null
    Objects.requireNonNull(c);
    return batchRemove(c, false);
}


private boolean batchRemove(Collection<?> c, boolean complement) {
    final Object[] elementData = this.elementData;
    int r = 0, w = 0;
    boolean modified = false;
    try {
        // 先将不存在目标集合中的元素设置在前列
        for (; r < size; r++)
            if (c.contains(elementData[r]) == complement)
                elementData[w++] = elementData[r];
    } finally {
        // Preserve behavioral compatibility with AbstractCollection,
        // even if c.contains() throws.
        // 防止出现异常，从异常开始位置往后的元素也会被设置进不满足条件列表
        if (r != size) {
            System.arraycopy(elementData, r,
                             elementData, w,
                             size - r);
            w += size - r;
        }
        // 设置满足条件元素为null
        if (w != size) {
            // clear to let GC do its work
            for (int i = w; i < size; i++)
                elementData[i] = null;
            modCount += size - w;
            size = w;
            modified = true;
        }
    }
    return modified;
}

remove这一系列的实现，其实还是挺简单的（其实都不难 (lll￢ω￢)）

set(int,E element)：设置索引位置的值

public E set(int index, E element) {
    // 校验index
    rangeCheck(index);
    
    // 获取对应元素
    E oldValue = elementData(index);
    elementData[index] = element;
    return oldValue;
}

clear(): 清除list

public void clear() {
    modCount++;

    // clear to let GC do its work
    for (int i = 0; i < size; i++)
        elementData[i] = null;

    size = 0;
}

设置所有的元素为null，size清0

感觉也没啥其他的方法了....ArrayList就到这吧 (lll￢ω￢)

总结:
1.ArrayList是一个有序列表，允许加入null元素
2.当我们按照索引来插入/删除时，会导致数组移位，当数据量很大的时候，是很消耗性能的
3.ArrayList的最大长度是 Integer.MAX_value - 8

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