Java collection source code parsing series:
- Unpacking decoding Java collection source code overview
- Decoding Java Collection source code Collection of three systems
- Iterator for decoding Java collection source code
- Unpacking Java collection source code ArrayList
- Unpack the LinkedList of Java collection source code
- Decode HashMap of Java collection source code
- Decode Java collection source code Hashtable
- Unlink decode Java collection source code LinkedHashMap
- Decode Java collection source code PriorityQueue
- ArrayDeque decoding Java collection source code
ArrayList features
- Data structure: Object[], can be dynamically expanded (new array)
- Allow elements to be Null.
- Not thread-safe. You can use the Collections. SynchronizedList packing list for thread safety.
- Support RandomAccess, identified by element index: RandomAccess interface (no method, just identification).
- Collections.binarysearch () determines whether RandomAccess is implemented for the incoming interface.
- The time complexity of inserting and deleting elements is influenced by the location of the elements.
The source code
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess.Cloneable.java.io.Serializable
{
/** * Default capacity */
private static final int DEFAULT_CAPACITY = 10;
/** * the internal structure of an empty collection, avoiding the repeated creation of an empty array */
private static final Object[] EMPTY_ELEMENTDATA = {};
/** * An initial empty array of default capacity (no argument constructor). The next time you expand the array, if the array is of this value, you will expand it to at least the default size. Note: At least, if the specified capacity is 5, the default capacity will still be 10. * If expansion is not specified, the default value is 10. * /
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
/** * The array buffer that stores the elements of the ArrayList. * The capacity of ArrayList is the length of this array buffer. * Any empty ArrayList with elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA will be expanded to DEFAULT_CAPACITY when the first element is added. * /
transient Object[] elementData; // non-private to simplify nested class access
/** * The number of elements actually added */
private int size;
public ArrayList(int initialCapacity) {
if (initialCapacity > 0) {
this.elementData = new Object[initialCapacity];
} else if (initialCapacity == 0) {
// If there is no capacity, set to an empty array.
// Note that this value is not limited by the default capacity
this.elementData = EMPTY_ELEMENTDATA;
} else {
throw new IllegalArgumentException("Illegal Capacity: "+ initialCapacity); }}public ArrayList(a) {
// Only when an element is added will a full array be opened
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
public ArrayList(Collection<? extends E> c) {
elementData = c.toArray();
if((size = elementData.length) ! =0) {
// defend against c.toArray (incorrectly) not returning Object[]
// (see e.g. https://bugs.openjdk.java.net/browse/JDK-6260652)
// If elementData is not Object (c. toarray may return an array that is not Object)
if(elementData.getClass() ! = Object[].class) elementData = Arrays.copyOf(elementData, size, Object[].class); }else {
// replace with empty array.
If the original collection is empty, then the capacity is 0
this.elementData = EMPTY_ELEMENTDATA; }}/** * Adjusts the array length to the actual number of elements */
public void trimToSize(a) {
modCount++;
if (size < elementData.length) {
elementData = (size == 0)? EMPTY_ELEMENTDATA : Arrays.copyOf(elementData, size); }}/** * Element search, element save, and element index are dependent on indexOfRange and lastIndexOfRange. * The former is forward, forward and back; The latter goes backwards, from back to front. Start = 0, end = size * /
int indexOfRange(Object o, int start, int end) {
Object[] es = elementData;
if (o == null) {
for (int i = start; i < end; i++) {
if (es[i] == null) {
returni; }}}else {
for (int i = start; i < end; i++) {
if (o.equals(es[i])) {
returni; }}}return -1;
}
int lastIndexOfRange(Object o, int start, int end) {
Object[] es = elementData;
if (o == null) {
for (int i = end - 1; i >= start; i--) {
if (es[i] == null) {
returni; }}}else {
for (int i = end - 1; i >= start; i--) {
if (o.equals(es[i])) {
returni; }}}return -1;
}
public int lastIndexOf(Object o) {
return lastIndexOfRange(o, 0, size);
}
public <T> T[] toArray(T[] a) {
if (a.length < size)
// If the array is not large enough, create a new one based on the type
return (T[]) Arrays.copyOf(elementData, size, a.getClass());
System.arraycopy(elementData, 0, a, 0, size);
if (a.length > size)
// If the length is too long, the position immediately following the last element is set to empty so that the caller can determine how many elements there are.
a[size] = null;
return a;
} return oldValue;
/** * This method is pulled out so that the amount of bytecode added is small enough to ensure that C1 compile-optimized loops are inlined */
private void add(E e, Object[] elementData, int s) {
if (s == elementData.length)
// Note that there is no space available to expand
// Indicates that the array itself does not reserve space.
// ps: If you insert many elements in a batch, you can manually expand the space reserved :ensureCapacity
elementData = grow();
elementData[s] = e;
size = s + 1;
}
public boolean add(E e) {
modCount++;
add(e, elementData, size);
return true;
}
public void add(int index, E element) {
rangeCheckForAdd(index);
modCount++;
final int s;
Object[] elementData;
if ((s = size) == (elementData = this.elementData).length)
// Same as above
elementData = grow();
System.arraycopy(elementData, index,
elementData, index + 1,
s - index);
elementData[index] = element;
size = s + 1;
}
public E remove(int index) {
Objects.checkIndex(index, size);
final Object[] es = elementData;
@SuppressWarnings("unchecked") E oldValue = (E) es[index];
// The actual remove action
fastRemove(es, index);
return oldValue;
}
/** * If the collection type is inconsistent, use the iterator * to compare the number of elements to be consistent, the order of elements to be consistent, and between elements to be consistent */
boolean equalsRange(List<? > other,int from, int to) {
final Object[] es = elementData;
if (to > es.length) {
throw new ConcurrentModificationException();
}
var oit = other.iterator();
for (; from < to; from++) {
if(! oit.hasNext() || ! Objects.equals(es[from], oit.next())) {return false; }}return! oit.hasNext(); }/** * the same type, you can use arrays to quickly compare */
private boolean equalsArrayList(ArrayList
other) {
final int otherModCount = other.modCount;
final int s = size;
boolean equal;
if (equal = (s == other.size)) {
final Object[] otherEs = other.elementData;
final Object[] es = elementData;
if (s > es.length || s > otherEs.length) {
throw new ConcurrentModificationException();
}
for (int i = 0; i < s; i++) {
if(! Objects.equals(es[i], otherEs[i])) { equal =false;
break;
}
}
}
other.checkForComodification(otherModCount);
return equal;
}
int hashCodeRange(int from, int to) {
final Object[] es = elementData;
if (to > es.length) {
throw new ConcurrentModificationException();
}
int hashCode = 1;
for (int i = from; i < to; i++) {
Object e = es[i];
// Calculate the hashcode of all elements to reduce collisions
hashCode = 31 * hashCode + (e == null ? 0 : e.hashCode());
}
return hashCode;
}
public boolean remove(Object o) {
final Object[] es = elementData;
final int size = this.size;
int i = 0;
// From front to back, delete the first one found
found: {
if (o == null) {
for (; i < size; i++)
if (es[i] == null)
break found;
} else {
for (; i < size; i++)
if (o.equals(es[i]))
break found;
}
return false;
}
fastRemove(es, i);
return true;
}
private void fastRemove(Object[] es, int i) {
modCount++;
final int newSize;
if ((newSize = size - 1) > i)
// change I +1 ~ size to I ~ size-1
// Set size to null
System.arraycopy(es, i + 1, es, i, newSize - i);
es[size = newSize] = null;
}
public void clear(a) {
modCount++;
final Object[] es = elementData;
for (int to = size, i = size = 0; i < to; i++)
es[i] = null;
}
public boolean addAll(Collection<? extends E> c) {
Object[] a = c.toArray();
modCount++;
int numNew = a.length;
if (numNew == 0)
return false;
Object[] elementData;
final int s;
// If the length of c is greater than the remaining space, the new capacity to be expanded is the sum of the two sizes
if (numNew > (elementData = this.elementData).length - (s = size))
elementData = grow(s + numNew);
System.arraycopy(a, 0, elementData, s, numNew);
size = s + numNew;
return true;
}
public boolean addAll(int index, Collection<? extends E> c) {
rangeCheckForAdd(index);
Object[] a = c.toArray();
modCount++;
int numNew = a.length;
if (numNew == 0)
return false;
Object[] elementData;
final int s;
if (numNew > (elementData = this.elementData).length - (s = size))
elementData = grow(s + numNew);
int numMoved = s - index;
if (numMoved > 0)
System.arraycopy(elementData, index,
elementData, index + numNew,
numMoved);
System.arraycopy(a, 0, elementData, index, numNew);
size = s + numNew;
return true;
}
protected void removeRange(int fromIndex, int toIndex) {
if (fromIndex > toIndex) {
throw new IndexOutOfBoundsException(
outOfBoundsMsg(fromIndex, toIndex));
}
modCount++;
shiftTailOverGap(elementData, fromIndex, toIndex);
}
/** Erases the gap from lo to hi, by sliding down following elements. */
private void shiftTailOverGap(Object[] es, int lo, int hi) {
// Place the following elements forward and null the space left behind
System.arraycopy(es, hi, es, lo, size - hi);
for (int to = size, i = (size -= hi - lo); i < to; i++)
es[i] = null;
}
boolean batchRemove(Collection<? > c,boolean complement,
final int from, final int end) {
Objects.requireNonNull(c);
final Object[] es = elementData;
int r;
// Optimize for initial run of survivors
for (r = from;; r++) {
if (r == end)
return false;
// Skip the prefix sequence for invalid conditions
if(c.contains(es[r]) ! = complement)break;
}
int w = r++;
try {
for (Object e; r < end; r++)
if (c.contains(e = es[r]) == complement)
es[w++] = e;
/ / array:... w........ r
} catch (Throwable ex) {
// Preserve behavioral compatibility with AbstractCollection,
// even if c.contains() throws.
// The rest of the unjudged elements (after r) are not processed, and are placed after w.
/ / array:... w........ r..... s
System.arraycopy(es, r, es, w, end - r);
/ / array:... r..... s.. r..... s
w += end - r;
throw ex;
} finally {
modCount += end - w;
shiftTailOverGap(es, w, end);
// Normal branch :............ w
// Exception branch :............ r..... s
}
return true; }}Copy the codecapacity
The default capacity is 10; The default capacity expansion is 1.5 times
1.8 and later, the default construct is a singleton empty array that is expanded only on the first addition. It’s lazy loading
Note: 1.7 is hungry,
Construct to build an array of default capacities.
The comparison of the two values in the figure is actually done by subtraction in the code to avoid the impact of an Integer overflow.
/** * Default capacity */
private static final int DEFAULT_CAPACITY = 10;
/** * the internal structure of an empty collection, avoiding the repeated creation of an empty array */
private static final Object[] EMPTY_ELEMENTDATA = {};
/** * An initial empty array of default capacity (no argument constructor). The next time you expand the array, if the array is of this value, you will expand it to at least the default size. Note: At least, if the specified capacity is 5, the default capacity will still be 10. * If expansion is not specified, the default value is 10. * /
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
/** * The number of elements actually added */
private int size;
public ArrayList(int initialCapacity) {
if (initialCapacity > 0) {
this.elementData = new Object[initialCapacity];
} else if (initialCapacity == 0) {
// If there is no capacity, set to an empty array.
// Note that this value is not limited by the default capacity
this.elementData = EMPTY_ELEMENTDATA;
} else {
throw new IllegalArgumentException("Illegal Capacity: "+ initialCapacity); }}public ArrayList(a) {
// Only when an element is added will a full array be opened
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
public ArrayList(Collection<? extends E> c) {
elementData = c.toArray();
if((size = elementData.length) ! =0) {
// defend against c.toArray (incorrectly) not returning Object[]
// (see e.g. https://bugs.openjdk.java.net/browse/JDK-6260652)
// If elementData is not Object (c. toarray may return an array that is not Object)
if(elementData.getClass() ! = Object[].class) elementData = Arrays.copyOf(elementData, size, Object[].class); }else {
// replace with empty array.
If the original collection is empty, then the capacity is 0
this.elementData = EMPTY_ELEMENTDATA; }}/** * External capacity expansion method * When a known number of elements are added in batches, this method can be used to expand capacity in advance and at a time */ To avoid multiple capacity expansion time loss */
public void ensureCapacity(int minCapacity) {
// In both cases, the specified capacity does not need to be expanded
// 1. The array capacity is sufficient
// 2. Under lazy loading and the specified capacity is smaller than the default capacity. Since the default capacity is lazy to load, it can be thought of as' an array of default capacities already opened '.
if (minCapacity > elementData.length
&& !(elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA
&& minCapacity <= DEFAULT_CAPACITY)) {
modCount++;
grow(minCapacity);
}
}
/** * same as AbstractCollection */
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
/** * At least meets the requirements for minCapacity expansion, suitable for batch addition * but still subject to the default rules. Such as 1.5x capacity expansion, default capacity, maximum capacity, etc. */
private Object[] grow(int minCapacity) {
return elementData = Arrays.copyOf(elementData,
newCapacity(minCapacity));
}
/** * applies to add, at least for capacity + 1. */
private Object[] grow() {
return grow(size + 1);
}
/** * returns a capacity that is at least equal to the given minimum capacity. If enough, return a 50% increase in the current capacity. * No capacity greater than MAX_ARRAY_SIZE is returned unless the given minimum capacity is greater than MAX_ARRAY_SIZE */
private int newCapacity(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
// The new capacity defaults to 1.5 times the original capacity
int newCapacity = oldCapacity + (oldCapacity >> 1);
if (newCapacity - minCapacity <= 0) {
// Since it is lazy loading, we need to determine the initial condition
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
// Under lazy loading, the capacity must be greater than or equal to the default capacity
return Math.max(DEFAULT_CAPACITY, minCapacity);
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
// By default, the new capacity does not meet the specified capacity
return minCapacity;
}
return (newCapacity - MAX_ARRAY_SIZE <= 0)? newCapacity1.5 Capacity overflow may occur. Determine the capacity overflow based on minCapacity
: hugeCapacity(minCapacity);
}
/** * No capacity greater than MAX_ARRAY_SIZE is returned unless the given minimum capacity is greater than MAX_ARRAY_SIZE */
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