1. ArrayList的基本实现原理
ArrayLiST其内部用一个普通数组来存储数据，当此数组不够容纳新添加的元素的时候，则创建一个更大长度的新数组，并将原来数组中的元素复制到新数组中。
2.ArrayList主要的全局变量/常量
除了其他一般的全局变量之外，还有一个继承于父类的 modCount属性，它用来记录集合结构被修改的次数，主要应用在迭代过程中确认没有删除或添加元素的操作，防止出现重复遍历或遍历遗漏错误。
// 用来储存集合元素的数组 transient Object[] elementData; //不通过构造方法指定容量时的默认容量（向ArrayList第一次添加元素时，数组elementData的长度） private static final int DEFAULT_CAPACITY = 10; /* * 空数组，如果使用new ArrayList(0)构造方法而不向里面添加元素， * 所有这类型的ArrayList对象内部的elementData都会引用这一个静态常量。 */ private static final Object[] EMPTY_ELEMENTDATA = {}; // 集合包含的元素个数 private int size; /*修改记数器，ArrayList中不含此属性，它来自于父类AbstractList * 当动态数组的结构（添加或删除元素）发生改变时，modCount加1 */ protected transient int modCount = 0; /* * 空数组，如果使用new ArrayList()构造方法而不向里面添加元素， * 所有这类型的ArrayList对象内部的elementData都会引用这一个静态常量 */ private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
3.ArrayList构造方法
1）指定初始容量的构造方法
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); } }
2）无参构造方法，不指定初始容量,使用默认的初始容量DEFAULT_CAPACITY
public ArrayList() { this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA; }
3）带集合参数的参构造方法，初始化后将含有集合参数对应的所有元素
public ArrayList(Collection<? extends E> c) { elementData = c.toArray();//将集合转为数组 if ((size = elementData.length) != 0) { //构造参数集合c含有元素时 /* * 构造参数集合c内部数组不是Object[]，则将其转为Object[]。 * 子类型向父类型转换，是安全的转换操作 */ if (elementData.getClass() != Object[].class) elementData = Arrays.copyOf(elementData, size, Object[].class); } else { //构造参数集合c不含元素时 this.elementData = EMPTY_ELEMENTDATA; } }
4.ArrayList主要的公共方法
1）public boolean add(E e) 在尾部添加元素
先用ensureCapacityInternal（int）方法判断，当前elementData是否能够容纳新元素，若是不能将扩展数组长度，
然后再进行将新元素添加到elementData数组的下标为size的位置。添加元素后，集合元素个数多了一个，最后将size加1。
public boolean add(E e) { //先检查容量 ensureCapacityInternal(size + 1); //内部数组elementData的赋值 elementData[size++] = e; return true; }
来看ensureCapacityInternal（int）方法的实现
private void ensureCapacityInternal(int minCapacity) { // 如果是空数组，则找minCapacity 、DEFAULT_CAPACITY中较大的那个数作为最小容量 if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) { minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity); } //确保显式容量 ensureExplicitCapacity(minCapacity); }
再看ensureExplicitCapacity(minCapacity) 方法的实现。
private void ensureExplicitCapacity(int minCapacity) { modCount++; // 调用当前方法表明，一定会添加一个元素，那么让modCount加1 /* * 当数组长度确实不满足当前所需的最小容量，必须进行扩容处理。 * 直到这步才进行真正的数组扩容。扩容处理比较耗费资源， * 最好一开始指定大致的容量个数，而不至于反复扩容。 */ if (minCapacity - elementData.length > 0)// grow(minCapacity); }
再探真正执行数组扩容处理的方法 grow(int）
private void grow(int minCapacity) { int oldCapacity = elementData.length; /* * 新容量（即数组elements的长度）,是原容量的1.5倍。 * "oldCapacity >> 1"表示是oldCapacity右移一位，结果是oldCapacity的1/2 */ int newCapacity = oldCapacity + (oldCapacity >> 1); /* * 将容量扩大至原容量的1.5倍还不够时 * 就将minCapacity作为新容量 */ if (newCapacity - minCapacity < 0) newCapacity = minCapacity; /* * 若数组长度扩展超出int最大的可表示范围(MAX_ARRAY_SIZE= Integer.MAX_VALUE - 8) * hugeCapacity(int)方法的主要代码是 * "(minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE" * 即取两者最接近minCapacity的那个值，以保证数组长度尽可能小 */ if (newCapacity - MAX_ARRAY_SIZE > 0) newCapacity = hugeCapacity(minCapacity); //将原数组的元素复制到更大长度的新数组上，并让elementData引用这个新数组。 elementData = Arrays.copyOf(elementData, newCapacity); }
2）public void add(int index, E element) 在指定下标处添加元素
public void add(int index, E element) { rangeCheckForAdd(index);//检查下标是否越界 ensureCapacityInternal(size + 1); //同样地检查容量是否够 //将从index下标后（包括index）的所有元素整体向后移动一个位置 System.arraycopy(elementData, index, elementData, index + 1, size - index); //将原来index位置上的元素引用替换为新添加的元素引用 elementData[index] = element; size++; }
3） public E remove(int index) 移除指定位置的元素
public E remove(int index) { rangeCheck(index);//检查下标是否越界 modCount++; //// 移除一个元素，modCount加一； E oldValue = elementData(index); //保存原来index位置上的元素 int numMoved = size - index - 1; //计算需要移动的元素个数 if (numMoved > 0) //将从index+1下标后（包括index+1）的所有元素整体向前移动一位 System.arraycopy(elementData, index+1, elementData, index, numMoved); /* * 对于最后一个元素而言它后而已经没有元素了，也就是说没有元素能将最后一个元素覆盖， * 所以要将最后一个元素赋为null,让垃圾回收器去回收它，否则可能造成内存泄漏。 */ elementData[--size] = null; return oldValue; }
4） public E remove(Object o) 根据元素的引用移除元素
public boolean remove(Object o) { //如果为空 if (o == null) { for (int index = 0; index < size; index++) if (elementData[index] == null) { fastRemove(index); return true; } //不为空时 } else { /* * 从头至尾进行遍历，对象o与循环集合时的当前元素相等 * 则可移除当前索引位置的元素，将退出循环,返回true。 * 若遍历了所有元素都没有一个元素与o相等，则集合中没有这个元素， * 那么移除指定元素失败，返回false */ for (int index = 0; index < size; index++) if (o.equals(elementData[index])) { /* * 与remove(int)类似，fastRemove（int）只是少去了边界检查、老值保存操作， * 能更快地移除元素 */ fastRemove(index); return true; } } return false; }
5）public E set(int index, E element) 替换指定下标对应的元素
public E set(int index, E element) { rangeCheck(index); //下标边界检查 E oldValue = elementData(index); //保存index下标处的原值 elementData[index] = element;//将新元素的赋值给index下标元素 return oldValue; }
6）public E get(int index) 获取指定下标对应的元素
public E get(int index) { rangeCheck(index); return elementData(index); }
这里只罗列了6种广泛使用的API,其他的API大多基于这几个方法，或是思路大致相同，我就不一 一列举了。
5.自定义的简单动态数组
package list; import java.util.Arrays; import java.util.Iterator; import java.util.NoSuchElementException; public class DynamicArray<E> implements Iterable<E> { private Object[] elements;// 储存元素的数组 private int size = 0;// 当前动态数组中所含元素个数 private static final int DEFAULT_CAPACITY = 16;// 默认的初始容量 /* * 空数组，如果只创建DynamicArray动态数组而不向里面添加元素， * 所有这类型的DynamicArray对象内部都会引用这一个静态常量。 * 这时运用了flyweight享元模式，共享一个对象，节省内存空间 */ private static final Object[] EMPTY_ELEMENTS = {}; public boolean isEmpty() { return size == 0 ; } public DynamicArray() { elements = new Object[DEFAULT_CAPACITY]; } public DynamicArray(int capacity) { if (capacity > 0) { elements = new Object[capacity]; } else if (capacity == 0) { elements = EMPTY_ELEMENTS; } else { throw new IllegalArgumentException("DynamicArray的初始容量不能小于0"); } } //修改记数器，当动态数组的结构（添加或删除元素）发生改变时，modCount加1 private int modCount = 0; public int size() { return size; } public boolean add(E e) { modCount++;// 添加一个元素，modCount加1 ensureCapacity(size + 1);// 添加元素前先检查数组elements的容量 elements[size] = e; // 索引和长度相差1，所以不是elements[size+1]=e size++; return true; } public E set(int index, E e) { checkIndex(index); @SuppressWarnings("unchecked") E oldValue = (E) elements[index]; elements[index] = e; return oldValue; } public boolean insert(int index, E e) { checkIndex(index); ensureCapacity(size + 1); int movedNum = size - index; System.arraycopy(elements, index, elements, index + 1, movedNum); modCount++;// 添加一个元素，modCount加1 elements[index] = e; size++; return true; } // 确保最小容量 private void ensureCapacity(int minCapacity) { // 如果是空数组，则找minCapacity 、DEFAULT_CAPACITY中较大的那个数作为最小容量 if (elements == EMPTY_ELEMENTS) { minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity); } // 数组elements的长度不够，必须扩展原数组 if (elements.length < minCapacity) { expand(minCapacity); } } // 容量扩展 private void expand(int minCapacity) { int oldCapacity = elements.length; // 确保minCapacity大于内部数组elements的长度 if (oldCapacity >= minCapacity) { return; } /* * 期望的容量（即数组elements的长度）,是原容量的1.5倍， * "oldCapacity >> 1"是右移一位， 值是oldCapacity的1/2 */ int desireCapacity = oldCapacity + oldCapacity >> 1; /* * 扩展后实际的容量 若将新容量扩大至原容量的1.5倍还不够时，就将minCapacity作为新容量 */ int newCapacity = desireCapacity > minCapacity ? desireCapacity : minCapacity; elements = Arrays.copyOf(elements, newCapacity); } public E remove(int index) { checkIndex(index);// 检查下标 modCount++;// 移除一个元素，modCount加一； @SuppressWarnings("unchecked") E removedElement = (E) elements[index]; int movedNum = size - 1 - index;// 要移动的元素个数 if (movedNum > 0) System.arraycopy(elements, index + 1, elements, index, movedNum); //删除元素成功后，最后一个元素赋空，垃圾回收，集合元素个数减1. elements[--size] = null; return removedElement; } @SuppressWarnings("unchecked") public E get(int index) { checkIndex(index);// 检查下标 return (E) elements[index]; } public boolean remove(E e) { int index = -1; //如果有一个元素和准备移除的对象相等，则将此元素的索引赋为index,并退出循环 for (int i = 0; i < size; i++) { @SuppressWarnings("unchecked") E curElement = (E) elements[i]; if ((curElement == e) || (curElement != null && curElement.equals(e))) { index = i; break; } } //index为-1,表明没有要移除的这个元素 if (index == -1) { return false; } else { remove(index); return true; } } private void checkIndex(int index) { if (index < 0 || index >= size) { throw new IndexOutOfBoundsException(indexOutOfBoundsTip(index)); } } private String indexOutOfBoundsTip(int index) { return "Index [" + index + "] , Size [" + size + "]"; } @Override public Iterator<E> iterator() { return new SimpleIterator(); } /** * 迭代器内部类 * @author Administrator * */ private class SimpleIterator implements Iterator<E> { private int desireModCount = modCount;// 预期的的修改次数 private int nextIndex = 0;// 预期情况下的下个元素的索引 private int lastIndex = -1;// 实际情况下的下个元素索引 @Override public boolean hasNext() { if (nextIndex < size) { return true; } return false; } @SuppressWarnings("unchecked") @Override public E next() { if (nextIndex >= size) { throw new NoSuchElementException("迭代到尾了，没有其它元素了"); } checkModCount(); lastIndex = nextIndex;// 预期的索引和实际的索引一致 nextIndex++;// 预期的下个索引自加1 return (E) elements[lastIndex]; } @Override public void remove() { /* * 在迭代过程中连续多次移除元素，将触发这个异常 * eg:下而的代码将抛出异常 * iterator.remove(); * iterator.remove(); */ if (lastIndex == -1) { throw new IllegalStateException("在迭代过程中不能多次移除同一个元素"); } checkModCount(); DynamicArray.this.remove(lastIndex); // 调用外围类的元素移除方法 /* * DynamicArray.remove(index )方法会改变成员变量的modCount的值 * 重新赋值给SimpleIterator的成员变量desireModCount， * 使desireModCount和 modCount再次相等 */ desireModCount = modCount; /* * 当前元素被移除后，后一个元素将顶替当前元素的位置 * 所以下次遍历的索引下标还是当前迭代位置 */ nextIndex = lastIndex; /* * 每次移除元素都将lastIndex的值重新赋为-1. * 可用来检测是否在迭代器中连续执行remove()的非法操作 */ lastIndex = -1; } /* * 校验在迭代过程中，是否使用了非迭代的方式改变了当前动态数组的结构（添加或删除） */ private void checkModCount() { if (desireModCount != modCount) throw new IllegalStateException("迭代过程中DynamicArray对象的结构被改变了"); } } public static void main(String[] args) { DynamicArray<String> dyArray = new DynamicArray<String>(); dyArray.add("34"); dyArray.add("45"); dyArray.add("啥子"); dyArray.add("哈"); dyArray.add("he"); Iterator<String> itor = dyArray.iterator(); int i = 0; while (itor.hasNext()) { if (i == 2) { itor.remove(); } i++; System.out.println(itor.next()); } System.out.println(itor.next()); } }
参考：《Java编程的逻辑》马俊昌