1. AzrrayList brief introduction
java.util.ArrayList It's a An array of the queue , amount to The dynamic array . And Java The array in , It has Capacity can grow dynamically 、 Slow addition and deletion of elements 、 Quick search Characteristics .
ArrayList Inherited from AbstractList, Realized List、 RandomAccess、 Cloneable、java.io.Serializable These interfaces .
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable{
--- omit ---
}ArrayListInheritedAbstractListAbstract method , Realized List Interface , Provides relevant add to 、 Delete 、 modify 、 Traverse And so on .RandomAccessIt's a logo interface , Indicates the implementation of this interface List Collection is support Fast random access Of . stayArrayListin , We can quickly get the element object through the element's ordinal number , This is fast random access .ArrayListRealizedCloneableInterface , That overrides the functionclone(), Can be cloned .ArrayListRealizedjava.io.SerializableInterface , It meansArrayListSupport serialization , Can be transmitted by serialization .
Tips：ArrayListOperations in are not thread safe ！ It is recommended to use in single threadArrayList, Choose to use in multithreading Vector perhapsCopyOnWriteArrayList.
2. ArrayList Analysis of source code （JDK 1.8）
2.1 Member attribute
// Default capacity size
private static final int DEFAULT_CAPACITY = 10;
// ArrayList An empty array shared by empty instances
private static final Object[] EMPTY_ELEMENTDATA = {};
// ArrayList An empty array shared by empty instances , Empty instance for default size .
// And EMPTY_ELEMENTDATA Separate , So you can see how much space you need to create when you add the first element .
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
// Real storage ArrayList An array of elements in
transient Object[] elementData;
// ArrayList The number of elements contained , Notice that it's not elementData The length of
private int size;
// The maximum length of an array
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;AbstractList The only attribute in an abstract class ：
// Express elementData Number of changes , Every time add perhaps remove Its value will add 1
protected transient int modCount = 0;Why? size It's not used to mark elementData The length of the array ？
stay Java in , Generally speaking ：
lengthAttributes are for arrays , For example, in the following source codeelementData.lengthExpresselementDataLength of array .length()Method is for Strings , You can calllength()Get string length .size()Methods are for generic collections , You can callsize()To get the number in the collection .
such , It's easy to understand why size No ArrayList The length of the , It's not easy to remember .
2.2 Construction method
ArrayList There are three ways to initialize ：
/**
* Constructors with parameters
*/
public ArrayList(int initialCapacity) {
if (initialCapacity > 0) {
// Initialization capacity is greater than 0, establish initialCapacity Array of sizes
this.elementData = new Object[initialCapacity];
} else if (initialCapacity == 0) {
// Initialization capacity equal to 0, Create an empty array
this.elementData = EMPTY_ELEMENTDATA;
} else {
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
}
}
/**
* Default parameterless constructor （ Initialization capacity size not specified ）, Use initial capacity 10 Construct an empty list .
*/
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
/**
* Use Collection Set to initialize ArrayList
*/
public ArrayList(Collection<? extends E> c) {
// Convert collection to array
elementData = c.toArray();
// If the length of the array size It's not equal to 0
if ((size = elementData.length) != 0) {
// If not Object Type data
if (elementData.getClass() != Object[].class)
// Recreate a size Array of sizes .
// And will not be Object[] Contents of array ,Copy To the new is Object[] Array of
elementData = Arrays.copyOf(elementData, size, Object[].class);
} else {
// Replace with empty array
this.elementData = EMPTY_ELEMENTDATA;
}
}From the above analysis we can see that EMPTY_ELEMENTDATA And DEFAULTCAPACITY_EMPTY_ELEMENTDATA The difference between .
EMPTY_ELEMENTDATA When we instantiate an object, we specify the capacity 0, When adding 1 After elements , that elementData.length=1.
DEFAULTCAPACITY_EMPTY_ELEMENTDATA Indicates that instantiation is a parameterless construct , No capacity specified , Calling add Method to add 1 After elements, the default expansion capacity is 10, namely elementData.length=10.
2.3 Additive elements
/**
* Add elements directly to the end of the array .
*/
public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
/**
* Adds an element to the specified index Location .
*/
public void add(int index, E element) {
// Yes index Do a boundary check
rangeCheckForAdd(index);
ensureCapacityInternal(size + 1); // Increments modCount!!
// native Static methods , primary elementData Array of index（ contain ） Later data , Copy to target elementData Array of index + 1 After the position
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
// Will be taken from index All members after the start move one bit back , take element Insert into index Location .
elementData[index] = element;
// Last size+1
size++;
}
/**
* Appends all elements in the specified collection to the end of this list .
*/
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;
return numNew != 0;
}
/**
* Start at the designated location , Inserts all elements in the specified collection into this list .
*/
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);
System.arraycopy(a, 0, elementData, index, numNew);
size += numNew;
return numNew != 0;
} The source code calls a lot of arraycopy() Method , Its specific use can refer to from System.arraycopy The consolidation triggered ： Object reference And object The difference between One article .
2.4 Remove elements
/**
* Delete the element at the specified position in the list . Move any subsequent elements to the left （ Subtract from its index 1）.
*/
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;
// Elements removed from the list
return oldValue;
}
/**
* Delete the specified element from the list .
*/
public boolean remove(Object o) {
// If the list does not contain the element , Then it will not change .
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++)
// return true, This list contains the specified elements
if (o.equals(elementData[index])) {
fastRemove(index);
return true;
}
}
return false;
}
// It skips the boundary check without returning the removed value .
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;
}
/**
* Remove all elements from the list .
*/
public void clear() {
modCount++;
// Set the values of all elements in the array to null
for (int i = 0; i < size; i++)
elementData[i] = null;
size = 0;
}
/**
* Remove all indexes from this list as fromIndex （ contain ） and toIndex Between the elements .
*/
protected void removeRange(int fromIndex, int toIndex) {
modCount++;
int numMoved = size - toIndex;
System.arraycopy(elementData, toIndex, elementData, fromIndex,
numMoved);
int newSize = size - (toIndex-fromIndex);
for (int i = newSize; i < size; i++) {
elementData[i] = null;
}
size = newSize;
}
/**
* Removes all elements contained in the specified collection from this list .
*/
public boolean removeAll(Collection<?> c) {
Objects.requireNonNull(c);
// If this list is modified, return to true
return batchRemove(c, false);
}2.5 ArrayList Expansion mechanism
You can find ,ArrayList When adding elements , Will be called ensureCapacityInternal Method .
With add(E e) Methods as an example ：
/**
* Add elements directly to the end of the array .
*/
public boolean add(E e) {
// Check whether expansion is needed
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}2.5.1 ensureCapacityInternal() and ensureExplicitCapacity()
see ensureCapacityInternal() Method ：
// Get the minimum capacity to meet the demand
private void ensureCapacityInternal(int minCapacity) {
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
private static int calculateCapacity(Object[] elementData, int minCapacity) {
// elementData It's an empty list
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
// Expand the array to DEFAULT_CAPACITY(10)
return Math.max(DEFAULT_CAPACITY, minCapacity);
}
// return size+1
return minCapacity;
}
// Determine whether capacity expansion is needed
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
if (minCapacity - elementData.length > 0)
// call grow Method for real expansion
grow(minCapacity);
}- When the 1 Elements to ArrayList In the middle of the day ,minCapacity by size+1=0,elementData Or empty? list,elementData.length=0 , All will be executed
return Math.max(DEFAULT_CAPACITY, minCapacity);,minCapacity Turn into 10. here ,minCapacity - elementData.length > 0establish , So it's going to entergrow(minCapacity)Method to really expand the capacity of . - When the 2 Element time ,minCapacity by size+1 =2, because elementData.length After adding the first element, it has been expanded to 10 了 . here ,
minCapacity - elementData.length > 0Don't set up , Not executegrow(minCapacity)Method , It won't expand . - Add para 3、4、5...... To the first 10 Element time , Still not expanding , The capacity of the array is still 10.
Until... Is added 11 Elements ,minCapacity - elementData.length > 0 establish , perform grow Methods to expand capacity .
2.5.2 grow()
grow The way is the whole ArrayList The core of expansion ：
private void grow(int minCapacity) {//11
// oldCapacity Old capacity
int oldCapacity = elementData.length;//10
// Displacement operators are much faster than ordinary operators .>> It means that you will oldCapacity Moves to the right one ,(oldCapacity >> 1) amount to oldCapacity /2
// Update new capacity to old capacity 1.5 times
int newCapacity = oldCapacity + (oldCapacity >> 1);
// If the new capacity is still less than the minimum required capacity
if (newCapacity - minCapacity < 0)
// The direct minimum requirement capacity is used as the new capacity of the array
newCapacity = minCapacity;
// If minCapacity Greater than maximum capacity , The new capacity is `Integer.MAX_VALUE`, otherwise , The new capacity is MAX_ARRAY_SIZE That is to say `Integer.MAX_VALUE - 8`.
// The new capacity is greater than MAX_ARRAY_SIZE,
if (newCapacity - MAX_ARRAY_SIZE > 0)
// perform hugeCapacity() Method
newCapacity = hugeCapacity(minCapacity);
elementData = Arrays.copyOf(elementData, newCapacity);
}
// Compare minCapacity and MAX_ARRAY_SIZE
private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0)
throw new OutOfMemoryError();
// minCapacity > MAX_ARRAY_SIZE, The size of the new array is Integer.MAX_VALUE
// otherwise , The size of the new array is MAX_ARRAY_SIZE
// MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
}Thus we can see that ,ArrayList The default expansion size is the original size 1.5 About times （oldCapacity Even, it must be 1.5 times , An odd number must be equal to 1.5 About times ）.
- If the expansion of newCapacity Still less than minCapacity, Then size the array to minCapacity size .
- If minCapacity The value of the MAX_ARRAY_SIZE and Integer.MAX_VALUE Between , So the new array allocation Integer.MAX_VALUE size , Otherwise, distribute MAX_ARRAY_SIZE.
">>"（ Shift right operator ）：”>>1“ To the right 1 position ; Move right n Bits are equal to dividing by 2 Of n Power .
2.6 ensureCapacity
From the above source analysis , In the use of Arraylist When initializing capacity , It will go through a series of logical judgments before expansion . If the amount of data is large , Isn't the operation efficiency very low .
and ensureCapacity() Method , Let's set it up in advance Arraylist Size , This can greatly improve the initialization speed .
public void ensureCapacity(int minCapacity) {
// In this way, we can judge whether we call the parameterless constructor when we instantiate . If not ,minExpand=0; If it is ,minExpand=10.
int minExpand = (elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
// any size if not default element table
? 0
// larger than default for default empty table. It's already
// supposed to be at default size.
: DEFAULT_CAPACITY;
// We set up minCapacity Greater than minExpand Before expansion
if (minCapacity > minExpand) {
ensureExplicitCapacity(minCapacity);
}
} Best in add A lot of elements were used before ensureCapacity Method , To reduce the number of incremental reallocation .
Let's test the use of ensureCapacity The difference between before and after ：
public class EnsureCapacityTest {
public static void main(String[] args) {
ArrayList<Object> list = new ArrayList<Object>();
final int minCapacity = 10000000;
long startTime = System.currentTimeMillis();
for (int i = 0; i < minCapacity; i++) {
list.add(i);
}
long endTime = System.currentTimeMillis();
System.out.println(" Don't use ensureCapacity Time consuming ：" + (endTime - startTime));
list = new ArrayList<Object>();
long startTime1 = System.currentTimeMillis();
list.ensureCapacity(minCapacity);
for (int i = 0; i < minCapacity; i++) {
list.add(i);
}
long endTime1 = System.currentTimeMillis();
System.out.println(" Use ensureCapacity Time consuming ：" + (endTime1 - startTime1));
}
}Running results ：
Don't use ensureCapacity Time consuming ：2471
Use ensureCapacity Time consuming ：2893 Traverse
ArrayList It mainly supports three traversal modes ：
- foreach Loop traversal
Integer value = null;
for (Integer integ:list) {
value = integ;
}- Iterator traversal
Integer value = null;
Iterator iter = list.iterator();
while (iter.hasNext()) {
value = (Integer)iter.next();
}- Random access , Traverse through index values
because ArrayList Realized RandomAccess Interface , It supports random access to elements through index values .
Integer value = null;
int size = list.size();
for (int i=0; i<size; i++) {
value = (Integer)list.get(i);
}4 fail-fast Mechanism
Fast failure (fail-fast) yes Java An error detection mechanism in a collection . Its characteristic is to traverse Java When the collection , Modification of values is not allowed , Otherwise it will throw ConcurrentModificationException abnormal .
For example, in Multithreading In development , Threads A Passing iterator Traverse a collection , Threads B It happens that the contents of the collection have been modified , So thread A Continue to traverse the collection and throw ConcurrentModificationException abnormal , produce fail-fast event .
see AbstractList Source code ：
public abstract class AbstractList<E> extends AbstractCollection<E> implements List<E> {
... ...
// Used to record List Number of changes ： Every modification ( add to / Delete and other operations ), take modCount+1
protected transient int modCount = 0;
// return List Corresponding iterator . actually , Is to return Itr object .
public Iterator<E> iterator() {
return new Itr();
}
// Itr yes Iterator( iterator ) Implementation class of
private class Itr implements Iterator<E> {
int cursor = 0;
int lastRet = -1;
// The record value of the modified number .
// Every time a new Itr() Object time , When the object is created, it will be saved modCount.
int expectedModCount = modCount;
public boolean hasNext() {
return cursor != size();
}
public E next() {
checkForComodification();
--- omit ---
}
public void remove() {
if (lastRet == -1)
throw new IllegalStateException();
checkForComodification();
--- omit ---
}
final void checkForComodification() {
// Every time I traverse List When it comes to the elements in , Will compare expectedModCount and modCount Whether it is equal or not .
// If not equal , Throw out ConcurrentModificationException abnormal , produce fail-fast event .
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
}
}
... ...
}so ,ArrayList When adding or deleting elements , Whether it's calling add()、remove() still clear() And so on , When it comes to modifying the number of elements in a collection , Will change modCount Value .
And every time the iterator iterates through the next element , Metropolitan detection modCount Is the variable expectedModCount value . If you modify the collection while it is traversed modCount Value , that modCount != expectedModCount , And then throw ConcurrentModificationException abnormal .
therefore , In multithreaded development , It is recommended to use java.util.concurrent Package to replace the thread safety class java.util Thread unsafe class under package . such as ArrayList The corresponding thread safety class is CopyOnWriteArrayList.
Special note , It's not only in multithreading that fail-fast event . Under single thread , If the content of the collection object is modified during traversal, it will also trigger fail-fast Mechanism .
foreach Loops are also traversed by means of iterators .
You should avoid writing code like this ：
List<String> list = new ArrayList<>();
list.add("a");
list.add("b");
for (String str : list) {
if("b".equals(str)){
list.remove(str);
}
}Reference resources
- ArrayList The source code parsing
- from System.arraycopy The consolidation triggered ： Object reference And object The difference between
- Java Collection Series 03 And ArrayList Detailed introduction ( The source code parsing ) And use examples
- Java Collection Series 04 And fail-fast summary ( adopt ArrayList To illustrate fail-fast Principle 、 terms of settlement )
