集合-ArrayList解析
2017-08-18 本文已影响0人
史云龙
一、概要
- ArrayList是一个 动态数组，线程不安全的，允许值为null
- 底层数据结构是数组，采用默认构造方法创建时，创建的数组是默认长度为0的数组，第一次添加数据时会进行判断，如果数组长度为默认的空数组,则创建一个新的数组，数组长度为默认值MAX[10，新的长度]，而在Android中数组的默认最小增加长度为12,当数组长度需要增加时如果数组的长度小于12则一次性增加到12。
- 继承抽象类AbstractList，实现了List，RandomAccess，Cloneable，Serializable，其中RandomAccess表示快速访问的能力。
- 由于是底层结构是数组，所以在使用get(i)/set(index, object) 访问速度较快，时间复杂度为O(1)，但是也是因为数组的原因，导致空间效率不高。
- 添加元素和删除元素时效率都不高。如果数组是在最后的位置增加时，并没有明显的效率变化。当数组长度需要变化时，则会新创建一个原有长度1.5倍的数组，然后将原来的数组中的元素通过Arrays.copyOf()方法拷贝到新数组(实际使用的System.arraycopy()方法)，此时效率比较低。如果在其他位置添加元素，添加位置及后面的元素都需要向后移动一位，则有可能涉及到两次arraycopy，此时效率最低。在删除时，则需要将删除位置以后的元素向前移动一位，则必用到System.arraycopy。效率低下的原因则是主要受到System.arraycopy()方法的影响。
- 源码参考的Android-23和Java 1.8
二、构造函数
Java
一共三个构造函数
- 默认构造函数：数组初始化为长度为0的数组
- 参数为initialCapacity的构造函数：参数为默认初始化数组的长度
- 参数为集合的构造函数：将数组为集合转换的数组，如果转换的数组不是Object对象，就将数组转换成Object数组
//存储元素的数组
transient Object[] elementData; // non-private to simplify nested class access
//数组的长度
private int size;
/**
* Shared empty array instance used for empty instances.
*/
private static final Object[] EMPTY_ELEMENTDATA = {};
/**
* Shared empty array instance used for default sized empty instances. We
* distinguish this from EMPTY_ELEMENTDATA to know how much to inflate when
* first element is added.
* 默认的数组 ，这个数组为了区分容量为0创建的数组EMPTY_ELEMENTDATA
* 在添加的时候进行了区分，如果是这个数组，则将数组重新换成相应长度的空数组
*/
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
/**
* Constructs an empty list with the specified initial capacity.
* 带有初始容量的构造函数
* @param initialCapacity the initial capacity of the list：初始化数组容量
* @throws IllegalArgumentException if the specified initial capacity
* is negative
*/
public ArrayList(int initialCapacity) {
//初始化容量必须大于0
if (initialCapacity > 0) {
this.elementData = new Object[initialCapacity];
} else if (initialCapacity == 0) {
this.elementData = EMPTY_ELEMENTDATA;
} else {
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
}
}
/**
* Constructs an empty list with an initial capacity of ten.
* 默认的构造函数，创建了一个空数组，
*/
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
/**
* Constructs a list containing the elements of the specified
* collection, in the order they are returned by the collection's
* iterator.
*
* @param c the collection whose elements are to be placed into this list
* @throws NullPointerException if the specified collection is null
*/
public ArrayList(Collection<? extends E> c) {
elementData = c.toArray();
if ((size = elementData.length) != 0) {
// c.toArray might (incorrectly) not return Object[] (see 6260652)
// 将数组转换成Object数组
if (elementData.getClass() != Object[].class)
elementData = Arrays.copyOf(elementData, size, Object[].class);
//本质还是调用System.arraycopy
} else {
// replace with empty array.
this.elementData = EMPTY_ELEMENTDATA;
}
}
//上述 Arrays.copyOf调用的方法
public static <T,U> T[] copyOf(U[] original, int newLength, Class<? extends T[]> newType) {
//判断是否是Object方法，如果不是Object，则调用反射创建数组
@SuppressWarnings("unchecked")
T[] copy = ((Object)newType == (Object)Object[].class)
? (T[]) new Object[newLength]
: (T[]) Array.newInstance(newType.getComponentType(), newLength);
System.arraycopy(original, 0, copy, 0,
Math.min(original.length, newLength));
return copy;
}
Android
- 还是三个构造函数，但是构造函数具体实现不太一样
- 关于EmptyArray 可以参考：链接
/**
* Constructs a new instance of {@code ArrayList} with the specified
* initial capacity.
*
* @param capacity
* the initial capacity of this {@code ArrayList}.
*/
public ArrayList(int capacity) {
if (capacity < 0) {
throw new IllegalArgumentException("capacity < 0: " + capacity);
}
array = (capacity == 0 ? EmptyArray.OBJECT : new Object[capacity]);
}
/**
* Constructs a new {@code ArrayList} instance with zero initial capacity.
*/
public ArrayList() {
array = EmptyArray.OBJECT;
}
/**
* Constructs a new instance of {@code ArrayList} containing the elements of
* the specified collection.
*
* @param collection
* the collection of elements to add.
*/
public ArrayList(Collection<? extends E> collection) {
if (collection == null) {
throw new NullPointerException("collection == null");
}
Object[] a = collection.toArray();
//判断转换后的数组是否是Object数组
if (a.getClass() != Object[].class) {
Object[] newArray = new Object[a.length];
System.arraycopy(a, 0, newArray, 0, a.length);
a = newArray;
}
array = a;
size = a.length;
}
都调用的System.arraycopy方法，该方法是native方法，针对基本数据类型(非String)在Android的System中有相应的重载类型，重载算法只针对了copy长度小于等于32时，使用了java代码进行copy，如果大于32时，依然使用了相应的native的算法。
public static native void arraycopy(Object src, int srcPos,
Object dest, int destPos,
int length);
三、增加元素
3.1 增加一个元素
Java
核心点在于容量超过时，新容量的计算，一般为老容量的1.5倍、或者是默认容量、或者是老容量+1、或者是Integer.MAX_VALUE - 8，或者是Integer.MAX_VALUE
//添加一个元素
public boolean add(E e) {
//确保内部容量(为当前的size+1)
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
Android
与java代码中的差异在于容量的扩充，以及空数组变成有值数组的数组的默认容量
//数组的最小扩充容量
private static final int MIN_CAPACITY_INCREMENT = 12;
@Override
public boolean add(E object) {
Object[] a = array;
int s = size;
if (s == a.length) {//如果数组已经满了
//新创建一个数组，数组长度为老容量+[最小扩充容量或老容量的一半]
//s<(MIN_CAPACITY_INCREMENT/2)一般只有【空数组、默认容量比较小、默认构造函数参数是collection的情况下发生】
Object[] newArray = new Object[s +
(s < (MIN_CAPACITY_INCREMENT / 2) ?
MIN_CAPACITY_INCREMENT : s >> 1)];
//将老数组元素copy到新数组中
System.arraycopy(a, 0, newArray, 0, s);
array = a = newArray;
}
a[s] = object;
size = s + 1;
modCount++;//修改次数，该属性是在AbstractList中。。。
return true;
}
3.2 在相应位置增加一个元素
Java
核心点在于数组的copy
public void add(int index, E element) {
rangeCheckForAdd(index);//检查index是否越界
//容量判断，并未修改size
ensureCapacityInternal(size + 1); // Increments modCount!!
//从index位置开始，长度为size-index，size为数组中有意义的元素个数，copy到数组的index+1位置。
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
elementData[index] = element;
size++;//容量相加
}
Android
与Java的区别在于数组扩容之后元素的copy，java是扩容是就将数组元素copy到新数组，然后将index位置及之后的元素依次向后移动一个位置，而Android代码就是在新建一个数组，然后从index开始分成两部分copy
@Override
public void add(int index, E object) {
Object[] a = array;
int s = size;
if (index > s || index < 0) {//判断是否越界
throwIndexOutOfBoundsException(index, s);
}
//如果数组容量足够，直接copy即可
if (s < a.length) {
System.arraycopy(a, index, a, index + 1, s - index);
} else {
//数组的容量不够，将数组扩展到新容量
// assert s == a.length;
Object[] newArray = new Object[newCapacity(s)];
//将老数组数据copy到新数组中
System.arraycopy(a, 0, newArray, 0, index);
System.arraycopy(a, index, newArray, index + 1, s - index);
array = a = newArray;
}
a[index] = object;
size = s + 1;
modCount++;
}
3.3 将集合中的元素全部添加到末尾
Java
如果添加c的容量超过了老的数组的一般大小，那么直接扩容到新的最小容量[old容量+c的容量]，但是有新问题就是，如果随后还添加的话，那么还需要扩容。
另外就是集合长度为0的情况，也进行了相应的数据copy
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);//将元素copy到新的数组里
size += numNew;//更新size
return numNew != 0;
}
Android
解决了java代码中存在的问题
@Override
public boolean addAll(Collection<? extends E> collection) {
Object[] newPart = collection.toArray();//转换成数组
int newPartSize = newPart.length;//新部分的大小
if (newPartSize == 0) {//新长度为0直接返回
return false;
}
Object[] a = array;//原有数据
int s = size;
int newSize = s + newPartSize; // If add overflows, arraycopy will fail
if (newSize > a.length) {//新的长度，大于原有长度
//容量扩充为，总容量-1的1.5倍，不知道为什么使用总容量-1,也有可能是将下标放置进去了。。。
int newCapacity = newCapacity(newSize - 1); // ~33% growth room
Object[] newArray = new Object[newCapacity];//创建新数组
System.arraycopy(a, 0, newArray, 0, s);//将老数据copy到新数组中
array = a = newArray;//数组赋值
}
System.arraycopy(newPart, 0, a, s, newPartSize);//将添加的数据copy到新数组中
size = newSize;
modCount++;
return true;
}
3.4 将集合中的元素添加到相应的位置
Java
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);//移动或者复制数组
//将新的数据a copy到集合对应的数据中
System.arraycopy(a, 0, elementData, index, numNew);
size += numNew;
return numNew != 0;
}
Android
public boolean addAll(int index, Collection<? extends E> collection) {
int s = size;
if (index > s || index < 0) {//判断数组是否越界
throwIndexOutOfBoundsException(index, s);
}
Object[] newPart = collection.toArray();//将添加的集合转换成数组
int newPartSize = newPart.length;
if (newPartSize == 0) {//如果添加的数据集合的长度为0就返回
return false;
}
Object[] a = array;
int newSize = s + newPartSize; // If add overflows, arraycopy will fail
if (newSize <= a.length) {//判断是否有足够的容量，如果有直接将后面的数据移动到新的位置
System.arraycopy(a, index, a, index + newPartSize, s - index);
} else {
// 扩充后的容量
int newCapacity = newCapacity(newSize - 1); // ~33% growth room
Object[] newArray = new Object[newCapacity];//新的数组
//分两段copy数据
System.arraycopy(a, 0, newArray, 0, index);
System.arraycopy(a, index, newArray, index + newPartSize, s-index);
array = a = newArray;
}
//copy新数据
System.arraycopy(newPart, 0, a, index, newPartSize);
size = newSize;
modCount++;
return true;
}
3.5 公共方法
Java
//默认的容量
private static final int DEFAULT_CAPACITY = 10;
//确保内部容量为最小容量minCapacity
private void ensureCapacityInternal(int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
//如果是使用空参数构造函数创建的数组，则将容量修改为【默认容量、当前容量】中的最小值
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
ensureExplicitCapacity(minCapacity);
}
//确保明确容量
private void ensureExplicitCapacity(int minCapacity) {
modCount++;//修改次数，在迭代器中使用，如果修改次数不明确，那么会发生一个异常【ConcurrentModificationException】,想了解具体的作用可以看源码的注释, 该属性是在AbstractList中，感觉是在迭代器循环查找时，插入和删除操作可能会报错
// overflow-conscious code
//如果最小容量大于数组的长度，需要增加容器的容量
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
//数组的最大数值
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
//增加数组容量
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;//老容量
int newCapacity = oldCapacity + (oldCapacity >> 1);//新容量为老容量的1.5倍
if (newCapacity - minCapacity < 0)//新容量小于最小容量，当老容量为0时
newCapacity = minCapacity;//新容量赋值为最小容量
if (newCapacity - MAX_ARRAY_SIZE > 0)//新容量大于最大容量时
newCapacity = hugeCapacity(minCapacity);
// minCapacity is usually close to size, so this is a win:
//将元素copy到新容量的数组中
elementData = Arrays.copyOf(elementData, newCapacity);
}
//巨大容量
private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
//最大容量大于设定的上限时，将容量修改为Integer.MAX_VALUE
// 一般都不会超，如果超过了，此时的ArrayList计算就会比较慢了。。。可以考虑换种集合用了。。。
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
}
Android
private static int newCapacity(int currentCapacity) {
//容量扩展
int increment = (currentCapacity < (MIN_CAPACITY_INCREMENT / 2) ?
MIN_CAPACITY_INCREMENT : currentCapacity >> 1);
return currentCapacity + increment;
}
3.6 总结
共有add(E e)，add(int index,E e) ，addAll(Collection<? extends E> c)，allAll(int index,Collection<? extends E> c)
步骤
- 判断index是否越界(有index参数)
- 判断是否需要扩容，如果需要就将容量扩展为原来总容量一半，如果不满足需求，就扩容到总容量，在Android中则是扩容到总容量-1的一半。。。，扩容后复制数组
- 关于扩容后复制数组，在add(int index,...)中Android和Java有实现差异，主要差异在数组是否是分段复制。Java在复制数组时直接扩容后复制完，然后再将index及后续后移，相当于后半段的数据复制了两遍，Android中的实现解决了这个问题。
- 关于modCount，Java是在判断是否需要扩容就增加，Android一般是在新的数据赋值后增加。
四、删除元素
4.1 移除一个指定位置上的元素
Java
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);//将index位置之后的元素依次向前copy
elementData[--size] = null; // clear to let GC do its work，将最后的元素置空，方便回收
return oldValue;//移除的元素
}
Android
@Override
public E remove(int index) {
Object[] a = array;
int s = size;
if (index >= s) {//判断是否越界
throwIndexOutOfBoundsException(index, s);
}
@SuppressWarnings("unchecked")
E result = (E) a[index];//获取元素
System.arraycopy(a, index + 1, a, index, --s - index);//移动元素
a[s] = null; // Prevent memory leak，方便回收
size = s;
modCount++;
return result;//移除的元素
}
4.2 移除一个指定的元素
移除第一个相等的元素
Java
public boolean remove(Object o) {
if (o == null) {//如果为null 移除第一个null
for (int index = 0; index < size; index++)
if (elementData[index] == null) {
fastRemove(index);
return true;
}
} else {//如果不为null移除第一个object，通过equals判断是否相等
for (int index = 0; index < size; index++)
if (o.equals(elementData[index])) {
fastRemove(index);
return true;
}
}
return false;
}
//快速移除某一个元素
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，清除最后一位元素
}
Android
@Override
public boolean remove(Object object) {
Object[] a = array;
int s = size;
if (object != null) {//元素不为空
for (int i = 0; i < s; i++) {
if (object.equals(a[i])) {//元素相等
System.arraycopy(a, i + 1, a, i, --s - i);//后置元素左移
a[s] = null; // Prevent memory leak//末尾置空
size = s;//修改size
modCount++;
return true;
}
}
} else {//元素为空
for (int i = 0; i < s; i++) {
if (a[i] == null) {//如果为空
System.arraycopy(a, i + 1, a, i, --s - i);//后置元素左移
a[s] = null; // Prevent memory leak，末尾置空
size = s;
modCount++;
return true;
}
}
}
return false;//移除失败
}
4.3 移除某一段元素
移除一段元素
Java
protected void removeRange(int fromIndex, int toIndex) {
modCount++;
int numMoved = size - toIndex;//移动的元素个数
System.arraycopy(elementData, toIndex, elementData, fromIndex,
numMoved);//将toIndex的后置元素左移
// clear to let GC do its work
int newSize = size - (toIndex-fromIndex);//新的size
for (int i = newSize; i < size; i++) {//从新的size开始到老的size，将之间的元素置空
elementData[i] = null;
}
size = newSize;
}
Android
@Override
protected void removeRange(int fromIndex, int toIndex) {
if (fromIndex == toIndex) {//位置相等，返回
return;
}
Object[] a = array;
int s = size;
//开始位置大于size，结束位置大于size，开始位置大于结束位置，抛出数组越界异常
if (fromIndex >= s) {
throw new IndexOutOfBoundsException("fromIndex " + fromIndex
+ " >= size " + size);
}
if (toIndex > s) {
throw new IndexOutOfBoundsException("toIndex " + toIndex
+ " > size " + size);
}
if (fromIndex > toIndex) {
throw new IndexOutOfBoundsException("fromIndex " + fromIndex
+ " > toIndex " + toIndex);
}
// 将toIndex所有后置元素，向左移动，移动到fromIndex
System.arraycopy(a, toIndex, a, fromIndex, s - toIndex);
int rangeSize = toIndex - fromIndex;//移动后，最后一个有效元素的位置距离s的差
//rangeSize = s-(fromIndex+s-toIndex)
Arrays.fill(a, s - rangeSize, s, null);//将所有的无效位置置空
size = s - rangeSize;
modCount++;
}
4.4 移除集合中所有元素
Java
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 {
//如果complement为true，则是将c中包含有当前集合中的所有元素前移
//如果complement为false，则是将c中不包含当前集合中的所有元素前移
// 在循环结束后 w及之后为集合中w位置及之后的元素
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.
//保持兼容一致性因为contains是抽象方法，有可能为发生异常
if (r != size) {//表示发生了异常
//将异常发生位置及以后的数据移到需要的元素最后w位置
System.arraycopy(elementData, r,
elementData, w,
size - r);
w += size - r;//修改w，后续元素因为没有发生判断，所以也是需要的
}
if (w != size) {
//如果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;
}
Android
Android中的ArrayList没有重写这个方法，如果调用这个API，调用的是AbstractCollection的API
public boolean removeAll(Collection<?> collection) {
boolean result = false;
Iterator<?> it = iterator();
//使用迭代器，如果包含在collection中就移除
while (it.hasNext()) {
if (collection.contains(it.next())) {
it.remove();
result = true;
}
}
return result;
}
4.5 总结
- 删除操作一定会修改modeCount，且可能会涉及到数组的复制，相对低效
- Android 中ArrayList竟然没有重写RemoveAll方法
五、修改元素
设置某一个位置的元素
不会修改modCount
Java
public E set(int index, E element) {
rangeCheck(index);//越界检查
E oldValue = elementData(index);//获取元素
elementData[index] = element;//将元素修改为新值
return oldValue;//返回旧值
}
Android
@Override
public E set(int index, E object) {
Object[] a = array;
if (index >= size) {//越界检查
throwIndexOutOfBoundsException(index, size);
}
@SuppressWarnings("unchecked")
E result = (E) a[index];//获取元素
a[index] = object;//将元素修改为新值
return result;//返回旧值
}
六、查询元素
获取某一位置的元素
Java
不会修改modCount
public E get(int index) {
rangeCheck(index);//判断是否越界
return elementData(index);
}
E elementData(int index) {
return (E) elementData[index];
}
Android
@SuppressWarnings("unchecked")
@Override
public E get(int index) {
if (index >= size) {
throwIndexOutOfBoundsException(index, size);
}
return (E) array[index];
}
七、包含元素
Java
public boolean contains(Object o) {
return indexOf(o) >= 0;//看位置信息是否>-1，
}
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;
}
//倒序查询，包含三
public int lastIndexOf(Object o) {
if (o == null) {//如果为空，就查找第一个空元素的位置
for (int i = size-1; i >= 0; i--)
if (elementData[i]==null)
return i;
} else {//如果不为空，就查找第一个相等(equals)元素的位置
for (int i = size-1; i >= 0; i--)
if (o.equals(elementData[i]))
return i;
}
return -1;
}
Android
@Override
public boolean contains(Object object) {
Object[] a = array;
int s = size;
if (object != null) {//如果不为null
for (int i = 0; i < s; i++) {//循环判断是否有有相等(equals)的元素
if (object.equals(a[i])) {
return true;
}
}
} else {//如果为null，循环判断数组中是有有null元素
for (int i = 0; i < s; i++) {
if (a[i] == null) {
return true;
}
}
}
return false;
}
@Override
public int indexOf(Object object) {
Object[] a = array;
int s = size;
if (object != null) {//如果不为null
for (int i = 0; i < s; i++) {//则正序循环判断是否有相等(equals)的元素
if (object.equals(a[i])) {
return i;//如果有，返回位置信息
}
}
} else {//如果为null，循环判断数组中是有有null元素
for (int i = 0; i < s; i++) {
if (a[i] == null) {
return i;//如果有，返回位置信息
}
}
}
return -1;//如果没有，返回-1
}
@Override
public int lastIndexOf(Object object) {
Object[] a = array;
if (object != null) {//如果不为null，则正序循环判断是否有相等(equals)的元素
for (int i = size - 1; i >= 0; i--) {
if (object.equals(a[i])) {
return i;//如果有，返回位置信息
}
}
} else {//如果为null，倒序循环判断数组中是有有null元素
for (int i = size - 1; i >= 0; i--) {
if (a[i] == null) {
return i;//如果有，返回位置信息
}
}
}
return -1;//如果没有，返回-1
}
八、集合的size
集合的size不等于集合中数组的长度
Java
public int size() {
return size;
}
Android
@Override
public int size() {
return size;
}
九、判空
判断size是否为空
Java
public boolean isEmpty() {
return size == 0;
}
Android
@Override
public boolean isEmpty() {
return size == 0;
}
十、其他常用方法
10.1清空
Java
public void clear() {
modCount++;
// clear to let GC do its work
for (int i = 0; i < size; i++)
elementData[i] = null;//循环置空
size = 0;
}
Android
@Override
public void clear() {
if (size != 0) {
Arrays.fill(array, 0, size, null);//使用Arrays填充空数据
size = 0;
modCount++;
}
}
10.2 转换成数组
Java
核心点调用Arrays的copy功能
public Object[] toArray() {
return Arrays.copyOf(elementData, size);
}
public <T> T[] toArray(T[] a) {
if (a.length < size)//如果copy到的数组长度较小，重新创建数组copy
// 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);//长度足够，直接copy
if (a.length > size)
a[size] = null;//将数组的size位置置空，判断copy的数据截止位置
return a;
}
Android
@Override
public Object[] toArray() {
int s = size;
Object[] result = new Object[s];
System.arraycopy(array, 0, result, 0, s);//直接copy到新数组
return result;
}
@Override
public <T> T[] toArray(T[] contents) {
int s = size;
if (contents.length < s) {//传入的数组长度不够，直接创建一个长度足够的数组
@SuppressWarnings("unchecked") T[] newArray
= (T[]) Array.newInstance(contents.getClass().getComponentType(), s);
contents = newArray;
}
System.arraycopy(this.array, 0, contents, 0, s);//长度足够，直接copy
if (contents.length > s) {
//将size位置设为空，表示这个位置之前的数据是copy的数组
contents[s] = null;
}
return contents;
}
十一、迭代
11.1 普通迭代器Iterator
实现了Iterator接口的迭代器
Java
//获取迭代器
public Iterator<E> iterator() {
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
//期望的修改次数，在使用迭代器循环过程中，如果调用ArrayList.remove和ArrayList.add方法，会报错，防止在迭代器循环过程中增删元素
int expectedModCount = modCount;
//是否有下一个
public boolean hasNext() {
return cursor != size;//游标不等于size
}
//获取下一个元素
@SuppressWarnings("unchecked")
public E next() {
checkForComodification();//检查是否ArrayList中元素修改过
int i = cursor;
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];//将当前位置(老游标位置)赋值给lastRet，根据当前位置取值，将该位置的值返回。
}
//移除最后一个取到的元素
public void remove() {
if (lastRet < 0)//如果没有取过值，自然无法移除值，抛出异常
throw new IllegalStateException();
checkForComodification();
try {
//将最后取出的元素位置的元素移除，会改变修改次数
ArrayList.this.remove(lastRet);
cursor = lastRet;//将游标移到上一次取出的位置
lastRet = -1;//将取出位置置为-1，防止连续移除
expectedModCount = modCount;//重新设置期望修改次数
} catch (IndexOutOfBoundsException ex) {
throw new ConcurrentModificationException();
}
}
//配合Lambda表达式使用，遍历
@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();
}
//检查是否ArrayList中元素修改过，如果修改过会报异常
final void checkForComodification() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
}
}
Android
不采取游标方式进行迭代，而是采取剩余量这个说法
@Override
public Iterator<E> iterator() {
return new ArrayListIterator();
}
private class ArrayListIterator implements Iterator<E> {
/** Number of elements remaining in this iteration */
private int remaining = size;//默认剩余量为ArrayList的size
/** Index of element that remove() would remove, or -1 if no such elt */
private int removalIndex = -1;//移除的位置
/** The expected modCount value */
private int expectedModCount = modCount;//期望修改次数
public boolean hasNext() {
return remaining != 0;//剩余量不等于0
}
@SuppressWarnings("unchecked")
public E next() {
ArrayList<E> ourList = ArrayList.this;
int rem = remaining;//剩余量
if (ourList.modCount != expectedModCount) {//判断迭代过程中是否修改过
throw new ConcurrentModificationException();
}
if (rem == 0) {//剩余量为0
throw new NoSuchElementException();
}
remaining = rem - 1;//剩余量-1，
return (E) ourList.array[removalIndex = ourList.size - rem];//返回size-旧剩余量位置的元素，将上一元素位置记录下来，移除时使用
}
public void remove() {
Object[] a = array;
int removalIdx = removalIndex;//上一元素位置
if (modCount != expectedModCount) {
throw new ConcurrentModificationException();
}
if (removalIdx < 0) {//上一元素位置<0，表示没有对应元素，不可移除
throw new IllegalStateException();
}
//将移除位置后置元素copy到移除位置
System.arraycopy(a, removalIdx + 1, a, removalIdx, remaining);
a[--size] = null; // Prevent memory leak，将最后元素置空
removalIndex = -1;//移除位置置为-1，放置连续remove
expectedModCount = ++modCount;//修改modCount
}
}
11.2 List特有迭代器ListIterator
该迭代器可以倒序遍历，也就是向前遍历
Java
public ListIterator<E> listIterator(int index) {
if (index < 0 || index > size)//防止数组越界
throw new IndexOutOfBoundsException("Index: "+index);
return new ListItr(index);//设置游标默认位置的迭代器
}
//返回游标位置默认为0的迭代器
public ListIterator<E> listIterator() {
return new ListItr(0);
}
//内部类，继承普通迭代，实现了ListItertor接口
private class ListItr extends Itr implements ListIterator<E> {
ListItr(int index) {
super();
cursor = index;//设置游标位置
}
//是否有前置元素，游标不等于0
public boolean hasPrevious() {
return cursor != 0;
}
//下一个位置，游标位置
public int nextIndex() {
return cursor;
}
//前一个位置
public int previousIndex() {
return cursor - 1;
}
//前置元素
@SuppressWarnings("unchecked")
public E previous() {
checkForComodification();//检查是否遍历过程中是否修改过
int i = cursor - 1;//将位置设置为游标位-1
if (i < 0)
throw new NoSuchElementException();
Object[] elementData = ArrayList.this.elementData;
if (i >= elementData.length)
throw new ConcurrentModificationException();
cursor = i;//将游标移动
return (E) elementData[lastRet = i];//获取旧游标位置元素，将最后取出的位置修改为对应位置
}
//设置元素
public void set(E e) {
if (lastRet < 0)
throw new IllegalStateException();
checkForComodification();//检查是否遍历过程中，是否修改过数组
try {
ArrayList.this.set(lastRet, e);//设置最后遍历位置的元素
} catch (IndexOutOfBoundsException ex) {
throw new ConcurrentModificationException();
}
}
//在游标位置，添加元素
public void add(E e) {
checkForComodification();
try {
int i = cursor;//将位置设为游标位
ArrayList.this.add(i, e);//在该位置添加元素
cursor = i + 1;//修改游标
lastRet = -1;//最后取出位置-1
expectedModCount = modCount;//更新修改次数
} catch (IndexOutOfBoundsException ex) {
throw new ConcurrentModificationException();
}
}
}
Android
ArrayList中没有实现listIterator，调用API则是调用AbstractList中的API
public ListIterator<E> listIterator() {
return listIterator(0);
}
public ListIterator<E> listIterator(int location) {
return new FullListIterator(location);
}
private class SimpleListIterator implements Iterator<E> {
int pos = -1;//泛游标，不同于游标，也可以理解为游标，指代的是最后变化(添加、查询、删除)的元素
int expectedModCount;
int lastPosition = -1;//最后修改位置
SimpleListIterator() {
expectedModCount = modCount;
}
public boolean hasNext() {
return pos + 1 < size();//泛游标是否已经指向了最后一个元素
}
public E next() {
if (expectedModCount == modCount) {
try {
E result = get(pos + 1);//获取pos+1位置的元素
lastPosition = ++pos;//最后修改pos位置和最后修改位置
return result;
} catch (IndexOutOfBoundsException e) {
throw new NoSuchElementException();
}
}
throw new ConcurrentModificationException();
}
public void remove() {
if (this.lastPosition == -1) {
throw new IllegalStateException();
}
if (expectedModCount != modCount) {
throw new ConcurrentModificationException();
}
try {
AbstractList.this.remove(lastPosition);//移除最后修改位置的元素
} catch (IndexOutOfBoundsException e) {
throw new ConcurrentModificationException();
}
expectedModCount = modCount;//设置修改次数
if (pos == lastPosition) {//泛游标=最后修改位置
pos--;//泛游标-1
}
lastPosition = -1;//修改最后位置
}
}
private final class FullListIterator extends SimpleListIterator implements ListIterator<E> {
FullListIterator(int start) {
//判断最后位置，
if (start >= 0 && start <= size()) {
pos = start - 1;//为了契合游标概念。。。
} else {
throw new IndexOutOfBoundsException();
}
}
public void add(E object) {
if (expectedModCount == modCount) {
try {
//在泛游标+1位置设置元素
AbstractList.this.add(pos + 1, object);
} catch (IndexOutOfBoundsException e) {
throw new NoSuchElementException();
}
pos++;//泛游标移动
lastPosition = -1;//最后位置
if (modCount != expectedModCount) {
expectedModCount = modCount;
}
} else {
throw new ConcurrentModificationException();
}
}
//是否有元素
public boolean hasPrevious() {
return pos >= 0;
}
//下一个位置
public int nextIndex() {
return pos + 1;
}
//前序遍历
public E previous() {
if (expectedModCount == modCount) {
try {
E result = get(pos);//获取pos位置元素
lastPosition = pos;//修改最后元素位置
pos--;//游标--
return result;
} catch (IndexOutOfBoundsException e) {
throw new NoSuchElementException();
}
}
throw new ConcurrentModificationException();
}
//向前移动游标
public int previousIndex() {
return pos;
}
public void set(E object) {
if (expectedModCount == modCount) {
try {
AbstractList.this.set(lastPosition, object);//设置最后修改位置元素
} catch (IndexOutOfBoundsException e) {
throw new IllegalStateException();
}
} else {
throw new ConcurrentModificationException();
}
}
}
十二、遍历
- 采用普通for循环，这种遍历方式效率最高，因为有了随机快速访问能力
ArrayList as = new ArrayList();
.......
for(int i=0;i<as.size();i++){
System.out.println(as.get(i));
}
- for-each遍历，这种遍历使用范围，只能是迭代数组或者实现了Iterable的对象
can only iterate over an array or an instance of java.lang.Iterable
ArrayList ls = new ArrayList();
......
for(Object o:ls){
System.out.println(o);
}
- 使用普通迭代器遍历，效率较低
ArrayList<String> as = new ArrayList<>();
......
Iterator<String> it = as.iterator();
while(it.hasNext()){
System.out.println(it.next());
}
- 使用ListIterator，这个迭代器可以前后循环
ArrayList<String> as = new ArrayList<>();
......
ListIterator<String> lit = as.listIterator();
while(lit.hasNext()){
System.out.println(lit.next());
}
while(lit.hasPrevious()){
System.out.println(lit.previous());
}
十三、总结
- 普通的增加、删除会修改modCount，它的主要功能是在迭代器迭代过程中判断是否进行过增加和删除操作，因为这两种操作会导致迭代异常。
- 所有涉及到数组copy的操作都会导致效率降低，其中增加扩容、中间某一位置增加元素、定点删除、批量删除、等操作都会产生数组copy。所以在查询情况比较多建议使用ArrayList，例如Android开发中的数据展示
- 和Vector的区别有以下几点
3.1 Vector 从JDK1.0就存在，ArrayList是从JDK1.2添加的
3.2 Vector是线程安全的，因为其中一些方法使用synchronized关键字来保证线程安全。
1.0加锁的方法有，具体如下：
public synchronized void addElement(E obj)
public synchronized void insertElementAt(E obj, int index)
public synchronized boolean removeElement(Object obj)
public synchronized void removeElementAt(int index)
public synchronized void removeAllElements()
public synchronized void setElementAt(E obj, int index)
public synchronized E elementAt(int index)
这些方法是1.0创建Vector就有的。
还有一些是实现了Collection(Since 1.2)的方法，这些方法是在1.2中实现的，其中加锁的具体如下：
public synchronized boolean add(E e)
public synchronized boolean addAll(Collection<? extends E> c)
public synchronized boolean addAll(int index, Collection<? extends E> c)
public synchronized E remove(int index)
public synchronized void removeAllElements()
public synchronized E set(int index, E element)
public synchronized E get(int index)
但是有一些方法虽说表面是不加锁的，但是还是调用的加锁方法如：
public void add(int index, E element) {
insertElementAt(element, index);
}
public boolean remove(Object o) {
return removeElement(o);
}
public void clear() {
removeAllElements();
}
3.3 扩容：Vector可以设置容量的默认增长量，如果不设置默认增长量，那么默认扩容量为原来数组的长度，也就是说扩容是容量变为两倍。
其他文章
容器解析
ArrayList解析
LinkedList解析
TreeMap解析(上)
TreeMap解析(下)
HashMap解析
LinkedHasMap解析(下)
Set解析
