preface
Welcome to our GitHub repository Star: github.com/bin39232820… The best time to plant a tree was ten years ago, followed by now
omg
The foundation of the previous 2, we still have a good study, the following is the link
🔥 Introduction to the most complete Collection of Java containers in history 🔥 Basic data structures of the most complete collection of Java containers in history (hand-torn list)
Wanted to direct will List the parent class of all such as, but afraid of too long, I put the most commonly used in the development of our true ArrayList separate speaking, behind two do a (by the way, if it is based is not recommended to zero, have experience in half a year follow me put these together again, for your help is very big)
First, ArrayList
concept
Concept: An ArrayList is a dynamic array whose capacity can grow dynamically. But it’s not like an array, and we’ll look at the comparison below. It inherits AbstractList and implements List, RandomAccess, Cloneable, java.io.Serializable.
The RandomAccess interface, when implemented by List, provides List with RandomAccess, that is, the ability to get element objects by subscript.
With Cloneable implemented, java.io.Serializable means it can be cloned and serialized.
The main thing is to look at the part where I circle
The data structure of ArrayList
When analyzing a class, data structure is often the soul of it. To understand the underlying data structure is to understand the implementation of the class, and the specific implementation details will be analyzed in detail.
The data structure of ArrayList is:
ArrayList source code analysis
Inheritance structure and hierarchy
Let’s look at the inheritance structure of ArrayList:
- ArrayList extends AbstractList
- AbstractList extends AbstractCollection
Copy the codeAll classes inherit from Object, so ArrayList’s inheritance structure looks like the one shown above
Ask why AbstractList should be inherited first and AbstractList should be implemented first. Instead of having ArrayList implement List directly?
This is the idea that an interface is full of abstract methods, and an abstract class can have abstract methods and concrete implementation methods. It’s this idea that AbstractList can be used to implement some general methods in an interface, and concrete classes like ArrayList inherit this class. Get some common methods, and then in their own implementation of some unique methods, so that the code is more concise, on the inheritance structure of the bottom class of the common method are extracted, first implemented together, reduce repeated code. So when you see a class with an abstract class on top of it, that’s what it does
RandomAccess this interface
I click into the source code to find it is an empty interface, why is an empty interface
RandomAccess interface is a Marker interface
The ArrayList collection implements this interface to support fast random access
public static <T>
int binarySearch(List<? extends Comparable<? super T>> list, T key) {
if (list instanceof RandomAccess || list.size()<BINARYSEARCH_THRESHOLD)
return Collections.indexedBinarySearch(list, key);
else
return Collections.iteratorBinarySearch(list, key);
}
Copy the codeLooking at the source code, we can see that lists that implement the RandomAccess interface are iterated through using a generic for loop, while those that don’t implement the interface use iterators.
Arraylists are faster for iterators than for iterators, linkedLists are faster for iterators than for iterators, so when we’re working on a project, we should take into account that different subclasses of lists can iterate differently to improve performance! How to determine whether the subclass of List received is ArrayList or LinkedList? Then you need to use instanceof to determine if the List subclass implements RandomAccess!
Conclusion: The RandomAccess interface is a skeleton that can be used to better determine whether a collection is an ArrayList or a LinkedList, so that it can better choose a better traversal method and improve performance
Properties in the ArrayList class
public class ArrayList<E> extends AbstractList<E> implements List<E>, RandomAccess, Cloneable, Java.io.Serializable {// Version number 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 = {}; [] elementData; [] elementData; [] elementData; // Actual element size, default is 0 private int size; Private static final Int MAX_ARRAY_SIZE = integer. MAX_VALUE - 8; private static final int MAX_ARRAY_SIZE = integer. MAX_VALUE - 8; }Copy the codeA constructor
No arguments structure
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
Copy the codeThe size of the ArrayList is empty, but the length of elementData is 1. The first time you add it, the capacity becomes the initial capacity size 10 (default no-parameter construction is 10)
Int parameter construction
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 codeIt’s a little bit easier to check if it’s greater than 0, and if it’s greater than 0 it creates an array of the size that’s passed in, and if it’s 0 it’s empty
Collection parameter constructor
public ArrayList(Collection<? Extends E> c) {extends E> c) {// Specifies the list of elements of the collection in the order they are returned by the iterator of the collection. Copy the elements of the collection into elementData. 2. Update the size value. elementData = c.toArray(); if ((size = elementData.length) ! = 0) { // c.toArray might (incorrectly) not return Object[] (see 6260652) if (elementData.getClass() ! = Object[].class) elementData = Arrays.copyOf(elementData, size, Object[].class); } else { // replace with empty array. this.elementData = EMPTY_ELEMENTDATA; }}Copy the codePut the elements of the collection back into the new collection, and then update the actual size
The specific methods
The add method
/** * Appends the specified element to the end of this list. * * @param e element to be appended to this list * @return <tt>true</tt> (as specified by {@link Collection#add}) */ public Boolean add(E E) { Enrecapacityinternal (size + 1) later; // Increments modCount!! // add elements to the end of the array elementData[size++] = e; return true; }Copy the codeThe first step is to expand and the second step is to add an element to the tail and we’ll go down
EnsureCapacityInternal (XXX); Method for determining internal capacity
Private void ensureCapacityInternal(int minCapacity) {if (elementData == EMPTY_ELEMENTDATA) { Check whether the initialized elementData array is empty, i.e. has no length // because if it is empty, minCapacity=size+1; So we changed minCapacity to 10, which is the default size, but we haven't really initialized the size of elementData yet. minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity); EnsureExplicitCapacity (minCapacity); }Copy the codeEnsureExplicitCapacity (XXX);
private void ensureExplicitCapacity(int minCapacity) { modCount++; // overflow-conscious code //minCapacity If minCapacity is larger than the actual length of elementData, then the length of elementData array is insufficient, so increase the length of elementData. MinCapacity =size+1 when elementData is initialized as an empty array; minCapacity=size+1 when elementData is initialized as an empty array. So minCapacity=1. The previous method (ensureCapacityInternal) would have determined that the array was empty and given minCapacity=10. So far, we have not changed the size of elementData. MinCapacity =size+1; elementData is not an empty array. MinCapacity represents the actual amount of data added to elementData. Use it to determine whether the length of elementData is sufficient. If the length is insufficient, you must expand the capacity or the added element will overflow. */ if (minCapacity -elementdata.length > 0) //arrayList can automatically expand the size of the key method grow(minCapacity); }Copy the codegrow(xxx); The method at the heart of arrayList is the real secret to expanding the size of arrays.
private void grow(int minCapacity) { // overflow-conscious code int oldCapacity = elementData.length; // add the elementData size to oldCapacity int newCapacity = oldCapacity + (oldCapacity >> 1); If (newCapacity -mincapacity < 0)// oldCapacity=0 if (newCapacity -mincapacity < 0) NewCapacity =0, so this is true, in this case the actual size of the initialization elementData is 10. The work ahead is all preparatory work. newCapacity = minCapacity; If (newCapacity -max_array_size > 0)// If newCapacity exceeds the maximum capacity limit, call hugeCapacity, NewCapacity = hugeCapacity(minCapacity); // minCapacity is usually close to size, so this is a win: elementData = Arrays.copyOf(elementData, newCapacity); }Copy the codehugeCapacity();
// This is the method used above, very simple, is to assign the maximum value. private static int hugeCapacity(int minCapacity) { if (minCapacity < 0) // overflow throw new OutOfMemoryError(); // If minCapacity is greater than MAX_ARRAY_SIZE, integer. MAX_VALUE is returned; otherwise, MAX_ARRAY_SIZE is returned. Because maxCapacity is three times of minCapacity, the expansion may be too large, so we can use minCapacity to judge. // integer. MAX_VALUE:2147483647 MAX_ARRAY_SIZE: 2147483639 It still exceeds this limit and it's going to overflow. Arraylist provides two layers of protection. return (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE; }Copy the codeSummarize the expansion process
- 1. Determine whether the capacity needs to be expanded. If yes, calculate the minimum capacity to be expanded
- 2. If capacity expansion is required, run grow(int minCapacity). MinCapacity is the minimum required capacity
- 3. Capacity expansion for the first time is 1.5 times the original capacity
- 4 If the capacity is still smaller than minCapacity after the first expansion, expand the capacity to minCapacity
- 5. Finally, if minCapacity is greater than the maximum capacity, expand the capacity to the maximum capacity
The add (int, E) method
Public void add(int index, E element) {// Insert the array position check rangeCheckForAdd(index); EnsureCapacityInternal (size + 1); // Increments modCount!! System.arraycopy(elementData, index, elementData, index + 1, size - index); ElementData [index] = element; // insert the element size++ at the desired position; // The array must be inserted between 0 and the last element, otherwise an error is reported // Because the array is contiguous space, There is no disconnect the private void rangeCheckForAdd (int index) {if (index > size | | index < 0) throw new IndexOutOfBoundsException(outOfBoundsMsg(index)); }Copy the codeAnd that’s not too hard to do because we already implemented arrays
The get method
Public E get(int index) {// Check rangeCheck(index); // Returns result data if it passes the check, otherwise throws an exception. return elementData(index); } // The code for the out-of-bounds check is simple, Private void rangeCheck(int index) {if (index >= size) throw new IndexOutOfBoundsException(outOfBoundsMsg(index)); } @SuppressWarnings("unchecked") E elementData(int index) { return (E) elementData[index]; }Copy the codeCheck the array out of bounds, and then you just go to the array and get the data and return it
set(int index, E element)
Public E set(int index, E element) {// check rangeCheck(index); E oldValue = elementData(index); elementData[index] = element; return oldValue; }Copy the codeThis is the element that replaces the specified position
Remove (int) : Removes an element from a specified position
Public E remove(int index) {// Check rangeCheck(index); modCount++; E oldValue = elementData(index); Int numMoved = size-index - 1; int numMoved = size-index - 1; If (numMoved > 0) Add (int, E) System. Arraycopy (elementData, index+1, elementData, index, numMoved); ElementData [--size] = null; elementData[--size] = null; Clear to let GC do its work return oldValue; }Copy the coderemove(Object o)
Public Boolean remove(Object o) {// If (o == null) {for (int index = 0; index < size; Index ++) if (elementData[index] == null) {// Delete fastRemove(index); return true; For (int index = 0; int index = 0; int index = 0; index < size; Index ++) if (o.quals (elementData[index])) {// Delete fastRemove(index); return true; } } return false; } private void fastRemove(int index) { modCount++; Int numMoved = size-index - 1; int numMoved = size-index - 1; Arraycopy (elementData, index+1, elementData, index, numMoved); // Decrement the element size by 1 and set the last one to null. elementData[--size] = null; // clear to let GC do its work }Copy the codeconclusion
Pros and cons of ArrayList
- The underlying implementation of ArrayList is an array, a random-access mode, and it implements the RandomAccess interface, so lookups, or get, are very fast
- Arraylists are very convenient for adding elements sequentially, just adding one element to the array
- When deleting an element, element replication is involved, and if there are many elements to copy, it can be costly in performance
- When inserting elements, element copying is involved, and if there are many elements to copy, it can be performance costly
Why is the elementData of an ArrayList decorated with transient
- Note: ArrayList implements the Serializable interface, which means that ArrayList can be serialized. Using transient to describe elementData means I don’t want the elementData array to be serialized
- When serializing an ArrayList, the elementData in the ArrayList may not be full. For example, elementData is 10 in size, but I only use three of them. Is it necessary to serialize the entire elementData? This is obviously not necessary, so the writeObject method is overridden in ArrayList.
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();
}
}
Copy the code- Advantages: This method not only improves the serialization efficiency, but also reduces meaningless serialization. It also reduces the serialized file size.
Release notes
- The source code here is JDK8 version, different versions may vary, but the basic principle is the same.
At the end
ArrayList so much, all he could to the blog, look for the source code, I appreciate this source code is not very difficult, it is based on array because blogger is also a development of the new I am also learning to write I have a goal is a week Two to three articles Hope to be able to insist on a year Hope to your bosses more ideas, let me learn more, Progress together.
Daily for praise
All right, everybody, that’s all for this article. All the people here are talented.
Creation is not easy, your support and recognition, is the biggest motivation for my creation, we will see in the next article
Six pulse excalibur | article “original” if there are any errors in this blog, please give criticisms, be obliged!