一帆磨砺

生活所迫，一叶孤舟

0%

源码阅读-ArrayList

发表于 更新于 分类于 阅读次数： Valine：

Tips：

  1. 如果要在集合中使用自定义类，建议重写equals函数
  2. 如果集合内元素较多，使用结束后建议清空（GC）
  3. BitSet
  4. ArrayList是非线程安全的

    继承实现关系图

    ArrayList
    蓝色实线为继承，绿色虚线为实现

    参数解释

参数 释义
DEFAULT_CAPACITY 默认容量
EMPTY_ELEMENTDATA 创建大小为空实例时使用的空数组
DEFAULTCAPACITY_EMPTY_ELEMENTDATA 给无参构造函数使用
elementData 数据数组
size 实际大小
MAX_ARRAY_SIZE 值为(Integer.MAX_VALUE - 8)，主要防止自动扩容时，申请空间过大
modCount 默认为0，统计集合的修改次数，也可用于线程安全判断

创建实例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
//创建指定大小容量实例
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)
        if (elementData.getClass() != Object[].class)
            elementData = Arrays.copyOf(elementData, size, Object[].class);
    } else {
        // replace with empty array.
        this.elementData = EMPTY_ELEMENTDATA;
    }
}

添加元素

单元素添加
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
//按顺序添加元素
public boolean add(E e) {
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    elementData[size++] = e;
    return true;
}

//每次添加元素之前都会进行容量检查，当容量不足时进行扩容
private void ensureCapacityInternal(int minCapacity) {
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
    }

    ensureExplicitCapacity(minCapacity);
}

//确保集合有足够大小空间添加元素
private void ensureExplicitCapacity(int minCapacity) {
    modCount++;

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

/**
* 当最小需求大于当前集合空间容量时，进行扩容
* 大部分情况下会进行1.5倍扩容策略
* 当集合本身超过2/3的`Integer.MAX_VALUE`时，因1.5倍会超过整形最大值
* 因此会有`hugeCapacity`进行娄底，以防内存泄露
**/
private void grow(int minCapacity) {
    // overflow-conscious code
    int oldCapacity = elementData.length;
    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);
}

/**
* 当minCapacity < 0 时，意味着当前集合元素数量基本已经达到整形最大值
* 因此会直接抛出`OutOfMemoryError`
* 
* 否则进行最大化扩容
**/
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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/**
* 指定位置添加元素采用的是指定索引及之后所有元素通过拷贝进行后移
* 在直接使用数组下标直接赋值
**/
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++;
}

//校验索引是否合法
private void rangeCheckForAdd(int index) {
    if (index > size || index < 0)
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
添加集合
1
2
3
4
5
6
7
8
9
10
11
/**
* 尾部拷贝
**/
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;
}
指定位置添加集合
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/**
* 通过两次拷贝完成
* 第一次拷贝腾出指定索引后传入集合大小的空间位置
* 第二次拷贝将传入集合元素拷贝进实例
**/
public boolean addAll(int index, Collection<? extends E> c) {
    rangeCheckForAdd(index);

    Object[] a = c.toArray();
    int numNew = a.length;
    ensureCapacityInternal(size + numNew);  // Increments modCount

    int numMoved = size - index;
    if (numMoved > 0)
        System.arraycopy(elementData, index, elementData, index + numNew,
                         numMoved);

    System.arraycopy(a, 0, elementData, index, numNew);
    size += numNew;
    return numNew != 0;
}

移除元素

移除单个元素
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
/**
* 移除元素都是移除索引在前的
* 如：aaacjgllstgt
* 移除g会先移除索引为5的，再次调用才会移除后面的
* 
* 元素的判断调用了传入参数对象的equals方法，因此进行了为空区分
* 使用自定义对象建议完成equals方法的重写
**/
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
}
根据条件删除元素
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
@Override
public boolean removeIf(Predicate<? super E> filter) {
    Objects.requireNonNull(filter);
    // figure out which elements are to be removed
    // any exception thrown from the filter predicate at this stage
    // will leave the collection unmodified
    int removeCount = 0;
    final BitSet removeSet = new BitSet(size);
    final int expectedModCount = modCount;
    final int size = this.size;
    for (int i=0; modCount == expectedModCount && i < size; i++) {
        @SuppressWarnings("unchecked")
        final E element = (E) elementData[i];
        if (filter.test(element)) {
            //筛选出符合条件的待移除元素
            //并且记录该元素索引
            removeSet.set(i);
            removeCount++;
        }
    }
    if (modCount != expectedModCount) {
        //因为ArrayList不是线程安全的，该判断防止在筛选时，集合被改动
        throw new ConcurrentModificationException();
    }

    // shift surviving elements left over the spaces left by removed elements
    final boolean anyToRemove = removeCount > 0;
    if (anyToRemove) {
        final int newSize = size - removeCount;
        for (int i=0, j=0; (i < size) && (j < newSize); i++, j++) {
            //返回无需移除的元素索引
            i = removeSet.nextClearBit(i);
            //无需移除的元素留存
            elementData[j] = elementData[i];
        }
        for (int k=newSize; k < size; k++) {
            //置null多余元素
            elementData[k] = null;  // Let gc do its work
        }
        this.size = newSize;
        if (modCount != expectedModCount) {
            //因为ArrayList不是线程安全的，该判断防止在筛选时，集合被改动
            throw new ConcurrentModificationException();
        }
        modCount++;
    }
    //返回是否有移除
    return anyToRemove;
}
移除指定集合
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
/**
* 传入集合必须非 NULL
* 
**/
public boolean removeAll(Collection<?> c) {
    Objects.requireNonNull(c);
    return batchRemove(c, false);
}

/**
* c为传入集合参数，complement为移除策略
* 分移除传入集合中元素（false），还是除传入集合元素之外移除（true）
**/
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) {
            //如果有异常出现导致try中for循环中断
            //在异常位置开始拷贝，从留存索引进行保存，防止数据异常
            System.arraycopy(elementData, r,
                             elementData, w,
                             size - r);
            w += size - r;
        }
        if (w != size) {
            //如果有元素被移除，则无论是否发生异常
            //在留存元素的最后一个下标之后全部置NULL，让GC回收
            // 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;
}
保留指定集合内元素
1
2
3
4
5
//基本与移除指定集合一直，只是传参为true
public boolean retainAll(Collection<?> c) {
    Objects.requireNonNull(c);
    return batchRemove(c, true);
}
清空集合
1
2
3
4
5
6
7
8
9
10
//全员置空，空间大小不变
public void clear() {
    modCount++;

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

    size = 0;
}

查找元素

是否包含元素
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public boolean contains(Object o) {
    return indexOf(o) >= 0;
}

/**
* 如果传入NULL，返回第一个null索引
* 如果不为null，使用传入参数对象的equals函数，返回第一个相等元素索引
**/
public int indexOf(Object o) {
    if (o == null) {
        for (int i = 0; i < size; i++)
            if (elementData[i]==null)
                return i;
    } else {
        for (int i = 0; i < size; i++)
            if (o.equals(elementData[i]))
                return i;
    }
    return -1;
}
查找元素的最后索引
1
2
3
4
5
6
7
8
9
10
11
12
13
//从集合末尾开始查找
public int lastIndexOf(Object o) {
    if (o == null) {
        for (int i = size-1; i >= 0; i--)
            if (elementData[i]==null)
                return i;
    } else {
        for (int i = size-1; i >= 0; i--)
            if (o.equals(elementData[i]))
                return i;
    }
    return -1;
}
查找指定索引元素
1
2
3
4
5
6
7
8
9
10
public E get(int index) {
    rangeCheck(index);

    return elementData(index);
}

@SuppressWarnings("unchecked")
E elementData(int index) {
    return (E) elementData[index];
}

修改集合

修改指定索引元素
1
2
3
4
5
6
7
8
//替换后返回旧元素
public E set(int index, E element) {
    rangeCheck(index);

    E oldValue = elementData(index);
    elementData[index] = element;
    return oldValue;
}
清除多余空间
1
2
3
4
5
6
7
8
9
//清除多余空间，使得GC能够回收
public void trimToSize() {
    modCount++;
    if (size < elementData.length) {
        elementData = (size == 0)
          ? EMPTY_ELEMENTDATA
          : Arrays.copyOf(elementData, size);
    }
}
根据特殊条件置换元素
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
@Override
@SuppressWarnings("unchecked")
public void replaceAll(UnaryOperator<E> operator) {
    Objects.requireNonNull(operator);
    final int expectedModCount = modCount;
    final int size = this.size;
    for (int i=0; modCount == expectedModCount && i < size; i++) {
        //调用传入operator的apply方法处理特定元素，并返回处理结果进行替换
        elementData[i] = operator.apply((E) elementData[i]);
    }
    if (modCount != expectedModCount) {
        //因为ArrayList不是线程安全的，该判断防止在筛选时，集合被改动
        throw new ConcurrentModificationException();
    }
    modCount++;
}
根据指定规则排序
1
2
3
4
5
6
7
8
9
10
11
@Override
@SuppressWarnings("unchecked")
public void sort(Comparator<? super E> c) {
    final int expectedModCount = modCount;
    Arrays.sort((E[]) elementData, 0, size, c);
    if (modCount != expectedModCount) {
        //因为ArrayList不是线程安全的，该判断防止在筛选时，集合被改动
        throw new ConcurrentModificationException();
    }
    modCount++;
}

欢迎关注我的其它发布渠道