Java容器解析——ArrayList
Java容器解析——LinkedList
Java容器解析——Hashtable
1 前言
Java的JDK中为开发者封装了各种类型的容器，以帮助开发人员提高开发效率。为了不当一名只会搬代码的码农，我们需要了解容器背后的秘密，能够更好的掌握Java。本系列开篇将从最简单的容器——ArrayList讲起。
2 ArrayList类定义
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable {
}
从ArrayList的定义可以得出：
- ArrayList<E>：说明ArrayList支持泛型。
- ArrayList继承了AbstractList。AbstractList是List接口的骨干实现，以最大限度地减少“随机访问”数据存储（如ArrayList）实现Llist所需的工作。
- implements List<E>：实现了List接口。实现了所有可选列表操作。
- implements RandomAccess：实现RandomAccess接口，说明ArrayList支持快速（通常是固定时间）随机访问。此接口的主要目的是允许一般的算法更改其行为，从而在将其应用到随机或连续访问列表时能提供良好的性能。
- implements Cloneable：实现Cloneable接口，表明其可以调用clone()方法来返回实例的field-for-field拷贝。
- implements java.io.Serializable：实现Serializable接口，说明ArrayList具有序列化功能。
3 属性值
ArrayList中主要包含以下属性，对于属性的说明在代码注释中。
// 初始化时容器的默认大小为10。
private static final int DEFAULT_CAPACITY = 10;
// 指定该ArrayList容量为0时，返回该空数组。
private static final Object[] EMPTY_ELEMENTDATA = {};
/**
* 当调用无参构造方法，返回的是该数组。刚创建一个ArrayList 时，其内数据量为0。
* 它与EMPTY_ELEMENTDATA的区别就是：该数组是默认返回的，而后者是在用户指定容量为0时返回。
*/
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
/**
* 保存添加到ArrayList中的元素。
* ArrayList的容量就是该数组的长度。
* 该值为DEFAULTCAPACITY_EMPTY_ELEMENTDATA 时，当第一次添加元素进入ArrayList中时，数组将扩容值DEFAULT_CAPACITY。
* 被标记为transient，在对象被序列化的时候不会被序列化。
*/
transient Object[] elementData;
// 容器中实际存储的元素个数
private int size;
elementData对象标记为transient，表明在对象被序列化的时候不会被序列化。那么该对象的序列化和反序列化过程就需要由ArrayList实现，下面为ArrayList中实现elementData序列化的过程。
private void writeObject(java.io.ObjectOutputStream s)
throws java.io.IOException {
// Write out element count, and any hidden stuff
int expectedModCount = modCount;
s.defaultWriteObject();
// Write out size as capacity for behavioural compatibility with clone()
s.writeInt(size);
// Write out all elements in the proper order.
for (int i = 0; i < size; i++) {
s.writeObject(elementData[i]);
}
if (modCount != expectedModCount) {
throw new ConcurrentModificationException();
}
}
/**
* Reconstitute the <tt>ArrayList</tt> instance from a stream (that is,
* deserialize it).
*/
private void readObject(java.io.ObjectInputStream s)
throws java.io.IOException, ClassNotFoundException {
elementData = EMPTY_ELEMENTDATA;
// Read in size, and any hidden stuff
s.defaultReadObject();
// Read in capacity
s.readInt(); // ignored
if (size > 0) {
// be like clone(), allocate array based upon size not capacity
ensureCapacityInternal(size);
Object[] a = elementData;
// Read in all elements in the proper order.
for (int i = 0; i < size; i++) {
a[i] = s.readObject();
}
}
}
4 构造函数
1）无参数构造，初始容量采用默认值为10
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
2）指定初始化容量为capacity
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);
}
}
3）使用集合创建
public ArrayList(Collection<? extends E> c) {
elementData = c.toArray();
if ((size = elementData.length) != 0) {
if (elementData.getClass() != Object[].class)
elementData = Arrays.copyOf(elementData, size, Object[].class);
} else {
// replace with empty array.
this.elementData = EMPTY_ELEMENTDATA;
}
}
5 核心方法
| 方法名 | 含义 | 时间复杂度 |
|---|---|---|
| get(int index) | 根据索引获取元素 | O(1) |
| add(E e) | 添加元素 | O(1) |
| add(int index, E element) | 添加元素到指定位置 | O(n) |
| remove(int index) | 删除索引为index的元素 | O(n) |
| set(int index, E element) | 设置索引为index的元素值 | O(1) |
| size() | 返回当前容器元素大小 | O(1) |
| isEmpty() | 判断容器是否为空 | O(1) |
| contains(Object o) | 判断是否包含某个元素 | O(n) |
| indexOf(Object o) | 获取某元素在列表中索引 | O(n) |
| clear() | 清空列表 | O(n) |
6 add()方法
add()方法是向集合中添加一个元素，那么在添加过程中都发生了什么呢？
/**
* 添加元素到list末尾.
*
* @param e 被添加的元素
* @return true
*/
public boolean add(E e) {
//确保list的容量大小，如果当前空间不足，容量加1。
ensureCapacityInternal(size + 1);
//将新元素添加在末尾位置
elementData[size++] = e;
return true;
}
/**
* 在制定位置插入元素。当前位置的元素和index之后的元素向后移一位
*
* @param index 即将插入元素的位置
* @param element 即将插入的元素
* @throws IndexOutOfBoundsException 如果索引超出size
*/
public void add(int index, E element) {
if (index > size || index < 0)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
//确保list的容量大小，如果当前空间不足，容量加1。
ensureCapacityInternal(size + 1);
//将index位置之后的元素后移
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
//将元素添加在index位置
elementData[index] = element;
//容量加1
size++;
}
// 数组容量检查，不够时则进行扩容
private void ensureCapacityInternal(int minCapacity) {
// 若elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA，则取minCapacity为DEFAULT_CAPACITY和参数minCapacity之间的最大值
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
ensureExplicitCapacity(minCapacity);
}
// 数组容量检查，不够时则进行扩容
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// 确保指定的最小容量 > 数组缓冲区当前的长度
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
//扩容，保证ArrayList至少能存储minCapacity个元素
private void grow(int minCapacity) {
// 获取当前数组的容量
int oldCapacity = elementData.length;
// 扩容。新的容量=当前容量+当前容量/2.即将当前容量增加一半。
int newCapacity = oldCapacity + (oldCapacity >> 1);
//如果扩容后的容量还是小于想要的最小容量
if (newCapacity - minCapacity < 0)
//将扩容后的容量再次扩容为想要的最小容量
newCapacity = minCapacity;
//如果扩容后的容量大于临界值，则进行大容量分配
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
//元素内容复制
elementData = Arrays.copyOf(elementData, newCapacity);
}
// 进行大容量分配
private static int hugeCapacity(int minCapacity) {
//如果minCapacity<0，抛出异常
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
//如果想要的容量大于MAX_ARRAY_SIZE，则分配Integer.MAX_VALUE，否则分配MAX_ARRAY_SIZE
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
}
综合上述过程：add()方法在添加元素时首先会检查容量空间是否足够，如果不够则进行扩容，扩容之后将元素添加至集合中。
7 get()方法
get()方法相对简单，不再赘述。
/**
* 返回list中索引为index的元素
*
* @param index 需要返回的元素的索引
* @return list中索引为index的元素
* @throws IndexOutOfBoundsException 如果索引超出size
*/
public E get(int index) {
// 检查是否越界
if (index >= size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
//根据索引返回元素
return (E) elementData[index];
}
8 remove()方法
remove()方法的详细说明已加在源码注释中。
/**
* 删除list中位置为指定索引index的元素
* 索引之后的元素向左移一位
*
* @param index 被删除元素的索引
* @return 被删除的元素
* @throws IndexOutOfBoundsException 如果参数指定索引index>=size，抛出一个越界异常
*/
public E remove(int index) {
//检查索引是否越界。如果参数指定索引index>=size，抛出一个越界异常
if (index >= size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
//结构性修改次数+1
modCount++;
//记录索引为inde处的元素
E oldValue = elementData(index);
// 删除指定元素后，需要左移的元素个数
int numMoved = size - index - 1;
//如果有需要左移的元素，就移动（移动后，该删除的元素就已经被覆盖了）
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
// size减一，然后将索引为size-1处的元素置为null。为了让GC起作用，必须显式的为最后一个位置赋null值
elementData[--size] = null; // clear to let GC do its work
//返回被删除的元素
return oldValue;
}
9 set()方法
/**
* 替换指定索引的元素
*
* @param 被替换元素的索引
* @param element 即将替换到指定索引的元素
* @return 返回被替换的元素
* @throws IndexOutOfBoundsException 如果参数指定索引index>=size，抛出一个越界异常
*/
public E set(int index, E element) {
//检查索引是否越界。如果参数指定索引index>=size，抛出一个越界异常
rangeCheck(index);
//记录被替换的元素
E oldValue = elementData(index);
//替换元素
elementData[index] = element;
//返回被替换的元素
return oldValue;
}
10 小结
本篇文章主要分析了ArrayList中数据的增删改查的方法，重点在于ArrarList的扩容方法。ArrayList实现相对简单，代码也不复杂，但是其中实现的各类方法需要牢记，有助于之后分析其他容器时作为比较。
