Preface

Today I’m going to learn a Java The most used class of collection class ArrayList , ArrayList Inherited AbstractList, And implemented List and RandomAccess Such as the interface ,

public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable

It’s a In array form Collection of stored data , It has the following characteristics ：

The arrays in a collection are ordered ;

The allowed element is null;

Allow duplicate data ;

Non-thread safety ;

In view of its characteristics , We follow up the source code step by step to analyze .

The source code parsing

Basic member variables

Let’s take a look at ArrayList Basic member variables of

transient Object[] elementData;
private static final int DEFAULT_CAPACITY = 10;
private int size;
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

elementData ： One object Array , Make up the ArrayList The underlying data structure , Because the array type is Object, So allow to add null . It is worth noting that , The modifier for a variable is transient , This means that the array cannot be serialized , But before ArrayList It implements the serialization interface , Can be initialized , Isn’t it contradictory , About this reason , We will talk about , Don’t worry. .

DEFAULT_CAPACITY : The initial capacity of the array

size ： Number of array elements

MAX_ARRAY_SIZE： Maximum capacity of array

After saying the variables , Begin to learn ArrayList Basic approach , We all know , The most important method of a set is to use the element Add, delete, change and check operation , I know how to do this , So we can basically understand the operation mechanism of the container .

Additive elements

ArrayList The most basic method of adding elements in is add(E e)

public boolean add(E e) {
// Adjust capacity
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}

The source code logic is relatively simple , The main thing is to adjust the capacity first , And put the element in the last position of the array .

Let’s take a look at how to adjust capacity ensureCapacityInternal(), Source code is as follows ：

private void ensureCapacityInternal(int minCapacity) {
// If it's an empty array , Initialize capacity , Take the default capacity and Number of current elements Maximum
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
ensureExplicitCapacity(minCapacity);
}
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// overflow-conscious code
if (minCapacity - elementData.length > 0)
// Not enough capacity , Do expansion
grow(minCapacity);
}
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
// New capacity is old capacity 1.5 times
int newCapacity = oldCapacity + (oldCapacity >> 1);
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
// minCapacity is usually close to size, so this is a win:
// Copy the contents of the element group into the new array
elementData = Arrays.copyOf(elementData, newCapacity);
}

You can see , The process of adjusting the capacity is actually to expand the capacity of the array , And finally called Arrays Of copyOf Method , Copy the contents of the element group into a new array ,

public static <T,U> T[] copyOf(U[] original, int newLength, Class<? extends T[]> newType) {
@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;
}

It’s like this in a graph

Except for the top add Outside method ,ArrayList It also provides several ways to add operations , Namely

// Add the element in the specified position
public void add(int index, E element) {
// Judge index Whether in size Within the scope of
rangeCheckForAdd(index);
ensureCapacityInternal(size + 1); // Increments modCount!!
// Whole copy , And move back one bit
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
elementData[index] = element;
size++;
}
// Add the entire collection
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;
}
// At a designated location , Add a collection
public boolean addAll(int index, Collection<? extends E> c) {
rangeCheckForAdd(index);
// Turn the collection into an array of objects
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;
}

These three methods are also insertion operations , But in fact, in the end, they all call System Of arraycopy Method to make a whole copy , This is a native Methods , The function is to copy the array as a whole , And moved back a bit . If there are many elements to copy , So it’s more performance intensive , It’s a bit of a bad thing .

therefore , In general ,ArrayList Scenarios suitable for sequential addition .

Query element

E elementData(int index) {
return (E) elementData[index];
}
public E get(int index) {
rangeCheck(index);
return elementData(index);
}

Query code is relatively simple , All are elements that directly return the corresponding position of the array , Do you take advantage of arrays querying elements by index , So it’s more efficient .

Expand ： When it comes to queries , Let’s make a point of knowledge , That’s the efficiency of traversing elements , I said before. ,ArrayList Realized RandomAccess Interface , therefore Traverse ArrayList The elements of get() Getting elements is more efficient than iterators , As for the reason , stay 《Java Collection classes ：“ Random access ” Of RandomAccess Interface 》 Introduction , There is no narration here .

Modifying elements

public E set(int index, E element) {
rangeCheck(index);
E oldValue = elementData(index);
elementData[index] = element;
return oldValue;
}

It’s also about manipulating arrays according to the index , Not much to say .

Remove elements

ArrayList There are many ways to delete elements , But there are three kinds of them ,

1、 Delete elements by subscript

2、 Delete… By element , This will delete ArrayList The first element in that matches the specified element to be removed

3、 Clear array elements

Although the former two functions are different , But the final call to the code is similar , They all refer to this code to solve the problem ：

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

The logic of this code is to copy all the elements after the specified element and move it forward one position , And then the last element is set to null, It’s very similar to some method logic in the insert , All calls System.arraycopy To do array operations , So , The efficiency of deleting elements is not high .

The third type of deletion method is to call clear ,

public void clear() {
modCount++;
// clear to let GC do its work
for (int i = 0; i < size; i++)
elementData[i] = null;
size = 0;
}

Set each element of the array to null, And put size Set as 0, It’s that simple .

Why “transient” Decorate array variables

Last question , Said before the ArrayList Can be serialized , But its array variable is transient modification , Why is that ？ according to Cangjie in May The explanation of this article is ：

serialize ArrayList When ,ArrayList Inside elementData It may not be full , For example elementData Yes 10 Size , But I used only one of them 3 individual , So is it necessary to serialize the whole elementData Well ？ Obviously, there is no need to , therefore ArrayList Rewritten in writeObject Method ：

private void writeObject(java.io.ObjectOutputStream s)
throws java.io.IOException{
// Write out element count, and any hidden stuff
int expectedModCount = modCount;
s.defaultWriteObject();
// Write out size as capacity for behavioural compatibility with clone()
s.writeInt(size);
// Write out all elements in the proper order.
for (int i=0; i<size; i++) {
s.writeObject(elementData[i]);
}
if (modCount != expectedModCount) {
throw new ConcurrentModificationException();
}
}

Call this method every time you serialize , First call defaultWriteObject() Method serialization ArrayList Middle Africa transient Elements ,elementData Don’t deserialize it , Then traverse elementData, Serialize only those elements that have , such ：

1、 Speed up serialization

2、 Reduces the size of the serialized file

Have to say , The designers are still very well intentioned .

summary

ArrayList This is the source code analysis of , Because there are only arrays at the bottom , So the logic of the source code is relatively simple , Compared with HashMap It’s much easier to learn like this (HashMap Looking back on the source code is really painful ?) , Let’s summarize some of its knowledge points ：

1、ArrayList The insert and delete operations are slow , Because it involves copying and moving the entire array .

2、 Because it’s an array , Support random access , So the speed of query and modification is faster

3、ArrayList There is no synchronization in the method of , therefore ArrayList It’s not thread safe , In general, you can call Collections.synchronizedList To pack .

Thank you for your article ：

https://www.cnblogs.com/xrq730/p/4989451.html