1. Introduction
ArrayList is a common data structure, but how much do you know about ArrayList? Might as well test yourself.
2.ArrayList Daily question (answers at bottom)
(1) What is the default size of jdk1.8ArrayList?
(2) How much can ArrayList be expanded?
(3) Is ArrayList thread safe? Why is that?
(4) Why use transient modifier for elementData in ArrayList?
(5) ArrayList list = new ArrayList(20); How many times does the list expand in?
If you can answer all of the above questions correctly, well, check the eyes, big tea ~
If you don’t get it right, don’t be discouraged. Let’s learn about ArrayList
3.ArrayList Underlying analysis (based on JDk1.8)
Interview building rockets, developing screws, actually most of us are in CRUD, ArrayList is no exception, let’s start from the CRUD of ArrayList
3.1 Member variables of ArrayList
// The default capacity
private static final int DEFAULT_CAPACITY = 10;
// An empty array instance
private static final Object[] EMPTY_ELEMENTDATA = {};
// An empty array instance of the default size.
Separate from the above example so that we know when the first element will be added
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
//Object, the underlying layer of ArrayList
transient Object[] elementData
/ / size
private int size;
Copy the code3.2 Constructor of ArrayList
Parameterless constructor, so here we see parameterless constructor, which is when we don’t give the size of an ArrayList, the ArrayList will be an empty array
// Here we see an empty array initialized
public ArrayList(a) {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
Copy the codeConstructor with initialization capacity
//1. If the initialized value is greater than 0, simply new an initialCapacity Object array
//2. If equal to 0, it is the first of the above member variables,EMPTY_ELEMENTDATA
< 0, IllegalArgumentException will be run
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 codeA constructor of type Collection
//1. Convert a Collection to an array
//2. If c.toarray () is not an Object array, use the array.copyof method to convert
//3. If the length of c.array () is equal to 0, use your own member variable
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 code3.3 ArrayList Add methods (divided into two types)
Added directly
(1) Check whether the array is empty, if it is empty, give the default value
(2) Determine whether capacity expansion is required
(3) Capacity expansion
(4) Add elements
// Whether to expand the capacity
// Add elements
public boolean add(E e) {
ensureCapacityInternal(size + 1);
elementData[size++] = e;
return true;
}
private void ensureCapacityInternal(int minCapacity) {
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
// If elementData is an empty array, minCapacity is 1
// The default size will be 10, similar to lazy loading, default is an empty array, when we
// The first time we add it, we give it a default size of 10,
private static int calculateCapacity(Object[] elementData, int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
return Math.max(DEFAULT_CAPACITY, minCapacity);
}
return minCapacity;
}
// Determine whether capacity expansion is required
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
// Real expansion code
// Old array capacity + old array capacity to the right =1.5 times
// Check whether the new capacity is smaller than the minimum required capacity. If yes, the new capacity is equal to the minimum required capacity
// If the new capacity is larger than MAX_ARRAY_SIZE, use hugeCapacity to compare the two
// arrays.copyof is used for copying
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
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:
elementData = Arrays.copyOf(elementData, newCapacity);
}
// Compare minCapacity with MAX_ARRAY_SIZE
// If minCapacity is large, use integer. MAX_VALUE as the size of the new array
// If MAX_ARRAY_SIZE is large, use MAX_ARRAY_SIZE as the size of the new array
//MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
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
3.4 Get method (two lines of code)
The first step is to determine whether the table below is out of bounds. The second step is to get the elements directly from the table below
public E get(int index) {
rangeCheck(index);
return elementData(index);
}
Copy the code3.5 Remove Method (Two methods)
Follow the subscript remove
(1) Determine whether the subscript is out of bounds. If it is, an exception will be thrown directly
(2) Query the element in the array
(3) Calculate the number of moves required
(4) If numMoved is greater than 0, all subsequent elements to be removed need to be moved to the left. If numMoved is the last element, no move is required
(5) Reduce the size of the original array by one and assign the value to null, which is beneficial to GC
(6) Return the old element
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;
}
/ / SRC: source array
//srcPos: moves from the srcPos position of the source array
//dest: destination array
//desPos: elements that start moving at srcPos of the source array. These elements start filling at desPos of the destination array
//length: Moves the source array length
public static native void arraycopy(Object src, int srcPos,
Object dest, int destPos,
int length);
Copy the codeDelete by the value of the element, which is easier to understand, first traverse, get the element subscript, and then use the above delete code to delete
3.6 ensureCapacity method
This method can use the Enrecapacity method before adding a large number of elements to reduce the number of deltas reassigned
public void ensureCapacity(int minCapacity) {
intminExpand = (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;
if(minCapacity > minExpand) { ensureExplicitCapacity(minCapacity); }}private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// overflow-conscious code
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
Copy the code3.7 writeObject and readObject
Why ArrayList defines these two methods for reading and writing streams, which brings us back to our fourth question,
Why use transient modifier for elementData in ArrayList?
Because ArrayList is implemented based on dynamic arrays, not all of the space is used. Therefore, a transient modifier is used to prevent automatic serialization. ArrayList therefore customizes serialization and deserialization, as seen in writeObject and readObject methods. It is important to note that when the writeObject and readObject methods are customized in an object, the JVM calls these two custom methods for serialization and deserialization.
Serialize an ArrayList through a stream
/** * Save the state of the ArrayList instance to a stream (that * is, serialize it). * * @serialData The length of the array backing the ArrayList * instance is emitted (int), followed by all of its elements * (each an Object) in the proper order. */
Deserialize an ArrayList from a stream
/** * Reconstitute the ArrayList instance from a stream (that is, * deserialize it). */
4. Answer
Jdk1.8 gives an empty array 0 by default if it does not give the initial value capacity. When it is added for the first time, it recalibrates the size and gives 10 capacity
NewCapacity = oldCapacity + (oldCapacity >> 1)
ArrayList is not thread-safe, elementData[size++] = e when we add or delete; elementData[–size] = e; These two operations, not atomic operations, are two steps
3.7 We have analyzed it
The default ArrayList is 10, so if you want to add 20 elements to the list you must expand it once (newCapacity is 1.5 times the original size, but it is smaller than minCapacity). If newCapacity = minCapacity (newCapacity = minCapacity), you need to expand your space only once. If newCapacity = minCapacity, you need to expand your space once.
5. Ask questions
Why add delete operation have modCount++, what effect, believe smart you already know the answer, welcome to leave a message in the comment area
About 6.
Programmer Little R: a non-professional coffee maker, using the public account “Programmer Little R”, reply to “666” to get the latest 1000 pages of questions