ArrayList的使用方法

1.ArrayList的初始空间大小

进入ArrayList源码中可以看到声明的初始容量(default capacity)

 /**
  * Default initial capacity.
  */
 private static final int DEFAULT_CAPACITY = 10;

从源码中我们可以得到ArrayList的初始容量为10

2.ArrayList的add()——>append操作(在最后追加)

/**
 * 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;
 }
==================================================================================
private void ensureCapacityInternal(int minCapacity) {
    // 此处获取计算容量
    ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
=================================================================================
private static int calculateCapacity(Object[] elementData, int minCapacity) {
    // 判断增加元素当前时间ArrayList中元素是否为初始空值
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        // 如果增加元素是首次增加则直接返回初始容量
        // Math.max()是获得两个数中的最大数
        return Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    // 如果当前集合中有元素，则直接返回要插入元素的索引(size+1)
    // e.g.
    // 当前集合中元素有3个，那么此时size=3，此时返回的值为3+1=4
    return minCapacity;
}
====================================================================================
private void ensureExplicitCapacity(int minCapacity) {
    // 如果当前集合容量足够，则不需要进行扩容，只需要修改该数值
    // 这个数值统计了当前集合的结构被修改的次数，主要用于迭代器
    modCount++;

    // overflow-conscious code
    // 如果当前元素插入的位置角标数大于当前集合的长度，则需要进行集合的扩容
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}
===================================================================================
/**
 * Increases the capacity to ensure that it can hold at least the
 * number of elements specified by the minimum capacity argument.
 *
 * minCapacity:所需的最小容量值
 * @param minCapacity the desired minimum capacity
 */
private void grow(int minCapacity) {
    // overflow-conscious code
    int oldCapacity = elementData.length;
    // 新值 = 当前集合长度 + 当前集合长度/2
    // e.g.
    // 当前集合长度为10，那么扩容后的长度就是：10 + 10 / 2 = 15
    // 15 + 15 / 2 = 15 + 7 = 21
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    // 如果扩容后的长度还不够最小需求容量的话直接用最小容量需求值为扩容后的值
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    // 如果后的值大于Integer最大值-8的话，那么用巨大容量
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    // minCapacity is usually close to size, so this is a win:
    // 其实就是重新new 一个ArrayList，容量为扩容后的容量，将原有元素拷贝到新集合的操作
    elementData = Arrays.copyOf(elementData, newCapacity);
}
==================================================================================
/**
 * 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
 */
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
==================================================================================
private static int hugeCapacity(int minCapacity) {
    if (minCapacity < 0) // overflow
        throw new OutOfMemoryError();
    return (minCapacity > MAX_ARRAY_SIZE) ?
        Integer.MAX_VALUE :
        MAX_ARRAY_SIZE;
}

Java中位运算符补充

经常在一些算法中看到 num >>> 1的写法，num >>> 1，相当于num除以2，为什么不直接写num除以2呢？因为计算机中的数据是以二进制的形式存储的，数学运算的加减乘除底层也是二进制移位实现的，直接在二进制上移位，显然要比数学运算来的更直接。
来看一下Java中的移位运算符，有三种:

<< : 左移运算符，num << 1，相当于num乘以2
>> : 右移运算符，num >> 1，相当于num除以2
>>> : 无符号右移运算符，num >>> 1，相当于num除以2，忽略符号位，空位都以0补齐
示例：
    int num = 8;
    int num1 = num << 1;  //num1 = 16
    int num2 = num >> 1 ;  //num2 = 4
    int num3 = num >>> 1;  //num3 = 4
注意：无符号右移运算符忽略了最高位的符号位，0补最高位，并且无符号右移运算符 >>> 只对32位和64位的数值有意义。Java中只有这三种位移，没有向左的无符号位移。
    int num = -8;
    int num1 = num << 1;  //num1 = -16
    int num2 = num >> 1 ;  //num2 = -4
    int num3 = num >>> 1;  //num3 = 21 4748 3644
为什么 num3 是 21 4748 3644 这么个数？因为数值在计算机中是以补码的形式的存储的，-8的补码是 [11111111 11111111 11111111 11111000]，右移一位则变成了 [01111111 11111111 11111111 11111100]，最高位的1表示负数，0表示正数，>>> 时0补最高位的符号位，[01111111 11111111 11111111 11111100] 的十进制就是21 4748 3644。在正数位移的时候，>> 和 >>> 是一样的，在负数位移的时候就不一样了。

3.ArrayList的add()——>增加到指定位置

/**
 * Inserts the specified element at the specified position in this
 * list. Shifts the element currently at that position (if any) and
 * any subsequent elements to the right (adds one to their indices).
 *
 * @param index index at which the specified element is to be inserted
 * @param element element to be inserted
 * @throws IndexOutOfBoundsException {@inheritDoc}
 */
public void add(int index, E element) {
    // 进行范围检查：插入的元素位置是否超出当前容器容量边界
    // eg:当前集合容量为10，元素个数也是10，那么size=10，此时index只能是0-9，容器自动扩容会在下一步完成
    rangeCheckForAdd(index);
    // 算法通追加元素一致
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    // 将要插入位置后面的size-index个元素后移
    System.arraycopy(elementData, index, elementData, index + 1,
                     size - index);
    // 将元素插入指定位置
    elementData[index] = element;
    size++;
}
===================================================================================
/**
 * A version of rangeCheck used by add and addAll.
 */
private void rangeCheckForAdd(int index) {
    if (index > size || index < 0)
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}

4.ArrayList的remove()——>指定角标

/**
 * Removes the element at the specified position in this list.
 * Shifts any subsequent elements to the left (subtracts one from their
 * indices).
 *
 * @param index the index of the element to be removed
 * @return the element that was removed from the list
 * @throws IndexOutOfBoundsException {@inheritDoc}
 */
public E remove(int index) {
    // 验证传入的角标是否在当前集合范围内
    rangeCheck(index);
    // 增加集合结构修改次数
    modCount++;
    // 要删除的元素值
    E oldValue = elementData(index);
    // 将要移动的元素数
    int numMoved = size - index - 1;
    if (numMoved > 0)
        System.arraycopy(elementData, index+1, elementData, index,
                         numMoved);
    // 让GC清除
    elementData[--size] = null; // clear to let GC do its work
    // 返回被删除的元素
    return oldValue;
}

5.ArrayList的remove()——>指定元素

/**
 * Removes the first occurrence of the specified element from this list,
 * if it is present.  If the list does not contain the element, it is
 * unchanged.  More formally, removes the element with the lowest index
 * <tt>i</tt> such that
 * <tt>(o==null&nbsp;?&nbsp;get(i)==null&nbsp;:&nbsp;o.equals(get(i)))</tt>
 * (if such an element exists).  Returns <tt>true</tt> if this list
 * contained the specified element (or equivalently, if this list
 * changed as a result of the call).
 *
 * @param o element to be removed from this list, if present
 * @return <tt>true</tt> if this list contained the specified element
 */
public boolean remove(Object o) {
    if (o == null) {
        for (int index = 0; index < size; index++)
            // 如果某个元素因为为null
            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 remove method that skips bounds checking and does not
 * return the value removed.
 */
// 该方法不会进行边界检查
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
}

6.ArrayList的clear()

可见该方法是将所有元素置为null

/**
 * Removes all of the elements from this list.  The list will
 * be empty after this call returns.
 */
public void clear() {
    modCount++;

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

    size = 0;
}