ArrayList It is the most commonly used collection in our development , But many people do not know its source code , Lead to interview , A slightly more in-depth question from the interviewer , There is no answer , Let's explore it today ArrayList Source code .
1. brief introduction
- ArrayList At the bottom is an array , Allow elements to be null, Dynamic capacity expansion
- size、isEmpty、get、set、add The time complexity of such methods is O (1)
- Non-thread safety , Concurrent modification , Will throw out ConcurrentModificationException
2. initialization
// Initial capacity
private static final int DEFAULT_CAPACITY = 10;
// An empty array
private static final Object[] EMPTY_ELEMENTDATA = {};
// Default empty array
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
// Array of storage elements
transient Object[] elementData;
// No parameter initialization , The default is an empty array
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
// Parameter initialization , Specified 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);
}
}
Bear in mind ： During parameterless initialization , The default is an empty array , Capacity size is not initialized , The capacity is initialized only when the element is added for the first time .
3. Additive elements
public boolean add(E e) {
// Make sure the array has enough capacity ,size It's the number of elements
ensureCapacityInternal(size + 1);
// Direct assignment
elementData[size++] = e;
return true;
}
// Make sure the array has enough capacity
private void ensureCapacityInternal(int minCapacity) {
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
// Calculate the minimum capacity required
private static int calculateCapacity(Object[] elementData, int minCapacity) {
// If the array equals an empty array , The minimum capacity is 10
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
return Math.max(DEFAULT_CAPACITY, minCapacity);
}
return minCapacity;
}
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// If the required minimum capacity is greater than the array length , Just expand
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
Take a look at the expansion logic ：
// Capacity expansion , Is to copy the old data into the new array
private void grow(int minCapacity) {
int oldCapacity = elementData.length;
// oldCapacity >> 1 It's a oldCapacity Divide 2, intend 1.5 Double expansion
int newCapacity = oldCapacity + (oldCapacity >> 1);
// If the capacity after expansion is less than the minimum capacity , The capacity after expansion is equal to the minimum capacity
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
// If the capacity after expansion is greater than Integer The maximum of , Just use Integer Maximum
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
// Expand and assign values to the original array
elementData = Arrays.copyOf(elementData, newCapacity);
}
You can see ：
- The expansion is based on the original capacity 1.5 Double expansion , It's not about doubling the capacity
- The maximum capacity is Integer The maximum of
- When adding elements , There is no element validation , It can be null
Take another look at the logic of array copying , It's all here Arrays Class ：
/**
* @param original Original array
* @param newLength New capacity size
*/
public static <T> T[] copyOf(T[] original, int newLength) {
return (T[]) copyOf(original, newLength, original.getClass());
}
public static <T,U> T[] copyOf(U[] original, int newLength, Class<? extends T[]> newType) {
// Create a new array , Capacity is the new capacity size
T[] copy = ((Object)newType == (Object)Object[].class)
? (T[]) new Object[newLength]
: (T[]) Array.newInstance(newType.getComponentType(), newLength);
// Copy the elements of the original array to the new array
System.arraycopy(original, 0, copy, 0,
Math.min(original.length, newLength));
return copy;
}
Finally called System Class , yes native Method ：
/**
* @param src Original array
* @param srcPos The starting position of the original array
* @param dest Target array
* @param destPos The starting position of the target array
* @param length Length copied
*/
public static native void arraycopy(Object src, int srcPos,
Object dest, int destPos,
int length);
4. Delete single element
public boolean remove(Object o) {
// Determine whether the element to be deleted is null
if (o == null) {
// Traversal array
for (int index = 0; index < size; index++)
// If it is equal to the element in the current position , Just delete the element in the current position
if (elementData[index] == null) {
fastRemove(index);
return true;
}
} else {
// Traversal array
for (int index = 0; index < size; index++)
// If it is equal to the element in the current position , Just delete the element in the current position
if (o.equals(elementData[index])) {
fastRemove(index);
return true;
}
}
return false;
}
// Delete elements at this location
private void fastRemove(int index) {
modCount++;
// Count the number of elements that need to be moved
int numMoved = size - index - 1;
if (numMoved > 0)
// from index+1 Position start copy , That is, the following elements move one position to the left as a whole
System.arraycopy(elementData, index+1, elementData, index, numMoved);
// The last element of the array is assigned null, Prevent memory leaks
elementData[--size] = null;
}
You can know , Remove elements , That's traversing the array , The loop compares whether it is equal to the target value . If equal , Just move the whole element behind this position to the left by one position , Then assign the value of the last element of the array to null.
5. Batch deletion
// Batch deletion ArrayList And collection c The elements that exist
public boolean removeAll(Collection<?> c) {
// Non empty verification
Objects.requireNonNull(c);
// Batch deletion
return batchRemove(c, false);
}
private boolean batchRemove(Collection<?> c, boolean complement){
final Object[] elementData = this.elementData;
int r = 0, w = 0;
boolean modified = false;
try {
for (; r < size; r++)
if (c.contains(elementData[r]) == complement)
// Move the elements that need to be preserved to the left
elementData[w++] = elementData[r];
} finally {
// When something goes wrong , It may not be equal
if (r != size) {
// 1： Maybe it's from above for An exception occurred in the loop
// 2： Other threads may have added elements
System.arraycopy(elementData, r,
elementData, w,
size - r);
w += size - r;
}
// Assign an element that does not need to be preserved to null
if (w != size) {
for (int i = w; i < size; i++)
elementData[i] = null;
modCount += size - w;
size = w;
modified = true;
}
}
return modified;
}
You can know , When deleting in batch , Only one copy of the array will be made , Than using for Circular single deletion is more efficient , So when deleting a batch of elements , As far as possible with removeAll() Method .
5. summary
This paper analyzes ArrayList The initialization 、put、add、remove、 Dynamic capacity expansion and other methods of the underlying source code , I'm sure you're interested in ArrayList With a deeper understanding , Let's learn the next chapter LinkedList Source code .
There are people who say ArrayList yes 2 Double expansion , I'll tear it with your hands today ArrayList More articles on source code
- Gouge your series —— Tear your hands ArrayList
Not much BB, Go straight to the code : public class MyArrayList { // Create an array object private Object[] elements; // Array length used private int siz ...
- Java - ArrayList Source code analysis
java Improve ( 21 )-----ArrayList One .ArrayList summary ArrayList It's the realization of List Dynamic array of interfaces , The so-called dynamic is that its size is variable . Implemented all optional list operations , And allow to include nul ...
- Java Generic underlying source code parsing -ArrayList,LinkedList,HashSet and HashMap
Statement : The following source code is based on JDK1.8_112 edition 1. ArrayList The source code parsing <1. The collection is still a reference to the object, not the object itself , And cannot place native data types , We need to use packages of native data types ...
- Java Xiaobai collection source code learning series ：ArrayList
ArrayList Source code learning This article is based on JDK1.8 edition , For the giants in the set ArrayList Do some source code learning , There will be a lot of references , Links to reference articles will be given at the end of the article , This article is used to consolidate the learning knowledge . ArrayList Of ...
- Java8 Collections framework ——ArrayList Source code analysis
java.util.ArrayList The following are the main points , from Java 8 set out : One .ArrayList Overview of the characteristics of Two .ArrayList Internal implementation : Let's start with internal properties and constructors 3、 ... and .ArrayLis ...
- Gather them together ArrayList（ contain JDK1.8 Source code analysis ）
One .ArrayList Data structure of ArrayList The underlying data structure is an array , The array element type is Object type , That is, all types of data can be stored . We are right. ArrayList Class ( Add, delete, change, check, etc ), Its bottom floor is ...
- JAVA Interview questions Handwriting ArrayList The implementation of the , Pass the written examination and be sure to ?
interviewer Q1: You can write a ArrayList The simple implementation of ? We all know ArrayList It's based on arrays , If you can achieve JDK Source code ArrayList in add().remove().get() Method , You know how to ...
- ( One )ArrayList Collection source code analysis
One .ArrayList Set characteristics of problem junction On ArrayList Is it allowed to be empty allow ArrayList Whether duplicate data is allowed allow ArrayList Is it orderly Orderly ArrayList Is it thread safe ...
- Source code analysis II (ArrayList And LinkedList The difference between )
One : Let's look at it first ArrayList Class architecture : public class ArrayList<E> extends AbstractList<E> implements Lis ...
- JDK12 Under the ArrayList Source code interpretation And Vector Comparison of
ArrayList Source code reading . // The test code is implemented as follows private static void arrayList() { ArrayList<String> list = new Array ...
Random recommendation
- stay java Project use AES256 CBC encryption
First of all, pay attention to , default JDK It is not supported 256 Bit encrypted , Need to Oracle Download the encryption enhancement file on the official website (Java Cryptography Extension (JCE) Unlimited Strength J ...
- HDU 4831 Scenic Popularity （ Duan tree ）
Scenic Popularity Problem Description Approaching the festival , The Dudu bears are planning to visit the park outdoors . The park contains many tourist attractions and rest areas , Because tourist attractions are very popular , Leading to scenic spots and rest areas ...
- In the data structure , Several tree structure representation methods （C Language implementation ）
//***************************************** // The various structural definitions of trees //***************************************** # ...
- Create and register custom HTTP modular
This walkthrough demonstrates customizing HTTP The basic function of the module . For each request , All need to be called HTTP Module in response to BeginRequest and EndRequest event . therefore , The module runs before and after processing the request . If ...
- HBase snapshot
CDH yes Cloudera Completely open source distributed Apache Hadoop And related projects ( Include Apache HBase).CDH The current version of (4.2) The one introduced HBase New features have recently been added to the trunk , Allows the user to enter... For the specified table ...
- php Delete files or folders
<?php function deleteDir($dir) { if (!$handle = @opendir($dir)) { return false; } while (false != ...
- Java Cut the picture
package com.test; import java.awt.image.BufferedImage; import java.io.File; import javax.imageio.Ima ...
- Reducing and Profiling GPU Memory Usage in Keras with TensorFlow Backend
keras Adaptive allocation of video memory & Clean up unused variables and release GPU memory Intro Are you running out of GPU memory when using keras or ten ...
- transfer function
After linear change , It is often desirable to make nonlinear changes , The commonly used nonlinear variation functions are Sigmoid,Tanh,ReLU. Will find , After these three functions change ,Tensor The dimension of does not change . tanh( Hyperbolic tangent function ):
- What’s a service mesh? And why do I need one?
https://buoyant.io/2017/04/25/whats-a-service-mesh-and-why-do-i-need-one/ Update 2018-02-06: Since t ...
