ArrayList源码解读(一)
ArrayList源码解读
属性
private static final int DEFAULT_CAPACITY = 10;//默认的初始化空间 private static final Object[] EMPTY_ELEMENTDATA = {};//空的数组用于空对象初始化 private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {}; transient Object[] elementData; //存储数组,非私有简化了嵌套类访问 private int size;//实际存储的数据量 protected transient int modCount = 0;//集合被操作次数,次数对不上抛出ConcurrentModificationException();
构造方法
设置初始空间大小的构造方法
public ArrayList(int initialCapacity) { if (initialCapacity > 0) {//大于0就构造对应长度的Object数组 this.elementData = new Object[initialCapacity]; } else if (initialCapacity == 0) {//等于0就直接赋值空的数组对象 this.elementData = EMPTY_ELEMENTDATA; } else {//小于0就抛出异常 throw new IllegalArgumentException("Illegal Capacity: "+ initialCapacity); } }
无参构造方法
public ArrayList() { this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;//直接赋值空的数组对象 }
集合子类参数的构造方法
public ArrayList(Collection<? extends E> c) { elementData = c.toArray();//参数c为实现了Collection的类,toArray为Collection接口定义方法 if ((size = elementData.length) != 0) { if (elementData.getClass() != Object[].class)//Arrays.copyOf返回类型依赖于第一个参数的类型,此处防止Arrays.copyOf不返回 Object[]类型数据,bug见https://bugs.openjdk.java.net/browse/JDK-6260652 elementData = Arrays.copyOf(elementData, size, Object[].class);//注意此处,仅拷贝实际数据长度 } else { // replace with empty array. this.elementData = EMPTY_ELEMENTDATA;//c参数集合长度为0,那么elementData赋值为空的数组对象 } }
基础方法
trimToSize elementData长度修剪到实际存储数据长度
public void trimToSize() { modCount++;//操作数+1 if (size < elementData.length) {//如果实际存储数量小于elementData长度 elementData = (size == 0) ? EMPTY_ELEMENTDATA//如果实际存储为0,那么elementData赋值为空的数组对象 : Arrays.copyOf(elementData, size);//否则拷贝实际存储的长度的数据 } }
ensureCapacity 确保elementData至少可以容纳minCapacity个数据
public void ensureCapacity(int minCapacity) { if ( minCapacity > elementData.length//最低容纳数量大于当前elementData长度 && !(elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA&& minCapacity <= DEFAULT_CAPACITY)//elementData不等于空数组对象并且最低容纳量大于默认空间(10) ) { modCount++;//操作数+1 grow(minCapacity);//符合条件则扩展数组 } }
grow 扩展数组
private Object[] grow() { return grow(size + 1);//按照实际存储数据量+1来扩展 }
grow(int minCapacity) 扩展数组
private Object[] grow(int minCapacity) { return elementData = Arrays.copyOf(elementData, newCapacity(minCapacity));//复制数组,长度为newCapacity(minCapacity)的返回 }
newCapacity(int minCapacity) 返回至少与给定最小容量一样大的容量
private int newCapacity(int minCapacity) { // overflow-conscious code int oldCapacity = elementData.length;//获取旧elementData长度 int newCapacity = oldCapacity + (oldCapacity >> 1);//新的长度为旧的1.5倍 if (newCapacity - minCapacity <= 0) {//如果新的长度比最小容量小 if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) return Math.max(DEFAULT_CAPACITY, minCapacity);//如果elementData是空的,返回10和最小容量中比较大的一个 if (minCapacity < 0) // overflow throw new OutOfMemoryError();//最小容量不允许为负数 return minCapacity;//如果新的长度比最小容量小,那么直接返回最小容量 } return (newCapacity - MAX_ARRAY_SIZE <= 0)//如果新的长度比最大长度小,那么返回新的容量,否则返回hugeCapacity(minCapacity)返回值 ? newCapacity : hugeCapacity(minCapacity); }
hugeCapacity(int minCapacity) 返回大的的容量
private static int hugeCapacity(int minCapacity) { if (minCapacity < 0) // overflow throw new OutOfMemoryError();//最小容量不允许为负数 return (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE//如果最小容量大于MAX_ARRAY_SIZE返回Integer的最大值 : MAX_ARRAY_SIZE;//否则返回MAX_ARRAY_SIZE (MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;) }
size 返回实际存储的数据数
public int size() { return size; }
isEmpty 判断实际存储的数据是否为空
public boolean isEmpty() { return size == 0; }
contains 判断一个元素是否存在
public boolean contains(Object o) { return indexOf(o) >= 0; }
indexOf 获取一个元素位置
public int indexOf(Object o) { return indexOfRange(o, 0, size); }
indexOfRange(Object o, int start, int end) 范围内查询目标数据在集合中的位置
int indexOfRange(Object o, int start, int end) { Object[] es = elementData; if (o == null) {//如果目标数据为空 for (int i = start; i < end; i++) {//从start循环到end if (es[i] == null) { return i;//如果数据为null,则返回对应的下标 } } } else {//目标数据不为空 for (int i = start; i < end; i++) {//从start循环到end if (o.equals(es[i])) {//调用的是目标函数的equals方法,这很重要 return i; } } } return -1; }
lastIndexOf(Object o) 查找元素最后一次出现位置
public int lastIndexOf(Object o) { return lastIndexOfRange(o, 0, size); }
lastIndexOfRange(Object o, int start, int end) 范围内查询元素最后一次出现位置(即逆第一次出现位置)
int lastIndexOfRange(Object o, int start, int end) { Object[] es = elementData; if (o == null) {//如果目标数据为空 for (int i = end - 1; i >= start; i--) {//从end-1 if (es[i] == null) { return i; } } } else { for (int i = end - 1; i >= start; i--) { if (o.equals(es[i])) {//调用的是目标函数的equals方法,这很重要 return i; } } } return -1; }
clone() 克隆集合
public Object clone() { try { ArrayList<?> v = (ArrayList<?>) super.clone(); v.elementData = Arrays.copyOf(elementData, size);//克隆出elementData长度为实际元素长度 v.modCount = 0; return v; } catch (CloneNotSupportedException e) { // this shouldn't happen, since we are Cloneable throw new InternalError(e); } }
toArray() 返回数组
public Object[] toArray() { return Arrays.copyOf(elementData, size);//仅返回实际元素长度的数组 }
toArray(T[] a) 返回数组
public <T> T[] toArray(T[] a) { if (a.length < size) // Make a new array of a's runtime type, but my contents: return (T[]) Arrays.copyOf(elementData, size, a.getClass()); System.arraycopy(elementData, 0, a, 0, size); if (a.length > size) a[size] = null;//如果传入的数组长度大于集合实际存储数目,那么将a数组size位置空后返回(不理解) return a; }
get(int index) 或许元素
public E get(int index) { Objects.checkIndex(index, size);//确认index>0,且index<size,否则抛出IndexOutOfBoundsException return elementData(index); }
set(int index, E element) 设置元素值
public E set(int index, E element) { Objects.checkIndex(index, size);//确认index>0,且index<size,否则抛出IndexOutOfBoundsException E oldValue = elementData(index);//获取旧值 elementData[index] = element;//设置新值 return oldValue;//返回旧值 }
elementData(int index) 获取元素
E elementData(int index) { return (E) elementData[index]; }
elementAt(Object[] es, int index) 获取传入数组的index位元素
static <E> E elementAt(Object[] es, int index) { return (E) es[index]; }
add(E e) 添加元素到集合里(尾插入)
public boolean add(E e) { modCount++; add(e, elementData, size); return true;//注意这里永远返回true }
add(E e, Object[] elementData, int s) 添加元素到集合里
private void add(E e, Object[] elementData, int s) { if (s == elementData.length) elementData = grow();//满了就扩容 elementData[s] = e;//把s位值设置为e, s一定会是空的 size = s + 1;//手动将实际元素数+1 }
add(int index, E element) 将元素插入到固定位置(中部插入)
public void add(int index, E element) { rangeCheckForAdd(index);//确认index>0,且index<size,否则抛出IndexOutOfBoundsException modCount++; final int s; Object[] elementData; if ((s = size) == (elementData = this.elementData).length) elementData = grow();//如果满了就扩容 System.arraycopy(elementData, index, elementData, index + 1, s - index);//复制index位开始的元素到index+1位,即index位开始元素全部往后挪1位 elementData[index] = element;//index位赋值为element size = s + 1;//手动将实际元素数+1 }
remove(int index)删除index位处的数据
public E remove(int index) { Objects.checkIndex(index, size);//确认index>0,且index<size final Object[] es = elementData; @SuppressWarnings("unchecked") E oldValue = (E) es[index]; fastRemove(es, index);//快速删除 return oldValue;//返回旧值 }
fastRemove(Object[] es, int i)快速删除
private void fastRemove(Object[] es, int i) { modCount++; final int newSize; if ((newSize = size - 1) > i)//i在实际存储数据范围内(数组下标从0开始) System.arraycopy(es, i + 1, es, i, newSize - i);//把i+1位后的newSize - i个数据往前移一位 es[size = newSize] = null;//把末位置空 }
equals(Object o)比较对象是否相等
public boolean equals(Object o) { if (o == this) {//判断内存地址 return true; } if (!(o instanceof List)) {//不是List子类,直接返回false return false; } final int expectedModCount = modCount;//赋值期望的操作数 // ArrayList can be subclassed and given arbitrary behavior, but we can // still deal with the common case where o is ArrayList precisely boolean equal = (o.getClass() == ArrayList.class) ? equalsArrayList((ArrayList<?>) o)//是ArrayList : equalsRange((List<?>) o, 0, size);//不是ArrayList checkForComodification(expectedModCount);//确认线程安全 return equal; }
equalsArrayList(ArrayList<?> other)ArrayList判断相等
private boolean equalsArrayList(ArrayList<?> other) { final int otherModCount = other.modCount; final int s = size; boolean equal; if (equal = (s == other.size)) {//比较存储数据量 final Object[] otherEs = other.elementData;//传入的缓冲区 final Object[] es = elementData;//当前的缓冲区 if (s > es.length || s > otherEs.length) { throw new ConcurrentModificationException();//线程不安全 } for (int i = 0; i < s; i++) { if (!Objects.equals(es[i], otherEs[i])) {//比较每个元素,一个不相等就break equal = false; break; } } } other.checkForComodification(otherModCount);//查看线程是否安全 return equal; }
equalsRange(List<?> other, int from, int to)判断List相等
boolean equalsRange(List<?> other, int from, int to) { final Object[] es = elementData;//当前缓冲区 if (to > es.length) { throw new ConcurrentModificationException();//线程不安全 } var oit = other.iterator();//获取迭代器 for (; from < to; from++) { if (!oit.hasNext() || !Objects.equals(es[from], oit.next())) {//判断每个元素,跑不到oit.hasNext()为false,因为for循环会先进不来 return false; } } return !oit.hasNext();//for循环结束后oit.hasNext()必定为false,即!oit.hasNext()是true }
checkForComodification(final int expectedModCount)确认线程是否安全
private void checkForComodification(final int expectedModCount) { if (modCount != expectedModCount) { throw new ConcurrentModificationException(); } }
hashCode()返回哈希码
public int hashCode() { int expectedModCount = modCount; int hash = hashCodeRange(0, size);//范围内哈希 checkForComodification(expectedModCount);//确认线程安全 return hash; }
hashCodeRange(int from, int to)范围内哈希
int hashCodeRange(int from, int to) { final Object[] es = elementData; if (to > es.length) { throw new ConcurrentModificationException();//线程不安全 } int hashCode = 1; for (int i = from; i < to; i++) { Object e = es[i]; hashCode = 31 * hashCode + (e == null ? 0 : e.hashCode());//对象为空则取0 } return hashCode; }
boolean remove(Object o)移除一个对象
public boolean remove(Object o) { final Object[] es = elementData; final int size = this.size; int i = 0; found: { if (o == null) {//空对象 for (; i < size; i++) if (es[i] == null)//循环比对内存地址获取被删除对象下标 break found;//跳出标记found } else {//不是空对象 for (; i < size; i++) if (o.equals(es[i]))//调用要被删除对象的equals方法 break found;//跳出标记found } return false;//要删除的数据不在缓冲区中,直接返回false } fastRemove(es, i);//调用快速删除,按照下标删除 return true;//成功返回true }