Matters needing attention

  1. ArrayList
  • ArrayList can add NULL, and multiple;
  • An ArrayList is implemented by arrays;
  • ArrayList is basically the same as Vector, except that ArrayList is thread-unsafe (efficient). In multithreaded situations, ArrrayList is not recommended.
  1. The Idea of the Debug setting
  2. Java -version 1.8.0 comes with _221

Underlying operating mechanism

  • An Array of elementData of type Object is maintained in ArrayList.

    transient Object[] elementData; // TRANSIENT indicates transient, indicating that the attribute will not be serialized
Copy the code

  • When creating an ArrayList object, the initial elementData capacity is 0 if a no-parameter constructor is used. If it is added for the first time, the capacity of elementData is expanded by 10. If it needs to be expanded again, the capacity of elementData is expanded by 1.5 times of the original capacity.

  • If a constructor of the specified size is used, the initial elementData capacity is the specified size. If you need to expand, expand elementData by 1.5.

Read the source code

Analysis creates and uses an ArrayList using the no-parameter constructor. The parameter constructor reads the source code process is similar, the difference is the first expansion!

Source program

@SuppressWarnings(value = "all")
public class ArrayListSource {
  public static void main(String[] args) {
    // Create an ArrayList using the no-argument constructor
    ArrayList list = new ArrayList();
    // Create an ArrayList using the parameter constructor
    // ArrayList list = new ArrayList(8);
    // Add 10 pieces of data to the collection
    for (int i = 1; i <= 10; i++) {
      list.add(i);
    }
    // Add 5 more pieces of data to the collection
    for (int i = 11; i <= 15; i++) {
      list.add(i);
    }
    list.add(100);
    list.add(200); }}Copy the code

The analysis process

1. Create an empty array.

List.add (E E)

  • Ensure the internal capacity and determine whether to expand the capacityensureCapacityInternal
  • Then perform the assignment

Debug F7 into source code for the first time added! If the data is of a basic type, there is a boxing operation before stuffing.

3. Determine the minimum capacity (minCapacity) and set it to 10 for the first time

4. Determine whether the system needs to be expanded

  • ModCount++ records the number of times the collection was modified
  • If elementData is not large enough, grow() is called to expand it

5. Expand the capacity. Use the expansion mechanism to determine the capacity to be expanded

  • For the first time newCapacity = 10
  • The second and subsequent expansion is 1.5 times the original capacity of the array
  • Expansion usesArrays.copyOf

6. Add data to the array

Grow () expansion function details

JDK 1.8.0_221 source code snippet

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);
}
Copy the code
  1. Elementdata. length is logged to oldCapacity with the first value of 0;
  2. newCapacity = oldCapacity + (oldCapacity >> 1); Expand the array by 1.5 times the current array capacity + move the current array size to the right by 1 bit (divided by 2).
  3. Because both oldCapacity and newCapacity are 0 for the first capacity expansionIf (newcapacity-mincapacity < 0) the condition is valid, the first expansion size is 10;
  4. The arrays.copyof () method can retain the original data for expansion;
  5. If the capacity exceeds2147483639The callhugeCapacityComputing capacity;