实现的接口
本文基于Oracle JDK1.8展开讨论
ArrayList位于java.util包下
ArrayList类的声明:
public class ArrayList<E> extends AbstractList<E> implements List<E>, RandomAccess, Cloneable, java.io.Serializable
ArrayList继承了AbstractList,看AbstractList源码,实现了List接口
public abstract class AbstractList<E> extends AbstractCollection<E> implements List<E>
而ArrayList再次实现了List接口,不觉得多余吗?实际上,这么设计是有原因的:
List接口里面包含了很多方法,实现了List接口的类要重新全部的方法,而且各自的实现类具体的方法实现是不一样的,比如ArrayList和LinkedList对于add的具体实现肯定是不一样的。
但是ArrayList和LinkedList对于某些方法的实现是一模一样的,比如size()方法
这时候,如果每增加一个List的实现类,都要重复的写一些方法体一模一样的方法,无法复用代码
这时候就利用了设计模式里的模板方法模式,把List的实现类的共有方法抽象到AbstractList里,并提供默认的实现,这样下层的实现类继承了AbstractList,直接继承共有的方法,而不需要重复的写一些代码
RandomAccess
此接口为一个空接口,目的是加快ArrayList随机访问的速度
public interface RandomAccess {}
Cloneable
此接口为一个空接口,实现了后可以重写clone方法实现深拷贝
public interface Cloneable {}
java.io.Serializable
此接口为一个空接口,目的是方便序列化
public interface Serializable {}
成员变量
/** * 序列化ID */ private static final long serialVersionUID = 8683452581122892189L; /** * 默认初始化容量 */ private static final int DEFAULT_CAPACITY = 10; /** * 创建一个空ArrayList时,赋值使用 */ private static final Object[] EMPTY_ELEMENTDATA = {}; /** * 默认空的数组,在初始化时使用 */ private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {}; /** * 实际存放数据的数组 */ transient Object[] elementData; // non-private to simplify nested class access /** * 数组内存放的实际元素个数 */ private int size;
构造函数
共三个构造函数
无参构造函数
public ArrayList() { this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA; } //elementData 为存放数据的数组 transient Object[] elementData; //无参初始化时,赋值为一个空的数组 private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
根据容量初始化构造函数
public ArrayList(int initialCapacity) { if (initialCapacity > 0) { //根据容量生成一个Object数组 this.elementData = new Object[initialCapacity]; } else if (initialCapacity == 0) { //参数等于0 则赋值一个空数组 this.elementData = EMPTY_ELEMENTDATA; } else { throw new IllegalArgumentException("Illegal Capacity: "+ initialCapacity); } }
根据现有List初始化构造函数
public ArrayList(Collection<? extends E> c) { elementData = c.toArray(); if ((size = elementData.length) != 0) { //如果返回的不是Object[]类型 则进行复制操作,Arrays.copyOf底层调用的System.arraycopy() if (elementData.getClass() != Object[].class) elementData = Arrays.copyOf(elementData, size, Object[].class); } else { // replace with empty array. this.elementData = EMPTY_ELEMENTDATA; } }
clone方法
public Object clone() { try { //先调用父类的clone克隆 ArrayList<?> v = (ArrayList<?>) super.clone(); //底层还是调用System.arraycopy(); v.elementData = Arrays.copyOf(elementData, size); //修改次数设置为0 v.modCount = 0; return v; } catch (CloneNotSupportedException e) { // this shouldn't happen, since we are Cloneable throw new InternalError(e); } }
get方法
```java
public E get(int index) {//首先检查index是否合法 rangeCheck(index); return elementData(index);
}
/**检查index是否合法
/
private void rangeCheck(int index) {if (index >= size) throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
/**
*返回index 位置的元素
*/
E elementData(int index) {
return (E) elementData[index];
}
### set方法 ```java public E set(int index, E element) { //检查index是否合法 rangeCheck(index); //取出旧元素 E oldValue = elementData(index); //把index位置的元素替换为新元素 elementData[index] = element; return oldValue; }
add方法:此处会产生扩容
public boolean add(E e) { //确定容量是否足够 不够则扩容 ensureCapacityInternal(size + 1); elementData[size++] = e; return true; } private void ensureCapacityInternal(int minCapacity) { //如果数组为空数组 即第一次add元素 取一个最大的Capacity if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) { minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity); } ensureExplicitCapacity(minCapacity); } private void ensureExplicitCapacity(int minCapacity) { //修改次数+1 modCount++; //如果需要的Capacity 大于当前elementData的长度 则需要扩容 if (minCapacity - elementData.length > 0) //扩容 grow(minCapacity); }
扩容机制 grow(minCapacity);
private void grow(int minCapacity) { // 记录旧容量 int oldCapacity = elementData.length; //新容量为 旧容量+ 旧容量的1/2 //这里使用了移位运算 右移一位相当于除以2 int newCapacity = oldCapacity + (oldCapacity >> 1); //取一个最大值 if (newCapacity - minCapacity < 0) newCapacity = minCapacity; //如果新容量超过Integer.MAX_VALUE - 8 则把newCapacity赋值为Integer.MAX_VALUE 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); } private static int hugeCapacity(int minCapacity) { if (minCapacity < 0) // overflow throw new OutOfMemoryError(); return (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE; }
remove方法
public E remove(int index) { //检查下标是否合法 rangeCheck(index); //修改次数+1 modCount++; //保存旧值 E oldValue = elementData(index); //删除元素后 数组需要移动的元素数量 int numMoved = size - index - 1; if (numMoved > 0) //移动数组 System.arraycopy(elementData, index + 1, elementData, index, numMoved); //置为null 方便gc elementData[--size] = null; // clear to let GC do its work return oldValue; }
clear方法
public void clear() { //修改次数+1 modCount++; // clear to let GC do its work for (int i = 0; i < size; i++) elementData[i] = null; size = 0; }
addAll方法
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; //此处的移动是把index之后的元素后移numMoved个 目的是给下面插入的元素腾出位置 if (numMoved > 0) System.arraycopy(elementData, index, elementData, index + numNew, numMoved); //把数据插入index处 System.arraycopy(a, 0, elementData, index, numNew); size += numNew; return numNew != 0; }
迭代器
public Iterator<E> iterator() { //平时使用的迭代器 实际上是ArrayList的一个内部类Itr return new Itr(); }
迭代器解析
private class Itr implements Iterator<E> { //指向下一个元素的游标 int cursor; // index of next element to return //上一个返回的元素 int lastRet = -1; // index of last element returned; -1 if no such //此处注意!!! 在获取迭代器的时候,expectedModCount只会被赋值一次 // 所以当外部的modCount改变之后,内部类的expectedModCount并不会改变 int expectedModCount = modCount; /** *判断是否有下一个元素 */ public boolean hasNext() { //直接判断游标是否==size return cursor != size; } @SuppressWarnings("unchecked") public E next() { //判断修改版本是否一致 checkForComodification(); int i = cursor; //下标大于size 抛出异常 if (i >= size) throw new NoSuchElementException(); Object[] elementData = ArrayList.this.elementData; if (i >= elementData.length) throw new ConcurrentModificationException(); //指向下一个元素 cursor = i + 1; return (E) elementData[lastRet = i]; } public void remove() { if (lastRet < 0) throw new IllegalStateException(); checkForComodification(); try { ArrayList.this.remove(lastRet); cursor = lastRet; lastRet = -1; //此处会更新修改的版本 expectedModCount = modCount; } catch (IndexOutOfBoundsException ex) { throw new ConcurrentModificationException(); } } @Override @SuppressWarnings("unchecked") public void forEachRemaining(Consumer<? super E> consumer) { Objects.requireNonNull(consumer); final int size = ArrayList.this.size; int i = cursor; if (i >= size) { return; } final Object[] elementData = ArrayList.this.elementData; if (i >= elementData.length) { throw new ConcurrentModificationException(); } while (i != size && modCount == expectedModCount) { consumer.accept((E) elementData[i++]); } // update once at end of iteration to reduce heap write traffic cursor = i; lastRet = i - 1; checkForComodification(); } //内外修改次数不一致时 此处会引起并发修改异常 final void checkForComodification() { if (modCount != expectedModCount) throw new ConcurrentModificationException(); } }
其他方法
/** * 获取元素数量 */ public int size() { return size; } /** * 判断是否为空 */ public boolean isEmpty() { return size == 0; } /** * 判断是否包含元素o 这里就是调用indexOf 看一下元素的索引是不是>0 */ public boolean contains(Object o) { return indexOf(o) >= 0; } public int indexOf(Object o) { if (o == null) { //如果对象为空 则取数组里查找第一个对象为空的索引 for (int i = 0; i < size; i++) if (elementData[i] == null) return i; } else { //不为空 则遍历数组 使用equals判断 for (int i = 0; i < size; i++) if (o.equals(elementData[i])) return i; } return -1; }
全部评论
(1) 回帖