preface
In the previous article, we combed through the Kotlin collection interface. This article begins by combing through the specific collections that are commonly used.
Articles in this series:
Kotlin sets and 1 – The parent interface of the Collection class – Nuggets (juejin. Cn)
The body of the
Let’s start by looking at the List family:
From the above, we often use about the above five sets:
After a brief overview of the features of various lists, in this article we’ll take a look at how arrayLists work.
Annotation summary
ArrayList has about 100 lines of comments, which are fairly comprehensive. Here are some of them, and we’ll explain them in more detail in the source code analysis.
-
Mutable arrays implement the List interface as a collection of elements that can be null.
-
The size, isEmpty, get, set, iterator, listIterator method calls are constant time, independent of the number of elements; The time complexity of the add method call is O(n).
-
Each ArrayList instance has a capacity that is the size of the array used to hold elements. The capacity must be greater than or equal to the number of elements. Each time a new element is added to the ArrayList, the capacity is determined to grow, and the strategy for growth is considered, and there is a time cost.
-
ArrayList is asynchronous. When multiple threads access an ArrayList instance and at least one thread changes the list structure, synchronization must be performed externally. In this case, modifying the list structure refers to adding, deleting elements or changing the underlying array size. Only setting the value of the element does not modify the list structure.
-
If no corresponding thread-safe object exists, synchronizedList in Collections can be used to make an ordinary ArrayList instance a thread-synchronized object.
-
The iterator returned by ArrayList has a “fail fast” mechanism. After the ArrayList iterator is created, Anyone who is not modified by the iterator structure will directly quoted ConcurrentModificationException abnormal operation; Therefore, in the face of concurrent modification problems, iterators simply return failures cleanly and quickly, rather than risk uncertain behavior on uncertain problems for some time in the future.
-
At the same time, iterator’s “fail fast” mechanism is not completely guaranteed, since unsynchronized concurrent changes can occur.
All right, so this is a summary of the comments on ArrayList, which describes the features of ArrayList and the “fail fast” mechanism.
The source code parsing
Source code is not much, let’s take a look.
Saved arrays and constructors
// The default array size
private static final int DEFAULT_CAPACITY = 10;
// A shared empty array for empty instances
private static final Object[] EMPTY_ELEMENTDATA = {};
// It is also an empty array. We split it up to see how much it expands when the first element is added
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
// The size of the array is its capacity
transient Object[] elementData;
// The number of elements in the ArrayList, note that this is not the same as the capacity above
private int size;
Copy the codeThe use of two empty arrays, both of Object type, proves that generics can be erased at runtime in real time.
Another point is that the array holding the data is decorated transient, which means that when the ArrayList is serialized, the variable does not need to participate in the serialization.
// Initializer with capacity
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); }}// The no-argument constructor is an empty array
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
/ / to the Collection
public ArrayList(Collection<? extends E> c) {
elementData = c.toArray();
if((size = elementData.length) ! =0) {
if(elementData.getClass() ! =Object[].class)
elementData = Arrays.copyOf(elementData, size, Object[].class);
} else {
this.elementData = EMPTY_ELEMENTDATA; }}Copy the codeNote that the toArray() of a Collection is a method defined in the Collection, so each Collection is implemented differently.
Expansion process
After finishing initialization, let’s talk about the expansion process, expansion is also exquisite, such as one-time expansion, how to add a lot of elements at a time, is a gradual expansion or one-time expansion, we will analyze.
The expansion method is called:
// Add an element
public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
Copy the code// Add multiple elements
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);
size += numNew;
returnnumNew ! =0;
}
Copy the codeThe ensurecapityInternal method is called here:
private void ensureCapacityInternal(int minCapacity) {
// If the set is empty and the size to be expanded is less than 10, the minimum capacity is 10 by default
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
ensureExplicitCapacity(minCapacity);
}
Copy the code// Specify a specific capacity
private void ensureExplicitCapacity(int minCapacity) {
// Structure changes
modCount++;
// The desired capacity is larger than the current saved capacity
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
Copy the code/ / capacity
private void grow(int minCapacity) {
// The original capacity
int oldCapacity = elementData.length;
// The new capacity is 1.5 times the old capacity
int newCapacity = oldCapacity + (oldCapacity >> 1);
// If 1.5 times is not enough, use the expected value to avoid further expansion
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
// Copy to the new array
elementData = Arrays.copyOf(elementData, newCapacity);
}
Copy the codeIf the desired size is greater than 1.5 times, use the expected value directly to avoid secondary expansion, because array replication is required after expansion, which wastes resources.
Add and delete
After finishing the process of expansion, it also comes to the operation that each collection likes to see, namely add, delete, change and check.
// Add directly by default to the end of the array
public boolean add(E e) {
//modCount will be increased, i.e., data structure change operations will be increased
ensureCapacityInternal(size + 1);
elementData[size++] = e;
return true;
}
Copy the code// Insert an element somewhere
public void add(int index, E element) {
if (index > size || index < 0)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
ensureCapacityInternal(size + 1);
// Copy all elements from index to the last bit
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
elementData[index] = element;
/ / size of the ArrayList + +
size++;
}
Copy the code// Delete the element at index
public E remove(int index) {
if (index >= size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
// The data structure has changed
modCount++;
// Returns the deleted element
E oldValue = (E) elementData[index];
// Once the index element is deleted, all elements after the index element must be moved forward one bit
int numMoved = size - index - 1;
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
// Note that the array is assigned a new value, but the last value is the same as the previously saved value
// Assign null here to speed up GC
elementData[--size] = null;
return oldValue;
}
Copy the code// Deleting an element in the ArrayList deletes the first element iterated through
public boolean remove(Object o) {
// ArrayList can hold NULL, so null first
if (o == null) {
for (int index = 0; index < size; index++)
if (elementData[index] == null) {
fastRemove(index);
return true; }}else {
for (int index = 0; index < size; index++)
if (o.equals(elementData[index])) {
fastRemove(index);
return true; }}return false;
}
Copy the code// Modify the element in index position
public E set(int index, E element) {
if (index >= size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
// Note that this method is not worth modifying modCount
E oldValue = (E) elementData[index];
elementData[index] = element;
return oldValue;
}
Copy the code// This can be obtained directly from the array subscript
public E get(int index) {
if (index >= size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
return (E) elementData[index];
}
Copy the codeAdding, deleting, modifying, and checking an ArrayList is fairly simple. Note the following points:
-
Both add and delete modify the structure, that is, modCount changes.
-
Adding and deleting usually copy arrays, which takes a long time. This is the disadvantage of ArrayList, where arrayCopy uses the System. ArrayCopy method, which is very common.
-
Since the index corresponds to the index of the array, the query time is a constant time return, which is the advantage of an ArrayList.
Traverse the ArrayList
When it comes to iterating through an ArrayList, there are generally four ways. Let’s take a look:
- Use iterators for traversal
// use iterators for traversal
val list = arrayListOf(1.2.3.7.8.9)
val iterator = list.iterator()
while (iterator.hasNext()){
println("value = ${iterator.next()}")}Copy the codeThis traversal is definitely fine, so let’s take a look at the iterator obtained here:
// You'll find that every time you get an iterator, a new instance is created, and the iterator instance is not
// Get ahead of time
public Iterator<E> iterator() {
return new Itr();
}
Copy the codeWe’ll talk more about the implementation of iterators later.
- Iterate directly based on the ArrayList length
// Index ranges from 0 to size-1
for (index in 0 until list.size){
println("element = ${list[index]}")}Copy the codeThis type of traversal does not use iterators, but simply gets all the values.
- Quick traversal, and a for loop that we use a lot:
// The for loop iterates quickly
for (element in list){
println("element = $element")}Copy the codeFor this method, maybe used a lot, but it may not understand what principle is called, in fact, this is also called iterator, but why it can be written so succinctly, in fact, is Kotlin’s convention.
Let’s look at the Iterator code:
/ / interface
public interface Iterator<out T> {
// Operator overload
public operator fun next(): T
public operator fun hasNext(): Boolean
}
Copy the codeAs you can see, the next and hasNext methods are operator qualified. There is a convention involved here. As I mentioned in the previous article, the convention is simply to simplify calling functions, such as next and hasNext.
- Use forEach for traversal:
list.forEach { it -> println("$it")}Copy the codeThe forEach method is an extension function in the KT code. Let’s look at its implementation:
/ / forEach source code
public inline fun <T> Iterable<T>.forEach(action: (T) -> Unit): Unit {
for (element in this) action(element)
}
Copy the codeYou’ll notice that we’re using a for loop here, and then we’re using an iterator at the bottom.
Since our most common quick traversal uses iterators, let’s take a look at the implementation of iterators.
Iterator Itr for ArrayList
The default call to getIterator returns an Itr instance, so take a look at the Itr source code:
// Default iterator source code
private class Itr implements Iterator<E> {
// The number of elements in the ArrayList
protected int limit = ArrayList.this.size;
// The index of the next element to be returned
int cursor;
// The index of the element already returned, that is, the index of the element just traversed
int lastRet = -1;
// The expected number of structural changes
int expectedModCount = modCount;
// There is no next element
public boolean hasNext() {
return cursor < limit;
}
// Fetch the iterated elements
public E next() {
// Throw exception directly
if(modCount ! = expectedModCount)throw new ConcurrentModificationException();
int i = cursor;
if (i >= limit)
throw new NoSuchElementException();
Object[] elementData = ArrayList.this.elementData;
if (i >= elementData.length)
throw new ConcurrentModificationException();
//cursor increment 1, note that this is the index of the element to be retrieved next time
cursor = i + 1;
//lastRet represents the element subscript that has been returned
return (E) elementData[lastRet = i];
}
// Delete the currently returned element
public void remove() {
if (lastRet < 0)
throw new IllegalStateException();
if(modCount ! = expectedModCount)throw new ConcurrentModificationException();
try {
// Call the delete method of ArrayList
ArrayList.this.remove(lastRet);
// The next index traversed will be the index just deleted
cursor = lastRet;
// The returned element was deleted, so set it to -1
lastRet = -1;
// Finally the assignment
expectedModCount = modCount;
// Keep the correct number of elements
limit--;
} catch (IndexOutOfBoundsException ex) {
throw newConcurrentModificationException(); }}}Copy the codeIterator code above is very simple, but may remove elements and remove elements during throw ConcurrentModificationException, and the exception is the iterator “fail fast” mechanism, we have to have a good look at the causes of abnormal
Abnormal ConcurrentModificationException
The conditions for this exception are very simple, first it is only thrown in the iterator, and second it is thrown when expectedModCount is not equal to modCount.
The expectedModCount is assigned to modCount when the iterator instance is created, and the two values are set to the same only when the iterator’s remove method is called, so the exception will be thrown when the iterator is created and the modCount changes during the iterator traversal.
External modCount changes are structural changes known as add and remove, so remember: after iterating through an iterator, if you want to remove an element, use the iterator’s delete method.
Let’s look at an example:
val list = arrayListOf("hello"."android"."kotlin"."java"."arrayList")
for (element in list) {
// Delete a value that meets the requirement
if (element == "android") {
// Call the delete method of ArrayList
list.remove("android")}}Copy the codeAs expected, the following exception is thrown:
The correct way to write this is to use an iterator and delete the method using the iterator:
val list = arrayListOf("hello"."android"."kotlin"."java"."arrayList")
// Call the iterator
val iterator = list.iterator()
while (iterator.hasNext()){
if (iterator.next() == "android") {// Call the iterator's method
iterator.remove()
}
}
Copy the codeSo an ArrayList must use iterators when iterating over deletions.
If iterators are used for traversal, can we call ArrayList’s delete method without iterators during traversal?
conclusion
ArrayList is actually an array of stored data encapsulation, but the contents of the content is quite worth learning, such as expansion, add and delete elements, iterator traversal delete knowledge, etc., this content here, after continuing to analyze the source of various collections.