This is the 21st day of my participation in the August Text Challenge.More challenges in August
1, an overview of the
An ArrayList is a List implemented as an array. Compared with an array, it has the ability to expand dynamically, so it can also be called a dynamic array.
1.1. When to use containers instead of arrays?
And to explain that, you have to figure out why there are containers at all. What are the limitations of using a good array?
I just want to up these two points, one of the main is the second point, container encapsulates many common functions, convenient developers call, improve the efficiency of development, so for us, the container of the underlying implementation is a very good learning materials, and write the underlying code, must be the quality of their code with high requirements.
- Containers can dynamically expand by themselves. The size of the array needs to be declared at creation time. After all, you need to tell the JVM how much contiguous storage space you want. You declare how much do you want, if you know how much you use itself is also good, if you don’t know themselves specific want how, first sound clear length of 100 (after all can’t because they don’t know how much you want again afraid bother to apply for it again, directly with the JVM to 10000, you want to burn is particularly waste), used with the not enough, You also need to apply for it again, which is very troublesome, right? Why don’t we encapsulate these processing operations when the capacity is not enough? So that’s one of the capabilities of the container, dynamic expansion.
- Containers encapsulate functionality in a way that many good code implementations do, such as double-pointer tag deletion in batch deletion. Container capable of things, the use of array must be capable, but you want to write some code to realize these requirements, and if every time your hand can’t reuse in violation of the principle of DRY, so some people will be wrapped up the commonly used function, allow users to out of the box, don’t have to write their own, and almost no bug.
1.2. When to use arrays instead of containers?
If nothing else, switching to arrays may save some performance overhead, depending on the requirements of the system, if it is low-level code, or higher performance requirements; In the case of a business system, perhaps these performance costs are also acceptable.
- As for the container, the storage type is Object, but the basic type cannot be stored. For example, the number 2 stored in the container will perform an automatic packing, and the number 2 taken out will perform an automatic unpacking operation, which requires performance consumption. If you care about the high performance requirements of the program, you can give up the knife and use a simple array.
- The data size of the operation is known, and no additional advanced features are required. Arrays can be used directly.
2, the class diagram
The inheritance and implementation relationship of ArrayList is shown
Four interfaces are implemented
2.1, the List
The top-level List interface provides operations such as adding, deleting, modifying, iterating through arrays.
2.2, the Serializable
Serialization interface: supports serialization interface
Use for logo
2.3, RandomAccess:
Without implementing any of these methods, like a symbol, the container supports fast RandomAccess. See this blog post: RandomAccess for what?
Considering that different lists have different traversal efficiency, different traversal methods are used according to different types to improve traversal performance
2.4, Cloneable
Support cloning
3, attributes,
-
DEFAULT_CAPACITY, size, and length
- DEFAULT_CAPACITY: the capacity of the default array
- Size: The actual number of elements stored in the array
- Length: the actual length of the current array
/** * After implementing the Serializable interface, declare the serialization ID */ in the class
private static final long serialVersionUID = 8683452581122892189L;
/** * Default initialization array size */
private static final int DEFAULT_CAPACITY = 10;
/** * The underlying array shared by all empty collection objects, belonging to the class attribute */
private static final Object[] EMPTY_ELEMENTDATA = {};
/** * shared empty array */
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
/** * an array that actually stores elements. The transient modifier is used to serialize this field */
transient Object[] elementData; // Non-private to simplify inner class access
/** * The actual number of stored elements. This value is maintained in real time when elements are added and deleted
private int size;
/** * The maximum size of array to allocate. The maximum length of the array that can be allocated */
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
Copy the code4. Construction method
4.1, new ArrayList(int initialCapacity)
Set the initial capacity to create the collection
public ArrayList(int initialCapacity) {
if (initialCapacity > 0) {
// Use local, object-level variables
this.elementData = new Object[initialCapacity];
} else if (initialCapacity == 0) {
this.elementData = EMPTY_ELEMENTDATA;
} else {
// Throw exception examples of invalid parameters
throw new IllegalArgumentException("Illegal Capacity: "+ initialCapacity); }}Copy the code4.2, new ArrayList ()
When the constructor takes no arguments, the default empty array is assigned
Given the default array of length 10 when adding the first element, you can look at the source code implementation of add (E E) below
public ArrayList(a) {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
Copy the code4.3, new ArrayList (Collection <? extends E> c)
public ArrayList(Collection<? extends E> c) {
// Call the incoming parameter object implementation method, may be different from collection implementation method
elementData = c.toArray();
if((size = elementData.length) ! =0) {
// C. toarray might (incorrectly) not return Object[] (see 6260652). ElementData is Object[]
if(elementData.getClass() ! = Object[].class) elementData = Arrays.copyOf(elementData, size, Object[].class); }else {
// replace with empty array.
this.elementData = EMPTY_ELEMENTDATA; }}Copy the code5. Common API methods
5.1 Add elements & Capacity expansion mechanism
add(E e)
Add an element to the end of the array
-
Ensure that the container capacity is sufficient. If not, expand the capacity. (Enter size+1 as the minCapacity parameter to determine whether the capacity is sufficient.)
- Calculates the size of the array that can hold the element. (If the current array is empty, return the default length of 10 and the larger value of minCapacity; Otherwise return minCapacity.
- Make sure the array is large enough. (If the current array length is greater than minCapacity, it is sufficient to return directly; Otherwise, perform capacity expansion.) [Capacity expansion Operation Below]
-
Store the element at the size index in the array, incrementing size by 1.
-
Returns true to indicate a successful addition.
add(E e)
/** ** Adds a single element to the end of the array */
public boolean add(E e) {
// Ensure that the internal capacity does not run out of bounds when storing e elements
ensureCapacityInternal(size + 1); // Increments modCount!!
// Store the element in the size position, then increment the size by 1 (note that the array starts at 0,).
elementData[size++] = e;
return true;
}
/** * Ensure that the array has enough free space to store the next element **@paramMinCapacity Minimum capacity of the current collection object that can meet storage requirements */
private void ensureCapacityInternal(int minCapacity) {
// Ensure clear and unambiguous capacity
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
/** * Calculate the capacity */
private static int calculateCapacity(Object[] elementData, int minCapacity) {
// Check whether the array is empty. The array created with no arguments is empty by default, and an array of size 10 is assigned to it when the first element is added
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
return Math.max(DEFAULT_CAPACITY, minCapacity);
}
return minCapacity;
}
/** * Ensure a clear array capacity * If the capacity is insufficient, there will be a capacity expansion operation */
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// overflow-conscious code Performs expansion if the minimum capacity that meets the storage requirement is greater than the array length
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
Copy the codegrow()
- NewCapacity = oldCapacity + (oldCapacity >> 1)
- If the new capacity is smaller than the required capacity, the required capacity is used
- Copies the original element into a new array of the specified length newCapacity
/** * The expansion operation is implemented */
private void grow(int minCapacity) {
// overflow-conscious code: code that considers overflow
int oldCapacity = elementData.length;
// Expand by 1.5 times
int newCapacity = oldCapacity + (oldCapacity >> 1);
// If the new capacity is found to be smaller than the required capacity, the required capacity prevails
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
// If the new capacity exceeds the maximum capacity, use the maximum capacity
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
// minCapacity is usually close to size, so this is a win: array copy
elementData = Arrays.copyOf(elementData, newCapacity);
}
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 codeadd(int index, E element) & grow()
Adds a single element to the specified location
- Checks whether the specified subscript is out of bounds
- Make sure the array is large enough.
- Move the index position and subsequent elements one bit back (using copyOf in System)
- Store the target element at the index location
- Number of elements in the current array size+1
// Add a single element to the specified position in the array
public void add(int index, E element) {
// Check whether the specified corner markers are valid
rangeCheckForAdd(index);
ensureCapacityInternal(size + 1); // Increments modCount!!
// Batch copies the index and subsequent elements into the specified array
System.arraycopy(elementData, index, elementData, index + 1, size - index);
elementData[index] = element;
size++;
}
/** * A version of rangeCheck used by add and addAll. Check horn range */
private void rangeCheckForAdd(int index) {
// Where this method is called, ensure that it is added element by element
if (index > size || index < 0)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
Copy the codeaddAll(Collection<? extends E> c)
Add multiple elements starting at the end of the array
- Count the number of elements to add
- Make sure the array is large enough
- Starts copying elements from the target array into the source array
- The number of elements in the array increases
😂 : The method implementation here is not very good, why not the numNew judgment is equal to 0 up front? If 0, end the method directly.
public boolean addAll(Collection<? extends E> c) {
Object[] a = c.toArray();
int numNew = a.length;
// Make sure the array size meets the minimum storage capacity
ensureCapacityInternal(size + numNew); // Increments modCount
System.arraycopy(a, 0, elementData, size, numNew);
size += numNew;
returnnumNew ! =0;
}
Copy the codeaddAll(int index, Collection<? extends E> c)
Adds multiple elements starting at the specified location
This is basically the same as above, except that the elements in this array need to be moved first
/** * add multiple elements from the specified position */
public boolean addAll(int index, Collection<? extends E> c) {
rangeCheckForAdd(index);
Object[] a = c.toArray();
int numNew = a.length;
ensureCapacityInternal(size + numNew); // Increments modCount
// Count the number of elements that need to be moved, and prepare the position for the new element
int numMoved = size - index;
if (numMoved > 0)
System.arraycopy(elementData, index, elementData, index + numNew, numMoved);
System.arraycopy(a, 0, elementData, index, numNew);
size += numNew;
returnnumNew ! =0;
}
Copy the code5.2. Delete elements
remove(Object o)
Iterating over elements to determine whether they are equals and deleting them (involving an array copy)
/** * add multiple elements from the specified position */
public boolean remove(Object o) {
// Perform a different processing depending on whether o is null, which removes only the first element that matches the first (front-to-back) element
if (o == null) {
for (int index = 0; index < size; index++)
if (elementData[index] == null) {
// Fast delete, delete directly according to the subscript
fastRemove(index);
return true; }}else {
for (int index = 0; index < size; index++)
if (o.equals(elementData[index])) {
fastRemove(index);
return true; }}return false;
}
/** * delete from index; Private remove method that skips bounds checking and does not * return the value removed. */
private void fastRemove(int index) {
modCount++;
int numMoved = size - index - 1;
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index, numMoved);
// Set the trailing element to null for garbage collection
elementData[--size] = null; // clear to let GC do its work
}
Copy the coderemove(int index)
Subscription-based deletion involves an array copy process that ends with the last position element set to NULL.
/** * check index validity, delete logic and fast delete */
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;
}
Copy the coderemoveRange(int fromIndex, int toIndex)
Delete an element by index. Delete an element by index
/**
* Removes from this list all of the elements whose index is between
* {@code fromIndex}, inclusive, and {@codeToIndex}, exclusive. * contains fromIndex and does not contain toIndex */
protected void removeRange(int fromIndex, int toIndex) {
modCount++;
// Count the number of elements that need to be moved later
int numMoved = size - toIndex;
System.arraycopy(elementData, toIndex, elementData, fromIndex, numMoved);
// Set the rest of the array to null
// clear to let GC do its work
int newSize = size - (toIndex-fromIndex);
for (int i = newSize; i < size; i++) {
elementData[i] = null;
}
size = newSize;
}
Copy the coderemoveAll(Collection<? > c)
Deletes elements from the collection passed in
After checking that the element is not empty, we call the batch delete method. Here we pass in a Boolean value of false. Here complement indicates whether the element is used in the complement set
public boolean removeAll(Collection
c) {
Objects.requireNonNull(c);
return batchRemove(c, false);
}
Copy the codebatchRemove(Collection<? > c, boolean complement)
Deletes elements from the collection
This method is also used when calculating the complement between sets
Complement identifies whether the operation is performed as a complement. This is a nice identifier (makes code reusable)
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++)
// Double pointer assignment, iterating through elementData to determine if the element is in C, if it contains a skipped assignment, no assignment
if (c.contains(elementData[r]) == complement)
// Delete the element by skipping it without assigning it
elementData[w++] = elementData[r];
} finally {
// Preserve behavioral compatibility with AbstractCollection,
// even if c.contains() throws. Use finally to catch null pointer cases when determining whether to include
if(r ! = size) { System.arraycopy(elementData, r, elementData, w, size - r); w += size - r; }// Assign the elements starting with w to null, updating the array size
if(w ! = size) {// clear to let GC do its work
for (int i = w; i < size; i++)
elementData[i] = null;
modCount += size - w;
size = w;
modified = true; }}return modified;
}
Copy the coderetainAll(Collection<? > c)
Keep all the elements in set C
public boolean retainAll(Collection
c) {
Objects.requireNonNull(c);
return batchRemove(c, true);
}
Copy the code5.3 update elements
E set(int index, E element)
Sets the specified subscript position to the specified element
- Check if the subscript is out of bounds
- Fetch the old element at that location (returned later)
- Stores the specified element at that location
- Returns the old element
/** * Replaces the element at the specified position in this list with * the specified element. */
public E set(int index, E element) {
rangeCheck(index);
E oldValue = elementData(index);
elementData[index] = element;
return oldValue;
}
Copy the code5.4. Find elements
E get(int index)
Implement O (1) time complexity query according to the subscript
- Check if array subscripts are out of bounds
- Returns the element in the array at index position
/** * Returns the element at the specified position in this list. */
public E get(int index) {
// index validity check
rangeCheck(index);
return elementData(index);
}
Copy the codeindexOf(Object o)
Returns the Angle of the first element with o, or -1 if none exists.
public int indexOf(Object o) {
if (o == null) {
for (int i = 0; i < size; i++)
if (elementData[i]==null)
return i;
} else {
for (int i = 0; i < size; i++)
if (o.equals(elementData[i]))
return i;
}
return -1;
}
Copy the codelastIndexOf(Object o)
Returns the horn of the last element with o, or -1 if none exists.
public int lastIndexOf(Object o) {
if (o == null) {
for (int i = size-1; i >= 0; i--)
if (elementData[i]==null)
return i;
} else {
for (int i = size-1; i >= 0; i--)
if (o.equals(elementData[i]))
return i;
}
return -1;
}
Copy the code5.5, other
Object[] toArray()
/** * is converted to an array but of type Object */
public Object[] toArray() {
return Arrays.copyOf(elementData, size);
}
/** * Instead of converting to Object, we pass in an array type to receive the result */
public <T> T[] toArray(T[] a) {
// If the size of the incoming array is smaller than the number of elements in the current container, create an appropriate array to copy
if (a.length < size)
// Make a new array of a's runtime type, but my contents:
return (T[]) Arrays.copyOf(elementData, size, a.getClass());
System.arraycopy(elementData, 0, a, 0, size);
// If the array passed is longer than the source, set the size position element to null
if (a.length > size)
a[size] = null;
return a;
}
Copy the codeint hashCode()
Inherit hashCode method overridden from AbstractList
31* hashcode + (e==null? 0: e.h ashCode ())
public int hashCode(a) {
int hashCode = 1;
for (E e : this)
hashCode = 31*hashCode + (e==null ? 0 : e.hashCode());
return hashCode;
}
Copy the codeboolean equals(Object o)
Inherit hashCode method overridden from AbstractList
List determines whether two sets are equal
We can also refer to this implementation when manually overriding equals on our class
- Determine if it is the same object,
- Check whether they both belong to the list
- Construct two iterators to iterate through to determine whether they are equal
- Determines whether there is a next element in both iterators
public boolean equals(Object o) {
if (o == this)
return true;
if(! (oinstanceof List))
return false; ListIterator<E> e1 = listIterator(); ListIterator<? > e2 = ((List<? >) o).listIterator();while (e1.hasNext() && e2.hasNext()) {
E o1 = e1.next();
Object o2 = e2.next();
if(! (o1==null ? o2==null : o1.equals(o2)))
return false;
}
return! (e1.hasNext() || e2.hasNext()); }Copy the codeclear()
The traversal sets all elements to NULL
public void clear(a) {
modCount++;
// clear to let GC do its work
for (int i = 0; i < size; i++)
elementData[i] = null;
size = 0;
}
Copy the code