Java collection source code analysis (3): ArrayList
summary
In the previous article: Java collection source code analysis (II): list and abstractlist and Java collection source code analysis (I): collection and abstractcollection, we have roughly understood the hierarchical relationship and method implementation process from collection interface to list interface, from abstractcollection abstract class to abstractlist.
In this article, based on the previous article, we will read the source code of ArrayList, the most commonly used implementation class of list, and have an in-depth understanding of this "familiar stranger".
1、 Class relationship of ArrayList
ArrayList implements three interfaces and inherits an abstract class. Serializable, Cloneable and randomaccess interfaces are empty interfaces for marking. Its main abstract methods come from list and some implementations come from abstractlist.
1. Abstractlist and list
ArrayList implements the list interface. It is one of the implementation classes of the list interface. It inherits the implementation of most methods obtained from the abstract class abstractlist.
In particular, in theory, the parent class abstractlist has implemented the class abstractlist interface, so in theory, ArrayList can obtain the abstract methods in the list through the parent class, and there is no need to implement the list interface.
There are different opinions on the answer to this question on the Internet. Some say it is to facilitate the implementation of JDK agent through a common interface, and others say it is for code standardization and readability. On stack overflow, why does linkedhashset extend HashSet and implementation set? An old brother who is said to have asked the original author gave an answer to it was a mistake, But this does not seem to explain why almost all container classes have similar behavior. Perhaps only the real original author knows what the truth is.
Randomaccess is a marked interface. The collection that implements this interface is allowed to be accessed randomly.
According to Javadoc, if a class implements this interface, then:
for (int i=0,n=list.size(); i < n; i++)
list.get(i);
Faster than
for (Iterator i=list.iterator(); i.hasNext(); )
i.next();
Random access is actually based on subscript access. Take LinkedList and ArrayList as examples. The underlying implementation of LinkedList is a linked list. Random access needs to traverse the linked list, with a complexity of O (n), while the underlying implementation of ArrayList is an array. Random access can be addressed directly through subscript, with a complexity of O (1).
When we need to specify the iterative algorithm, we can select the corresponding iterative method by whether the implementation class implements the randomaccess interface. In some methods that operate collections (such as sublist in abstractlist), some processing is also done according to this point.
3.Cloneable
Clonable interface means that its implementation class can be copied. According to Javadoc:
In short, if a class wants to use object Clone () method to copy the object, then this class needs to implement the clonable interface and override object Clone() method. It is worth mentioning that object The default copy provided by clone () is a shallow copy. In fact, the shallow copy does not copy and creates a new instance. The object variable obtained by shallow copy is actually a pointer and points to the original memory address. The method of deep copy needs to be provided by ourselves.
4.Serializable
The serializable interface is also a markup interface, which indicates that the implementation class can be serialized and deserialized.
Here is the concept of serialization.
It is worth mentioning that Java provides the transient keyword for private information that does not want to be stored in a file or transmitted in the form of byte stream, and the attributes marked by it will not be serialized. For example, in abstractlist, the variable modcount used to record the number of structural operations in the concurrent modification check mentioned earlier, and the underlying array elementdata of ArrayList to be introduced below are modified by the transient keyword.
For more information, please refer to the boss's blog: Notes on the use of Java transient keyword
2、 Member variable
In ArrayList, there are seven member variables:
private static final long serialVersionUID = 8683452581122892189L;
/**
* 默认初始容量
*/
private static final int DEFAULT_CAPACITY = 10;
/**
* 用于空实例的共享空数组实例
*/
private static final Object[] EMPTY_ELEMENTDATA = {};
/**
* 共享的空数组实例，用于默认大小的空实例。我们将此与EMPTY_ELEMENTDATA区别开来，以了解添加第一个元素时要扩容数组到多大。
*/
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
/**
* 存储ArrayList的元素的数组缓冲区。 ArrayList的容量是此数组缓冲区的长度。添加第一个元素时，任何符合
* elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA 的空ArrayList都将扩展为DEFAULT_CAPACITY。
*/
transient Object[] elementData;
/**
* ArrayList的大小（它包含的元素数）
*/
private int size;
/**
* 要分配的最大数组大小
*/
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
Let's explain their role one by one.
1.serialVersionUID
private static final long serialVersionUID = 8683452581122892189L;
UUID used for serialization detection. We can simply understand its role:
For more information, you can still refer to the boss's blog: what is the role of serialVersionUID in Java classes? Give an example
2.DEFAULT_ CAPACITY
Default capacity. If the initial capacity is not specified in the construction method during instantiation, the first capacity expansion will be based on this value.
3.EMPTY_ ELEMENTDATA
An empty array. When the specified capacity is 0 when calling the construction method, or other operations will cause the length of the array in the collection to become 0, the empty array will be directly assigned to the array elementdata actually used to store data in the collection.
4.DEFAULTCAPACITY_ EMPTY_ ELEMENTDATA
It is also an empty array, which is different from empty_ Elementdata specifies that when the capacity is 0, it will be assigned to elementdata, and default capability_ EMPTY_ Elementdata is assigned to elementdata only when the capacity is not specified, and the capacity will be expanded when the first element is added.
DEFAULTCAPACITY_ EMPTY_ Elementdata and empty_ Elementdata does not affect the actual subsequent addition of elements. The two mainly represent a logical difference: the former indicates that the collection is currently empty, but elements may be added in the future, while the latter indicates that the collection does not intend to store anything at the beginning. It is an empty collection with a capacity of 0.
5.elementData
For the array that actually stores data, when expanding capacity or other operations, the data will be copied to the new array first, and then the variable will point to the new array.
6.size
The number of elements in the collection (note not the array length).
7.MAX_ ARRAY_ SIZE
The maximum array length allowed is equal to integer MAX_ Value - 8 is to prevent array headers from being used to hold some other information in some virtual machines.
3、 Construction method
Three construction methods are provided in ArrayList:
// 1.构造一个空集合
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
// 2.构造一个具有指定初始容量的空集合
public ArrayList(int initialCapacity) {
// 判断指定的初始容量是否大于0
if (initialCapacity > 0) {
// 若大于0，则直接指定elementData数组的长度
this.elementData = new Object[initialCapacity];
} else if (initialCapacity == 0) {
// 若等于0，将EMPTY_ELEMENTDATA赋给elementData
this.elementData = EMPTY_ELEMENTDATA;
} else {
// 小于0，抛异常
throw new IllegalArgumentException("Illegal Capacity: " + initialCapacity);
}
}
// 3.构造一个包含指定集合所有元素的集合
public ArrayList(Collection<? extends E> c) {
elementData = c.toArray();
// 判断传入的集合是否为空集合
if ((size = elementData.length) != 0) {
// 确认转为的集合底层实现是否也是Objcet数组
if (elementData.getClass() != Object[].class)
elementData = Arrays.copyOf(elementData,size,Object[].class);
} else {
// 如果是空集合，将EMPTY_ELEMENTDATA赋给elementData
this.elementData = EMPTY_ELEMENTDATA;
}
}
We usually use the first one, and sometimes the third one. In fact, if we can estimate how many elements will be added, we can use the second constructor to specify the capacity to avoid the consumption caused by capacity expansion.
4、 Expansion and contraction
The scalability of ArrayList is one of its most important features. Before we begin to understand other methods, we need to understand how ArrayList expands and shrinks.
0.System. arraycopy()
Before that, we need to understand the core method system Arraycopy() method:
/**
* 从一个源数组复制元素到另一个数组，如果该数组指定位置已经有元素，就使用复制过来的元素替换它
*
* @param src 要复制的源数组
* @param srcPos 要从源数组哪个下标开始复制
* @param dest 要被移入元素的数组
* @param destPos 要从被移入元素数组哪个下标开始替换
* @param length 复制元素的个数
*/
arraycopy(Object src,int srcPos,Object dest,int destPos,int length)
For example, if we now have Arr1 = {1,2,3,4,5} and arr2 = {6,7,8,9,10}, now we use arraycopy (Arr1, arr2,2), which means:
Start with the element with an index of 0 in Arr1, copy 2 elements, and then replace the original elements with these two elements from the place with an index of 0 in arr2 array,
int[] arr1 = {1,5};
int[] arr2 = {6,10};
System.arraycopy(arr1,2);
// arr2 = {1，2，8，9，10}
1. Capacity expansion
Although there is a simple capacity expansion method finishtoarray () in the abstractcollection abstract class, ArrayList does not continue to use it, but re implements the capacity expansion process itself. The capacity expansion process of ArrayList generally occurs on new elements.
Let's take the add () method as an example:
public boolean add(E e) {
// 判断新元素加入后，集合是否需要扩容
ensureCapacityInternal(size + 1);
elementData[size++] = e;
return true;
}
(1) Check whether the capacity is expanded for the first time
We know that when using the constructor to build a collection, if the initial capacity is not specified, the internal array elementdata will be assigned the default empty array defaultcapability_ EMPTY_ ELEMENTDATA。
Therefore, when we call add (), we will first call the ensurecapacityinternal () method to determine whether elementdata is still defaultcapability_ EMPTY_ Elementdata, if yes, indicates that the initial capacity is not specified during creation and has not been expanded. Therefore, it is necessary to ensure that the collection is expanded to 10 or more capacity:
private void ensureCapacityInternal(int minCapacity) {
// 判断是否还是初始状态
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
// 扩容到默认容量（10）或更大
minCapacity = Math.max(DEFAULT_CAPACITY,minCapacity);
}
ensureExplicitCapacity(minCapacity);
}
(2) Check whether capacity expansion is required
When the size of the first expansion is determined, or the elementdata has been expanded at least once, it will enter the preparation process of expansion, ensureexplicitcapacity(). In this method, the operation counter modcount will be increased, and the new capacity will be greater than the length of the current group:
private void ensureExplicitCapacity(int minCapacity) {
// 扩容也是结构性操作，modCount+1
modCount++;
// 判断最小所需容量是否大于当前底层数组长度
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
(3) Capacity expansion
Finally, enter the real capacity expansion method (grow):
// 扩容
private void grow(int minCapacity) {
// 旧容量为数组当前长度
int oldCapacity = elementData.length;
// 新容量为旧容量的1.5倍
int newCapacity = oldCapacity + (oldCapacity >> 1);
// 如果新容量小于最小所需容量（size + 1），就以最小所需容量作为新容量
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
// 如果新容量大于允许的最大容量，就再判断能否再继续扩容
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
// 扩容完毕，将旧数组的数据拷贝到新数组上
elementData = Arrays.copyOf(elementData,newCapacity);
}
Some people may wonder why oldcapacity should be equal to elementdata Length instead of size ()?
In the ArrayList, there are both true deletions that need to completely remove elements and create a new array, and false deletions that only set the corresponding subscript element to null. Size() actually calculates the number of elements, so elementdata needs to be used here Length to understand the real length of the array.
Back to capacity expansion due to Max_ ARRAY_ Size is already the maximum expansion size allowed in theory. If the new capacity is larger than max_ ARRAY_ If the size is still large, a critical expansion size is involved. The hugecapacity() method is used to determine the final allowable capacity size:
private static int hugeCapacity(int minCapacity) {
// 是否发生溢出
if (minCapacity < 0) // overflow
throw new OutOfMemoryError
("required array size too large");
// 判断最终大小是MAX_ARRAY_SIZE还是Integer.MAX_VALUE
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
}
The hugecapacity () of ArrayList is exactly the same as that of abstractcollection abstract class, when mincapacity > max_ ARRAY_ When size is true, it indicates that the current number of elements and size capacity are equal to max_ ARRAY_ Size, the array is already very large. Copying at this time will consume a lot of performance, so the last expansion will be directly expanded to integer MAX_ Value, if it is larger, it can only overflow.
The following is the flow chart of capacity expansion:
2. Volume reduction
In addition to capacity expansion, ArrayList also provides a capacity reduction method trimtosize (), but this method is not called by any other internal methods, and can only be called by the program itself. It actively reduces the size of ArrayList, so it is not very common in daily use.
public void trimToSize() {
// 结构性操作，modCount+1
modCount++;
// 判断当前元素个数是否小于当前底层数组的长度
if (size < elementData.length) {
// 如果长度为0，就变为EMPTY_ELEMENTDATA空数组
elementData = (size == 0)
? EMPTY_ELEMENTDATA
// 否则就把容量缩小为当前的元素个数
: Arrays.copyOf(elementData,size);
}
}
3. Test
We can use reflection to see the expansion and contraction process of ArrayList:
First write a method to obtain elementdata through reflection:
// 通过反射获取值
public static void getEleSize(List<?> list) {
try {
Field ele = list.getClass().getDeclaredField("elementData");
ele.setAccessible(true);
Object[] arr = (Object[]) ele.get(list);
System.out.println("当前elementData数组的长度：" + arr.length);
} catch (NoSuchFieldException e) {
e.printStackTrace();
} catch (illegalaccessexception e) {
e.printStackTrace();
}
}
Then experiment:
public static void main(String[] args) {
// 第一次扩容
ArrayList<String> list = new ArrayList<>();
getEleSize(list); // 当前elementData数组的长度：0
list.add("aaa");
getEleSize(list); // 当前elementData数组的长度：10
// 指定初始容量为0的集合，进行第一次扩容
ArrayList<String> emptyList = new ArrayList<>(0);
getEleSize(emptyList); // 当前elementData数组的长度：0
emptyList.add("aaa");
getEleSize(emptyList); // 当前elementData数组的长度：1
// 扩容1.5倍
for (int i = 0; i < 10; i++) {
list.add("aaa");
}
getEleSize(list); // 当前elementData数组的长度：15
// 缩容
list.trimToSize();
getEleSize(list);// 当前elementData数组的长度：11
}
5、 Add / get
1.add
public boolean add(E e) {
// 如果需要就先扩容
ensureCapacityInternal(size + 1);
// 添加到当前位置的下一位
elementData[size++] = e;
return true;
}
public void add(int index,E element) {
// 若 index > size || index < 0 则抛 indexoutofboundsexception 异常
rangeCheckForAdd(index);
// 如果需要就先扩容
ensureCapacityInternal(size + 1);
// 把原本 index 下标以后的元素集体后移一位,为新插入的数组腾位置
System.arraycopy(elementData,index,elementData,index + 1,size - index);
elementData[index] = element;
size++;
}
The principle of adding is relatively simple. In fact, if you do not specify a subscript, insert it into the end of the array. Otherwise, first create a new array, and then move the data of the old array to the new array. In this process, leave the space of the element to be inserted on the new array in advance, and finally insert the element into the array. The following addition and deletion operations are basically based on this principle.
2.addAll
public boolean addAll(Collection<? extends E> c) {
// 将新集合的数组取出
Object[] a = c.toArray();
int numNew = a.length;
// 如有必要就扩容
ensureCapacityInternal(size + numNew);
// 将新数组拼接到原数组的尾部
System.arraycopy(a,numNew);
size += numNew;
return numNew != 0;
}
public boolean addAll(int index,Collection<? extends E> c) {
rangeCheckForAdd(index);
Object[] a = c.toArray();
int numNew = a.length;
// 先扩容
ensureCapacityInternal(size + numNew);
// 判断是否需要移动原数组
int numMoved = size - index;
if (numMoved > 0)
// 则将原本 index 下标以后的元素移到 index + numNew 的位置
System.arraycopy(elementData,index + numNew,numMoved);
System.arraycopy(a,numNew);
size += numNew;
return numNew != 0;
}
3.get
public E get(int index) {
rangeCheck(index);
return elementData(index);
}
// 根据下标从数组中取值，被使用在get(),set(),remove()等方法中
E elementData(int index) {
return (E) elementData[index];
}
6、 Delete / modify
1.remove
public E remove(int index) {
// 若 index >= size 会抛出 indexoutofboundsexception 异常
rangeCheck(index);
modCount++;
E oldValue = elementData(index);
// 判断是否需要移动数组
int numMoved = size - index - 1;
if (numMoved > 0)
System.arraycopy(elementData,index+1,numMoved);
// 把元素尾部位置设置为null，便于下一次插入
elementData[--size] = null;
return oldValue;
}
public boolean remove(Object o) {
// 如果要删除的元素是null
if (o == null) {
for (int index = 0; index < size; index++)
// 移除第一位为null的元素
if (elementData[index] == null) {
fastRemove(index);
return true;
}
} else {
// 如果要删除的元素不为null
for (int index = 0; index < size; index++)
if (o.equals(elementData[index])) {
fastRemove(index);
return true;
}
}
return false;
}
A fastremove() method is available here:
// fast 的地方在于：跳过边界检查，并且不返回删除的值
private void fastRemove(int index) {
modCount++;
int numMoved = size - index - 1;
if (numMoved > 0)
System.arraycopy(elementData,numMoved);
elementData[--size] = null;
}
The interesting thing is that index > = size is checked during remove (), and index > size | index < 0 is checked during add (). It can be seen that whether the index is less than 0 should be checked during addition.
The reason is that add () will call system immediately after verification Arraycopy(), because this is a native method, no exception will be thrown when an error occurs; After reme() is called, elementdata (index) will be used to get the value. At this time, if index < 0, exceptions will be thrown directly.
2.clear
It should be noted that, compared with the remove () method, clear () only sets each bit of the array to null, and the length of elementdata remains unchanged:
public void clear() {
modCount++;
// 把数组每一位都设置为null
for (int i = 0; i < size; i++)
elementData[i] = null;
size = 0;
}
3.removeAll / retainAll
public boolean removeAll(Collection<?> c) {
Objects.requireNonNull(c);
return batchRemove(c,false);
}
public boolean retainAll(Collection<?> c) {
Objects.requireNonNull(c);
return batchRemove(c,true);
}
Both methods depend on the batchremove() method:
private boolean batchRemove(Collection<?> c,boolean complement) {
final Object[] elementData = this.elementData;
int r = 0,w = 0;
boolean modified = false;
try {
// 1.遍历本集合
for (; r < size; r++)
// 如果新增集合存在与本集合存在相同的元素，有两种情况
// 1.removeAll，complement=false：直接跳过该元素
// 2.retainAll，complement=true：把新元素插入原集合头部
if (c.contains(elementData[r]) == complement)
elementData[w++] = elementData[r];
} finally {
// 2.如果上述操作中发生异常，则判断是否已经完成本集合的遍历
if (r != size) {
System.arraycopy(elementData,r,w,size - r);
w += size - r;
}
if (w != size) {
// 3.将数组剩下的位置都改为null
for (int i = w; i < size; i++)
elementData[i] = null;
modCount += size - w;
size = w;
modified = true;
}
}
return modified;
}
The above three processes may be a little difficult to understand. Let's assume that this is retailall(), so complexity = true. The execution process is as follows:
Similarly, if removeall(), w will always be 0, and finally all locations of elementdata will be set to null.
In other words, if no exception occurs during the traversal, the second step will be skipped and the third step will be entered directly.
Of course, there is no exception. Therefore, after the traversal is completed, r = size. If the traversal reaches r = 2, that is, after entering the if branch, the program has an exception and enters the finally block before the traversal is completed, the second step will be entered first, that is, the following process:
Finally, the array will become {C, C, D, null}, and only the last d will be deleted.
4.removeIf
This is a new method after jdk8:
public boolean removeIf(Predicate<? super E> filter) {
Objects.requireNonNull(filter);
int removeCount = 0;
final BitSet removeSet = new BitSet(size);
final int expectedModCount = modCount;
final int size = this.size;
// 遍历集合，同时做并发修改检查
for (int i=0; modCount == expectedModCount && i < size; i++) {
@SuppressWarnings("unchecked")
final E element = (E) elementData[i];
// 使用 lambda 表达式传入的匿名方法校验元素
if (filter.test(element)) {
removeSet.set(i);
removeCount++;
}
}
// 并发修改检测
if (modCount != expectedModCount) {
throw new ConcurrentModificationException();
}
// 是否有有需要删除的元素
final boolean anyToRemove = removeCount > 0;
if (anyToRemove) {
// 新容量为旧容量-删除元素数量
final int newSize = size - removeCount;
// 把被删除的元素留下的空位“补齐”
for (int i=0,j=0; (i < size) && (j < newSize); i++,j++) {
i = removeSet.nextClearBit(i);
elementData[j] = elementData[i];
}
// 将删除的位置设置为null
for (int k=newSize; k < size; k++) {
elementData[k] = null;
}
this.size = newSize;
if (modCount != expectedModCount) {
throw new ConcurrentModificationException();
}
modCount++;
}
return anyToRemove;
}
5.set
public E set(int index,E element) {
rangeCheck(index);
E oldValue = elementData(index);
elementData[index] = element;
return oldValue;
}
6.replaceAll
This is also a new method in jdk8:
public void replaceAll(UnaryOperator<E> operator) {
Objects.requireNonNull(operator);
final int expectedModCount = modCount;
final int size = this.size;
// 遍历，并使用lambda表达式传入的匿名函数处理每一个元素
for (int i=0; modCount == expectedModCount && i < size; i++) {
elementData[i] = operator.apply((E) elementData[i]);
}
if (modCount != expectedModCount) {
throw new ConcurrentModificationException();
}
modCount++;
}
7、 Iteration
ArrayList re implements its own iterator instead of continuing to use the iterator provided by abstractlist.
Like abstractlist, the iterator internal class implemented by ArrayList is still the basic iterator ITR and the enhanced iterator listitr. It is basically the same as the two internal classes with the same name in abstractlist, but some adjustments have been made to the method according to the characteristics of ArrayList: for example, the call to the internal method has been cancelled in some places, and the elementdata subscript has been operated directly.
This one can refer to the previous article or look at the source code, which will not be repeated here.
2.forEach
This is an override of the foreach method in the Iterable interface of the parent interface of the collection. The implementation of ArrayList is as follows:
public void forEach(Consumer<? super E> action) {
Objects.requireNonNull(action);
// 获取 modCount
final int expectedModCount = modCount;
@SuppressWarnings("unchecked")
final E[] elementData = (E[]) this.elementData;
final int size = this.size;
for (int i=0; modCount == expectedModCount && i < size; i++) {
// 遍历元素并调用lambda表达式处理元素
action.accept(elementData[i]);
}
// 遍历结束后才进行并发修改检测
if (modCount != expectedModCount) {
throw new ConcurrentModificationException();
}
}
3. Problems in iterative deletion
So far, we know that there are three iterative methods:
If we delete the nodes of the collection in the loop, only the iterator can delete them normally, and other problems will occur.
forEach
Let's try foreach ():
ArrayList<String> arrayList1 = new ArrayList<>(Arrays.asList("A","B","C","D"));
arrayList1.forEach(arrayList1::remove); // java.util.ConcurrentModificationException
It can be seen that a concurrentmodificationexception will be thrown. Let's go back to the code of foreach():
public void forEach(Consumer<? super E> action) {
// 获取 modCount
final int expectedModCount = modCount;
... ...
for () {
// 遍历元素并调用lambda表达式处理元素
action.accept(elementData[i]);
}
... ...
// 遍历结束后才进行并发修改检测
if (modCount != expectedModCount) {
throw new ConcurrentModificationException();
}
}
Since expectedmodcount = modcount is set at the beginning of method execution, modcount will not be performed until the end of loop processing= In this way, if we do some structural operations on the element in the anonymous function, resulting in the increase of modcount, we will finally find that the modcount after the end of the cycle is inconsistent with the modcount obtained at the beginning, so we will throw a concurrentmodificationexception.
For loop
Write an example first:
ArrayList<String> arrayList1 = new ArrayList<>(Arrays.asList("A","D"));
for (int i = 0; i < arrayList1.size(); i++) {
arrayList1.remove(i);
}
System.out.println(arrayList1); // [B,D]
As you can see, the deletion of B and C is skipped. In fact, this problem is similar to the problem encountered by the remove() method in the iterator ITR of abstractlist:
In ITR of abstractlist, each deletion will lead to "shortening" of the array. The previous element of the deleted element will "fill in the blank" after remove() and fall to the position corresponding to the subscript of the deleted element, that is, if there are two elements a and B, after deleting element a with subscript 0, B will fall to the position with subscript 0.
As mentioned above, remove() of ArrayList calls fastremove() method. We can see if it is the culprit:
private void fastRemove(int index) {
... ...
// 如果不是在数组末尾删除
if (numMoved > 0)
// 数组被缩短了
System.arraycopy(elementData,numMoved);
elementData[--size] = null;
}
Therefore, the change of element subscript caused by array "shortening" is the root of the problem. In other words, if you do not call system Arraycopy () method will not cause this problem in theory, so we can try to reverse delete:
ArrayList<String> arrayList1 = new ArrayList<>(Arrays.asList("A","D"));
// 反向删除
for (int i = arrayList1.size() - 1; i >= 0; i--) {
arrayList1.remove(i);
}
System.out.println(arrayList1); // []
It can be seen that reverse deletion is no problem.
8、 Other
1.indexOf / lastIndexOf / contains
Compared with abstractlist, ArrayList no longer uses iterators, but is rewritten into a for loop according to subscripts:
// indexOf
public int indexOf(Object o) {
if (o == null) {
for (int i = 0; i < size; i++)
if (elementData[i]==null)
return i;
} else {
for (int i = 0; i < size; i++)
if (o.equals(elementData[i]))
return i;
}
return -1;
}
// lastIndexOf
public int lastIndexOf(Object o) {
if (o == null) {
for (int i = size-1; i >= 0; i--)
if (elementData[i]==null)
return i;
} else {
for (int i = size-1; i >= 0; i--)
if (o.equals(elementData[i]))
return i;
}
return -1;
}
As for the contains () method, since indexof () has been implemented, it is not necessary to continue to use the iterative search provided by abstractcollection, but instead:
public boolean contains(Object o) {
return indexOf(o) >= 0;
}
2.subList
Like iterator (), sublist () returns a special internal class sublist. The same implementation has been made in abstractlist, but some improvements have been made in ArrayList. The general logic is similar to that in abstractlist. This part has been mentioned earlier, so we won't spend more time here.
3.sort
public void sort(Comparator<? super E> c) {
final int expectedModCount = modCount;
Arrays.sort((E[]) elementData,c);
if (modCount != expectedModCount) {
throw new ConcurrentModificationException();
}
modCount++;
}
In Java, the collection sorting element class either implements the comparable interface, or writes a comparator comparator by itself. The parameter of this function indicates that the type is a comparator, so you can only pass custom comparators. After jdk8, the comparator class provides some default implementations, which can be similar to comparator Reverseorder(), or directly pass in an anonymous method with a lambda expression.
4.toArray
The toarray() method has been basically implemented in the parent class abstractcollection of abstractlist. ArrayList rewrites the method according to its own situation:
public Object[] toArray() {
// 直接返回 elementData 的拷贝
return Arrays.copyOf(elementData,size);
}
public <T> T[] toArray(T[] a) {
// 如果传入的素组比本集合的元素数量少
if (a.length < size)
// 直接返回elementData的拷贝
return (T[]) Arrays.copyOf(elementData,a.getClass());
// 把elementData的0到size的元素覆盖到传入数组
System.arraycopy(elementData,a,size);
// 如果传入数组元素比本集合的元素多
if (a.length > size)
// 让传入数组size位置变为null
a[size] = null;
return a;
}
5.clone
ArrayList implements the Cloneable interface, so it should have its own clone () method:
public Object clone() {
try {
// Object.clone()拷贝ArrayList
ArrayList<?> v = (ArrayList<?>) super.clone();
// 拷贝
v.elementData = Arrays.copyOf(elementData,size);
v.modCount = 0;
return v;
} catch (CloneNotSupportedException e) {
// this shouldn't happen,since we are Cloneable
throw new InternalError(e);
}
}
Note that the ArrayList obtained through clone () is not the same instance, but uses arrays The element object obtained by copyof () is the same object. Let's take an example:
public static void main(String[] args) throws NoSuchMethodException,InvocationTargetException,illegalaccessexception {
ArrayList<MyBean> arrayList1 = new ArrayList<>(Arrays.asList(new MyBean()));
ArrayList<MyBean> arrayList2 = (ArrayList<MyBean>) arrayList1.clone();
System.out.println(arrayList1); // [$MyBean@782830e]
System.out.println(arrayList2); // [$MyBean@782830e]
System.out.println(arrayList1 == arrayList2); // false
arrayList1.add(new MyBean());
System.out.println(arrayList1); // [MyBean@782830e,$MyBean@470e2030]
arrayList2.add(new MyBean());
System.out.println(arrayList2); // [$MyBean@782830e,$MyBean@3fb4f649]
}
public static class MyBean {}
You can see that arraylist1 = = arraylist2 is false, which means that there are two instances of ArrayList, but the first mybean inside is both$ MyBean@782830e , the description is the same instance.
6.isEmpty
public boolean isEmpty() {
return size == 0;
}
9、 Summary
The bottom layer of ArrayList is the object [] array, which is marked by randomaccess interface and has the function of high-speed random access according to subscripts;
The capacity expansion of ArrayList is 1.5 times. Only when the initial capacity specified by the construction method is 0, the capacity less than 10 will appear in the first capacity expansion, otherwise the capacity after the first capacity expansion must be greater than or equal to 10;
ArrayList has a volume reduction method trimtosize(), but it will not be called on its own initiative. After calling, the capacity will shrink back to the actual number of elements, and the minimum capacity will shrink to the default capacity of 10;
The addition of ArrayList may cause the array to "expand" due to capacity expansion. Similarly, not all deletions will cause the array to "shrink": when the deleted element is the end of the queue element, or the clear () method will only set the corresponding place of the subscript to null, but will not really delete the position of the array;
Deleting an ArrayList in a loop - to be exact, any structural operation that causes a change in modcount - may cause an accident: