public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
上面的函数，就是Arraylist添加一个的元素的过程。
ensureCapacityInternal(size + 1); // Increments modCount!!
从这一句来看，添加一个元素首先要做的是确保ArrayList能装下size+1个元素。那么如何确保么?下面来看看ensureCapacityInternal函数.
private void ensureCapacityInternal(int minCapacity) {
//DEFAULT_CAPACITY的值为10
//DEFAULTCAPACITY_EMPTY_ELEMENTDATA是一个空数组
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
ensureExplicitCapacity(minCapacity);
}
从代码来看，如果操作前的ArrayList.size = 0，也就是对一个空的ArrayList进行扩容，那么Arraylist默认将size扩大为DEFAULT_CAPACITY(10)和参数minCapacity中的较大值，也就是说，如果说往空的Arraylist里面添加的元素个数小于10个的话，则Arraylist默认初始化size为10。
需要强调的是，ArrayList类有两个静态变量DEFAULTCAPACITY_EMPTY_ELEMENTDATA和EMPTY_ELEMENTDATA。
/**
* Shared empty array instance used for empty instances.
*/
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.
*/
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
这两个变量都代表初始化空数组，但是DEFAULTCAPACITY_EMPTY_ELEMENTDATA是用于扩容之前的空数组，使用它一般是在第一次添加元素时，表明添加之后ArrayList要进行扩容。
然后我们看看ensureExplicitCapacity这个函数
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// overflow-conscious code
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
调用它时表明，扩容操作用于非第一次添加元素，换句话说这个时候ArrayList的size>=10.
modCount++;
modeCount是Arraylist的父类AbstractList的一个属性，它在AbstractList中的定义如下：
/**
* The number of times this list has been <i>structurally modified</i>.
* Structural modifications are those that change the size of the
* list, or otherwise perturb it in such a fashion that iterations in
* progress may yield incorrect results.
*
* <p>This field is used by the iterator and list iterator implementation
* returned by the {@code iterator} and {@code listIterator} methods.
* If the value of this field changes unexpectedly, the iterator (or list
* iterator) will throw a {@code ConcurrentModificationException} in
* response to the {@code next}, {@code remove}, {@code previous},
* {@code set} or {@code add} operations. This provides
* <i>fail-fast</i> behavior, rather than non-deterministic behavior in
* the face of concurrent modification during iteration.
*
* <p><b>Use of this field by subclasses is optional.</b> If a subclass
* wishes to provide fail-fast iterators (and list iterators), then it
* merely has to increment this field in its {@code add(int, E)} and
* {@code remove(int)} methods (and any other methods that it overrides
* that result in structural modifications to the list). A single call to
* {@code add(int, E)} or {@code remove(int)} must add no more than
* one to this field, or the iterators (and list iterators) will throw
* bogus {@code ConcurrentModificationExceptions}. If an implementation
* does not wish to provide fail-fast iterators, this field may be
* ignored.
*/
protected transient int modCount = 0;
这个字段的意义是记录ArrayList发生过多少次的结构变动。这里用到了一个很少见的关键字transient，我们都知道一个对象只要实现了Serilizable接口，这个对象就可以被序列化，java的这种序列化模式为开发者提供了很多便利，我们可以不必关系具体序列化的过程，只要这个类实现了Serilizable接口，这个类的所有属性和方法都会自动序列化。然而在实际开发过程中，我们常常会遇到这样的问题，这个类的有些属性需要序列化，而其他属性不需要被序列化，打个比方，如果一个用户有一些敏感信息（如密码，银行卡号等），为了安全起见，不希望在网络操作（主要涉及到序列化操作，本地序列化缓存也适用）中被传输，这些信息对应的变量就可以加上transient关键字。换句话说，这个字段的生命周期仅存于调用者的内存中而不会写到磁盘里持久化。
// overflow-conscious code
if (minCapacity - elementData.length > 0)
grow(minCapacity);
这段代码表明，如果添加元素后容量已经超出了ArrayList的实际容量时，需要扩容了。于是我们接着看看grow操作。
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);
}
先对容量扩大1.5倍，这里oldCapacity >> 1是二进制操作右移，相当于除以2。接再来把新的临时容量（还没正式改变容量，应该叫预期容量）和实际所需要的最小容量比较，如果还不满足，则把临时容量改成需要的最小容量值。接着再判断容量是否超过MAX_ARRAY_SIZE的值，MAX_ARRAY_SIZE值为Integer.MAX_VALUE - 8。那么为什么要用这个值呢？去google了一下，发现下面这个答案很好的解释了。
The shape and structure of an array object, such as an array of int values, is similar to that of a standard Java object. The primary difference is that the array object has an additional piece of metadata that denotes the array's size. An array object's metadata, then, consists of: Class : A pointer to the class information, which describes the object type. In the case of an array of int fields, this is a pointer to the int[] class.
Flags : A collection of flags that describe the state of the object, including the hash code for the object if it has one, and the shape of the object (that is, whether or not the object is an array).
Lock : The synchronization information for the object — that is, whether the object is currently synchronized.
Size : The size of the array.
简单来说，这里需要8个byte用来存储size的值(Integer.MAX_VALUE = 2^31 = 2,147,483,648)。
接续来看上面的代码，如果容量已经超过MAX_ARRAY_SIZE，则调用hugeCapacity方法检查容量的int值是不是已经溢出。
private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
}
最后确定了新的容量，就使用Arrays.copyOf方法来生成新的数组，copyOf也已经完成了将就的数据拷贝到新数组的工作（Arrays.copyOf是浅拷贝）.
接着我们看看在指定位置插入数据的代码：
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++;
}
首先进行rangeCheckForAdd(index)操作。
private void rangeCheckForAdd(int index) {
if (index > size || index < 0)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
如果index不合法这里会抛出IndexOutOfBoundsException。接着ensureCapacityInternal(size + 1)同样是确保添加size增加后容量够用。确保容量后，这里做了一个操作，把数组里的相关部分通过copy整个右移了一位，然后在index处添加需要添加的元素。不过为什么这里会使用Sytem.arraycopy，它的效率如何呢？由于篇幅原因，Sytem.arraycopy的分析放在下一篇文章，尽请期待。
网友评论