大厂之路的第一篇 顺序表即ArrayList
说到ArrayList 我们首先想起的是它的父类
AbstractList,以及它的兄弟LinkedList和Vector。下一篇我们再来分析它的兄弟LinkedList。
1. ArrayList的数据结构
Java语言向来望文生义，看它的名字我们就可以想到，它的底层应该是由数组实现的。为了确认这一点，我们到它的源码里面去探一探究竟。
transient Object[] elementData;
我们可以在ArrayList的源码中看到这样一个成员变量elementData,再看看官方对他的解释：
The array buffer into which the elements of the ArrayList are stored.
大概的意思就是，用于存储ArrayList元素的数组。
2. ArrayList的主要方法
上面我们了解到ArrayList是用数组来存储元素。我们知道，数组是有固定长度的，而ArrayList之类的集合是支持任意长度的数据的，所以我们可以肯定ArrayList之中肯定存在着一定的数组扩容机制。那让我们进一步深入到ArrayList的源码当中来验证我们的猜想。
2.1 ArrayList的几种构造方法
- 无参构造
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_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 {
// replace with empty array.
this.elementData = EMPTY_ELEMENTDATA;
}
}
2.2 ArrayList的常用方法
2.2.1 add方法
向尾部添加
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);
}
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);
}
add函数的整个调用过程如上所示，
- 首先确定
elementData数组的内部容量大小，看看是否需要扩容。从minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);这一行代码可以看出，默认情况下，elementData数组的大小为10.如果需要扩容的话，按照原来数组大小的1/2扩容，即如果原来是10的话，新数组的大小就是15.
int newCapacity = oldCapacity + (oldCapacity >> 1);当然如果需要扩容后超过了Integer.MAX_VALUE - 8，是会抛出异常的。扩容之后，就是将原来数组的数据，转移到新数组当中去。 - 当确定了是否需要扩容以后，最后的步骤就是将想要添加的元素，添加到数组的
size的位置,并将size加1。
elementData[size++] = e;
向指定位置添加
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++;
}
这个方法与向尾部添加元素的区别在于：
- 需要确定index的有效性，如果小于零或者是大于数组的长度都是不合理的，会直接抛出数组越界异常
- 因为涉及到向指定index添加元素，那么就意味着需要将index以后的每一个元素都向后移动一位，然后再将要添加的元素赋给指定的index。这样的话，性能其实是比较低的。
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
向尾部添加一个集合:
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;
}
向指定位置插入一个集合：
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;
}
这两个函数与上面两个函数添加一个元素类似，这里就不再做分析了。
2.2.2 remove方法
remove方法包含两个，一个是从指定位置移除，一个是移除指定对象。
我们分别看一下这两个函数：
1.从指定位置移除
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);
elementData[--size] = null; // clear to let GC do its work
return oldValue;
}
可以看到，此函数先检查索引是否合法，然后获得从数组指定位置获取到要移除的元素对象，然后再将数组中index以后的每一个元素向前移动一位，最后将最后一个元素置为null，同时减小size的大小。
2. 移除数组中指定对象
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 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
}
这个函数与上面从指定位置移除元素不同的地方在于：
- 需要遍历查找到该元素在数组中的位置，如果能找到的话直接操作数组，不需要再进行索引检查，也不需要将移除的对象返回。
3.移除所有元素
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.
4.从某一索引区间移除相应元素
protected void removeRange(int fromIndex, int toIndex) {
modCount++;
int numMoved = size - toIndex;
System.arraycopy(elementData, toIndex, elementData, fromIndex,
numMoved);
// clear to let GC do its work
int newSize = size - (toIndex-fromIndex);
for (int i = newSize; i < size; i++) {
elementData[i] = null;
}
size = newSize;
}
此函数分为以下几步操作：
- 将数组中
toIndex之后的所有元素向前移动int numMoved = size - toIndex;个位置- 然后将移动后
int newSize = size - (toIndex-fromIndex);的后面的所有位置的元素置为null，同时改变size的值
5.移除指定集合中所有元素
public boolean removeAll(Collection<?> c) {
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;
}
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;
}
我们可以看到，主要还是调用的batchRemove(Collection<?> c, boolean complement)这个函数，这个函数看名字就知道，批量删除。
主要分以下几个步骤：
- 将要移除的集合中不包含的元素都往数组的前面挪
for (; r < size; r++) if (c.contains(elementData[r]) == complement) elementData[w++] = elementData[r];
- finally中有两个
if代码块，前一个只有在发生异常的是时候才会命中，咱们不看，咱只看后面那个if。后面的if就是将数组中w后面的元素全都置为null。- 重新将size置为w。
2.2.3 获取指定元素在列表中的位置
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;
}
/**
* Returns the index of the last occurrence of the specified element
* in this list, or -1 if this list does not contain the element.
* More formally, returns the highest index <tt>i</tt> such that
* <tt>(o==null ? get(i)==null : o.equals(get(i)))</tt>,
* or -1 if there is no such index.
*/
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.2.4 获取指定索引所在位置的元素对象
E elementData(int index) {
return (E) elementData[index];
}
/**
* Returns the element at the specified position in this list.
*
* @param index index of the element to return
* @return the element at the specified position in this list
* @throws IndexOutOfBoundsException {@inheritDoc}
*/
public E get(int index) {
rangeCheck(index);
return elementData(index);
}
第一步，先检查index是否合法，然后再去从数组中取index所对应的元素对象。
2.2.5 更新指定索引所对应的元素对象
public E set(int index, E element) {
rangeCheck(index);
E oldValue = elementData(index);
elementData[index] = element;
return oldValue;
}
还是一样，先检查index的合法性，然后获取index所在位置对应的对象，然后给数组index位置重新赋值并将老的数据返回。
关于ArrayList的主要源码就分析到这了。
在文章的开头，我们有提到Vector。那Vector与ArrayList有什么异同呢？
(This class is roughly equivalent to Vector, except that it is unsynchronized.)
在ArrayList的源码开头就有对这两个List有做解释，几乎是差不多的，除了ArrayList是unsynchronized的。也就是说，ArrayList不是同步的，而Vector是同步的，同步就意味着是线程安全的，但同时性能相对较差一点。
所以，在不考虑线程安全的情况下，我们建议使用ArrayList。
OK，那今天咱就说到这！下一篇，我们来分析LinkedList。
