Q&A

  1. 为什么for中不能remove，而iterator时可以？
    见foreach中不宜进行remove/add等操作
  2. 迭代是怎么实现的？
    见Java foreach原理

关联知识

  1. 本质是数组 Object[]
  2. forEach(Consumer<? super E> action) action.accept(elementData[i]) 了解下Consumer，lambda
  3. removeIf(Predicate<? super E> filter) if (filter.test(element))

要点

扩容

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
58
59
60
61
62
   /**
    * Default initial capacity. 默认容量
    */
   private static final int DEFAULT_CAPACITY = 10;

   /**
    * Shared empty array instance used for empty instances. 指定容量为0时用到
    */
   private static final Object[] EMPTY_ELEMENTDATA = {};

   /**
    * Shared empty array instance used for default sized empty instances. We
    * distinguish this from EMPTY_ELEMENTDATA to know how much to inflate when
    * first element is added. 默认构造函数用到，容量为10
    */
   private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

/**
    * The maximum size of array to allocate.
    * Some VMs reserve some header words in an array.
    * Attempts to allocate larger arrays may result in
    * OutOfMemoryError: Requested array size exceeds VM limit 受VM影响
    */
   private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

   /**
    * Increases the capacity to ensure that it can hold at least the
    * number of elements specified by the minimum capacity argument.
    *
    * @param minCapacity the desired minimum capacity
    */
   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) // 如果超过array最大值，尝试Intager最大值，不一定成功
           newCapacity = hugeCapacity(minCapacity);
       // minCapacity is usually close to size, so this is a win:
       elementData = Arrays.copyOf(elementData, newCapacity);
   }

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

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

 private static int calculateCapacity(Object[] elementData, int minCapacity) {
       if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
           return Math.max(DEFAULT_CAPACITY, minCapacity);
       }
       return minCapacity;
   }

   // minCapacity为size + 1
   private void ensureCapacityInternal(int minCapacity) {
       ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
   }

增

还有add(int,E),addAll(collection<>)等
重点是检查容量和扩容ensureCapacityInternal，在指定位置上赋值新元素

1
2
3
4
5
6
7
8
9
10
11
/**
 * Appends the specified element to the end of this list.
 *
 * @param e element to be appended to this list
 * @return <tt>true</tt> (as specified by {@link Collection#add})
 */
public boolean add(E e) {
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    elementData[size++] = e;
    return true;
}

删

  1. public E remove(int index) rangeCheck(index); 移动后续元素 最后元素赋值释放引用
  2. public boolean remove(Object o) null和非null分开处理 fastRemove（与remove不同的是，无需rangeCheck）

改

  1. public E set(int index, E element) rangeCheck;赋值；return old data

查

  1. public E get(int index) rangeCheck;return elementData(index);
    1
    2
    3
    E elementData(int index) {
        return (E) elementData[index];
    }

一些源码的解惑

batchRemove

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
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++)
                // 这里complement也很巧妙，removeAll把contains false的元素保留，retainAll把contains true的元素保留
                if (c.contains(elementData[r]) == complement) 
                    elementData[w++] = elementData[r];
        } finally {
            // Preserve behavioral compatibility with AbstractCollection,
            // even if c.contains() throws.
            // 此处是指contains抛出异常，r != size，需要把size-r个（没有被处理）的元素拷贝到w位置后
            if (r != size) {
                System.arraycopy(elementData, r,
                                 elementData, w,
                                 size - r);
                w += size - r;
            }
            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;
    }

removeIf

用了BitSet，filter test为真时，将该位BitSet设置为true

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
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];
            // filter test为真时，将该位BitSet设置为true
            if (filter.test(element)) {
                removeSet.set(i);
                removeCount++;
            }
        }
        if (modCount != expectedModCount) {
            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++) {
                // 将值为false的元素保留（前移）
                i = removeSet.nextClearBit(i);
                elementData[j] = elementData[i];
            }
            // 清除多余的空间，赋值null，去掉对对象的引用
            for (int k=newSize; k < size; k++) {
                elementData[k] = null;  // Let gc do its work
            }
            this.size = newSize;
            if (modCount != expectedModCount) {
                throw new ConcurrentModificationException();
            }
            modCount++;
        }

        return anyToRemove;
    }

replaceAll

UnaryOperator 一元操作

1
2
3
4
5
List<Integer> list = new ArrayList<Integer>();
for (int i = 0; i < 10; i++) {
    list.add(i);
}
list.replaceAll(x -> x + 10);
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
/**
 * Replaces each element of this list with the result of applying the
 * operator to that element.  Errors or runtime exceptions thrown by
 * the operator are relayed to the caller.
 * @implSpec
 * The default implementation is equivalent to, for this {@code list}:
 * <pre>{@code
 *     final ListIterator<E> li = list.listIterator();
 *     while (li.hasNext()) {
 *         li.set(operator.apply(li.next()));
 *     }
 * }</pre>
 */
@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++) {
        elementData[i] = operator.apply((E) elementData[i]);
    }
    if (modCount != expectedModCount) {
        throw new ConcurrentModificationException();
    }
    modCount++;
}

经常用到

  1. System.arraycopy(original, 0, copy, 0, Math.min(original.length, newLength));