Recommended reading:
- Poured over these five JVM knowledge, the interviewer must think you are very NB (dry goods | recommend collection)
ArrayList overview
ArrayList: ArrayList: ArrayList: ArrayList: ArrayList: ArrayList: ArrayList: ArrayList: ArrayList: ArrayList: ArrayList: ArrayList Today, let’s talk about its underlying source code.
ArrayList is more accurately described as a dynamic array implementation, the use of the word dynamic, to fully reflect its characteristics.
Another is that ArrayLists are not thread-safe, so they are more efficient, but is this absolute? The answer is no.
ArrayList underlying source code
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable{
private static final long serialVersionUID = 8683452581122892189L;
private static final int DEFAULT_CAPACITY = 10;
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;
}
Copy the code(1) ArrayList inherits AbstractList class and implements RandomAccess, Cloneable, Serializable interfaces. RandomAccess enables it to access quickly.
(2) Cloneable is actually a tag interface. Clone can be successfully cloned only after implementing this interface, overwriting the Clone method of Object in the class, and calling the Clone method in the class. If this interface is not implemented, Will throw CloneNotSupportedException abnormal (cloning is not supported).
(3) Serializable is a serialization interface, supporting serialization and deserialization.
DEFAULT_CAPACITY is the size of the default initialization collection for ArrayList.
(5) EMPTY_ELEMENTDATA is an empty object array used to share empty array instances of empty instances.
DEFAULTCAPACITY_EMPTY_ELEMENTDATA is used when the collection is created using the default constructor
(7) elementData An array object used to store the current data.
(8) size is the size of the set.
(9) When the number of elements in the set exceeds the specified length of the array, the array will be expanded. The expansion operation is the reason why the storage operation of ArrayList is slow, especially when the amount of data is large, each expansion consumes more and more time.
ArrayList constructor source code
ArrayList(int initialCapacity)
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); }}Copy the codeIf the value is greater than zero, initialize an array object of that length and assign it to elementData. If it is equal to zero, assign the EMPTY_ELEMENTDATA object to elementData. Otherwise, throw an exception.
(2) This constructor is usually used to initialize a large set of data.
ArrayList()
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
Copy the code(1) Assign DEFAULTCAPACITY_EMPTY_ELEMENTDATA to elementData
ArrayList(Collection c)
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 codeThere are two main things that are done here: (1) The collection C is first converted to an array and then assigned to the elementData array object.
(2) Then determine whether size and are equal and not equal to 0. If yes, perform the assignment of data and reassign to the array object elementData; otherwise, directly assign the empty array object to elementData.
ArrayList method source analysis
The add () method
public boolean add(E e) {
ensureCapacityInternal(size + 1);
elementData[size++] = e;
return true;
}
Copy the code(1) Execute the ensureCapacityInternal method to determine whether the original array object needs to be expanded.
(2) Add e object to elementData array object.
Let’s look at the source code for the Enrecapact Internal method.
private void ensureCapacityInternal(int minCapacity) {
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
Copy the codeEnsureExplicitCapacity method and calculateCapacity method are called in Enrecapacity Internal, so let’s look at the calculateCapacity method
private static int calculateCapacity(Object[] elementData, int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
return Math.max(DEFAULT_CAPACITY, minCapacity);
}
return minCapacity;
}
Copy the code(1) The task here is mainly to calculate the size of the capacity. First determine whether the elementData array object has an initial size. If not, the larger of DEFAULT_CAPACITY or minCapacit is the capacity.
EnsureExplicitCapacity:
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
Copy the code(1) Run modCount increment, modCount is the number of times the current list structure has been modified.
(2) If minCapacity is greater than elementData.length, perform expansion; otherwise, exit this method and add elements.
Grow ();
private void grow(int minCapacity) {
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1);
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
elementData = Arrays.copyOf(elementData, newCapacity);
}
Copy the code(1) Here, the length of the original elementData is assigned to a variable oldCapacity, and then the original length is increased by 1.5 times and paid to oldCapacity.
(2) Determine whether minCapacity is greater than newCapacity. If yes, assign minCapacity to newCapacity. Why do we do this? After the previous layer upon layer analysis, minCapacity is the minimum length allowed after expansion, that is, the minimum length of actual stored data. If the expanded length is still smaller than minCapacity, you can only use minCapacity as the container length.
(3) Then determine whether newCapacity is greater than MAX_ARRAY_SIZE, if yes, set the expanded length to the maximum available length.
(4) Copy, expand, build a new array.
The hugeCapacity method is called by the grow method.
private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
}
Copy the code(1) Check whether minCapacity is less than zero and then throw an exception. Then compare whether the minimum length allowed by the container is greater than MAX_ARRAY_SIZE. If yes, assign the maximum value of Integer to minCapacity as the maximum length of the container.
Add (int index, E Element) method
public void add(int index, E element) {
rangeCheckForAdd(index);
ensureCapacityInternal(size + 1); // Increments modCount!!
System.arraycopy(elementData, index, elementData, index + 1,size - index);
elementData[index] = element;
size++;
}
Copy the code(1) here is mainly to do three things, the first thing is to determine whether a subscript crossing the line, if is thrown IndexOutOfBoundsException anomalies.
(2) Then it is to determine whether expansion is needed. This method is the same as the above method, which has been said and will not be repeated.
(3) Finally, the array object index is moved back one bit, adding the element to the specified position.
Let’s look at the source code for rangeCheckForAdd
private void rangeCheckForAdd(int index) {
if (index > size || index < 0)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
Copy the code(1) If index > size or index < 0 is true, throw an out-of-bounds exception directly.
AddAll (Collection c) method
public boolean addAll(Collection<? extends E> c) {
return addAll(this.size, c);
}
public boolean addAll(int index, Collection<? extends E> c) {
rangeCheckForAdd(index);
int cSize = c.size();
if (cSize==0)
return false;
checkForComodification();
parent.addAll(parentOffset + index, c);
this.modCount = parent.modCount;
this.size += cSize;
return true;
}
private void checkForComodification() {
if(ArrayList.this.modCount ! = this.modCount) throw new ConcurrentModificationException(); }Copy the codeAddAll (this.size, c); addAll(this.size, c); addAll(this.size, c);
(2) Then check whether the size of c is greater than 0, and return false if it is equal to 0.
(3) check whether to modify the number of equal, if not equal to direct the throw ConcurrentModificationException (concurrent modification) anomaly, this is when we use a list iterator cycle, in which add/remove elements, using the method of the list will appear this mistake.
(4) Insert the element into the array, assign the number of changes to modCount, and finally add one to the size
(5) During the add operation, determine whether the subscript is out of bounds and whether the capacity needs to be expanded. If the capacity needs to be expanded, copy the array and expand by half by default. If the capacity is not expanded by half, use the target size as the capacity after expansion and then set the corresponding subscript element value.
The get () method
public E get(int index) {
rangeCheck(index);
return elementData(index);
}
private void rangeCheck(int index) {
if (index >= size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
E elementData(int index) {
return (E) elementData[index];
}
Copy the code(1) This is very simple to determine whether the index is out of bounds, then throw an exception, and finally return the specified index element value.
The set () method
public E set(int index, E element) {
rangeCheck(index);
E oldValue = elementData(index);
elementData[index] = element;
return oldValue;
}
Copy the code(1) first check whether the boundary is crossed, then fetch the value of the original index position as oldValue, set the new value element to index position, and finally return the oldValue oldValue.
Remove () method
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);
elementData[--size] = null; // clear to let GC do its work
return oldValue;
}
Copy the codeModCount = modCount = modCount = modCount = modCount = modCount
(2) Then calculate the number of elements after the index position, then move the element after the index position forward one, and finally return the old value.
Remove (Object o) method
public boolean remove(Object o) {
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;
}
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
}
Copy the code(1) This method is relatively simple according to the object deletion, first determine whether the o object is null object, if null, traverse the set of elements, whether there is a null value, delete the specified object method is fastRemove, the principle is to calculate the number of elements after the index position. It then moves each element after index one bit forward, and finally assigns the last bit to null.
(2) If the o object is not null, the same logic is executed, so why write separately? If it is null, the null pointer will be declared as an exception.
The Iterator Iterator
public Iterator<E> iterator() {
return new Itr();
}
private class Itr implements Iterator<E> {
int cursor;
int lastRet = -1;
int expectedModCount = modCount;
Itr() {}
public boolean hasNext() {
returncursor ! = size; } @SuppressWarnings("unchecked")
public E next() {
checkForComodification();
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];
}
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();
}
}
}
Copy the codeInt cursor is the index of the next element to be returned, and int lastRet = -1 is the index of the last element to be returned.
(2) The hasNext method determines whether the next element exists by determining whether the following subscript is an array size.
(3) The next method obtains the next element. First, the checkForComodification method is called to check whether The Times of modification are consistent, and then the subscript of the next element is defined and judged. If the subscript is greater than the number of elements contained in ArrayList, Throw NoSuchElementException, get the elementData object in the ArrayList, and check the index again. If the index is not the same, the array has been modified. Refers to the index of the next element, and finally defines lastRet as the index of the returned element, and then returns the value of the index.
(4) remove remove the current element, first judge whether the subscript lastRet of the last element is less than 0, if it is true, the element does not exist, throw an exception, and then call checkForComodification to judge whether the modification times are consistent. Then the remove method of ArrayList is called, and finally the values of CURSOR, lastRet, and expectedModCount are updated again.
Welcome to pay attention to the public number: the growth of the old boy road, selected dry goods regularly every week!
