ArrayList analysis

You know, arrayList is an array implementation. I use it all the time, but I haven’t seen much of it.

1. ArrayList initial parameters and capacity expansion mechanism

Two construction methods

As you can see from the constructor below, elements are placed inside elementData, which is an array.

No initial capacity is specified

As you can see, the no-parameter constructor does not set the capacity

  public ArrayList(a) {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }
Copy the code

The problem?

What is DEFAULTCAPACITY_EMPTY_ELEMENTDATA?
// Shared empty array instance used for default sized empty instances. We distinguish this from EMPTY_ELEMENTDATA to know how much to inflate when first element is added.
// Shared empty array instances, empty instances for the default size, and EMPTY_ELEMENTDATA differentiates the start to know how much to swell when the first element is added
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
Copy the code
It’s just an empty array. It’s nothing. What is the EMPTY_ELEMENTDATA mentioned above?
// Shared empty array instance used for empty instances.
// Shared empty array instances are used for empty instances.
private static final Object[] EMPTY_ELEMENTDATA = {};
Copy the code
The difference between the two has been explained in the notes above, but it feels foggy,

EMPTY_ELEMENTDATA and DEFAULTCAPACITY_EMPTY_ELEMENTDATA are both empty arrays, but DEFAULTCAPACITY_EMPTY_ELEMENTDATA is the default for initial capacity. EMPTY_ELEMENTDATA is used when initialCapacity is specified as 0.

Specify initial capacity

 // This is easy enough, but if initialCapacity is specified, if 0, elementData is EMPTY_ELEMENTDATA;
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 code

grow(int minCapacity)

It is recommended that you read the following section of Add first, which was originally written in the Add section, but moved here for structural integrity

private void grow(int minCapacity) {
    // overflow-conscious code
    // The length of the original array
    int oldCapacity = elementData.length;
  
  // The new array is 1.5 times the length of the original array.
    int newCapacity = oldCapacity + (oldCapacity >> 1);
  
  // If the calculated capacity is smaller than the minimum capacity, then gg. Direct minimum capacity
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    // If the calculated new capacity is too large, the following method gives it a large value
   // private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    // minCapacity is usually close to size, so this is a win:
  
   Array.copyof (system.copyarray); // Array.copyArray (system.copyarray
    elementData = Arrays.copyOf(elementData, newCapacity);
}


 // 
 private static int hugeCapacity(int minCapacity) {
    // Why is it less than 0, because overflow is likely
        if (minCapacity < 0) // overflow
            throw new OutOfMemoryError();
        return (minCapacity > MAX_ARRAY_SIZE) ?
            Integer.MAX_VALUE :
            MAX_ARRAY_SIZE;
    }
Copy the code

A few expansion and initialization points

If no size is specified, the default is 10 (DEFAULT_CAPACITY)

When you expand it, you expand it by 1.5 times. This is based on his formula above

A +a/2 = 3/2a = 1.5a
int newCapacity = oldCapacity + (oldCapacity >> 1);
Copy the code

If the capacity is too large, exceeding integer.max_value, an overflow occurs. An OutOfMemoryError is thrown based on whether it is less than 0

2. Analysis of related methods of ADD

When you add it, you add it directly to the end.

  public boolean add(E e) {
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        elementData[size++] = e;
        return true;
    }
Copy the code

With the exception of the EnrecapityInternal method, the rest is pretty simple. The point is, what’s going on in it?

ensureCapacityInternal

 private void ensureCapacityInternal(int minCapacity) {
        ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
    }


// If elementData is DEFAULTCAPACITY_EMPTY_ELEMENTDATA, note that reference addresses are used here.
private static int calculateCapacity(Object[] elementData, int minCapacity) {
      // As long as the initial capacity is specified, minCapacity is returned directly.
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
          MinCapacity =size+1; minCapacity=size+1; So minCapacity is equal to 1
          // private static final int DEFAULT_CAPACITY = 10;
            return Math.max(DEFAULT_CAPACITY, minCapacity);
        }
        return minCapacity;
    }

// 
 private void ensureExplicitCapacity(int minCapacity) {
         
       // Fail quickly. Record change count,
   // modCount=modifyCount
   			modCount++;

       // The size of the array has not reached the required minimum size, so it needs to be expanded. The analysis of this group method is written in the above chapter.
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }
Copy the code

Conclusion:

The add method determines whether an element needs to be expanded before adding it. The minimum element length is required to be the current array length +1. This is not the same as a HashMap, which determines whether it needs to be expanded or converted to a red-black tree after adding elements, in preparation for the next time.

When you add, you add modCount, which counts the number of operations. Used for quick failure.

And the array expansion is throughSystem.arraycopyMethod to do it.

Therefore, this is also the hard part of arrayList expansion, and its space utilization is lower than that of LinkList, after all, it is continuous storage space

3. Remove method analysis

The remove method removes the first element that meets the condition. When I remove, I’m going to iterate over it from scratch, which is not tolerable for some frameworks with extreme performance requirements (HikariCP)

So remove is iterated from the beginning.

public boolean remove(Object o) {
        if (o == null) {
            for (int index = 0; index < size; index++)
                if (elementData[index] == null) {
                    fastRemove(index);
                    return true; }}else {
            for (int index = 0; index < size; index++)
                if (o.equals(elementData[index])) {
                    fastRemove(index);
                    return true; }}return false;
    }
Copy the code

The above search is easy to find, but the point is what does fastRemove do?

This method provides an answer to why array storage is inconvenient to delete elements, and how deletion is done.

// This index is the index position of the element to be deleted
private void fastRemove(int index) {
   // this is also a quick fail count++
        modCount++;
        // The length of the move, which is the number of elements after the node to be removed, because of the data integrity of the array
        int numMoved = size - index - 1;
  
      // Copy numMoved, starting with the next element to be removed from the current array, to the index position of the current array.
        if (numMoved > 0)
            System.arraycopy(elementData, index+1, elementData, index,
                             numMoved);
  
   	   // This assigns the last element to null, because the top element is just the previous one. But the last one is still there, not covered.
        elementData[--size] = null; // clear to let GC do its work
    }
Copy the code

That’s the logic of moving arrays. There’s nothing to say. It’s all in the notes

4. AddAll method analysis

At first I thought addAll would iterate over the array passed in, but now it doesn’t. I call System. Arraycopy to copy the array.

    public boolean addAll(Collection<? extends E> c) {
       // Become an array
        Object[] a = c.toArray();
        int numNew = a.length;
       // This is the method in the add operation above, to determine whether the capacity needs to be expanded. If the capacity is smaller than this, then the capacity value is the required capacity of the library
        ensureCapacityInternal(size + numNew);  // Increments modCount
       // Copy the entire array into elementData using a direct copy of the array
        System.arraycopy(a, 0, elementData, size, numNew);
        size += numNew;
        returnnumNew ! =0;
    }
Copy the code

By reading the comments on the source code of ArrayList, there is an Enrecapacity method that is commented like this

An application can increase the capacity of an ArrayList instance before adding a large number of elements using the ensureCapacity operation. This may reduce the amount of incremental reallocation. The ensureCapacity method can be called before adding a large number of elements to reduce capacity expansionCopy the code

A little tip, recorded here.

Let’s look at the source code

   public void ensureCapacity(int minCapacity) {
        // What is the minimum increment? If elementData is not DEFAULTCAPACITY_EMPTY_ELEMENTDATA (list without specifying initial capacity)
      // 
        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;
      // As long as you specify the size, the minCapacity can be used at will, but it cannot be smaller than the previous one. If it is smaller than the previous one, nothing is done.
        if(minCapacity > minExpand) { ensureExplicitCapacity(minCapacity); }}Copy the code

5. Fail fast

Let’s start with Alibaba’s development manual, starting with his demo

I’m going to use the iterator directly.

  @Test
    public void testArrayList(a){
        ArrayList<String> list = new ArrayList<>(0);
        list.add("1");
        list.add("2");
        Iterator<String> iterator = list.iterator();
        for(; iterator.hasNext();) {if("1".equals(iterator.next())){
                list.remove("1");
            }
        }
        System.out.println(list);
    }
 // The result is 2
Copy the code

You can see that the iterator used here is iterator traversal, but it does call the remove method of the list when deleting, which should be called iterator to delete

So what happens when YOU change 1 to 2

Direct error, direct quote ConcurrentModificationException

In addition, I found that only two elements of the list are not reported and only the first element is deleted. If one of the conditions is not met, an error is reported

Add (“3”).

Source code analysis

Remember what I said about modCount? This records the number of changes to the list.

Add and remove both modCount++.

The problem is the iterator. Look what the iterator does.

// The Itr class of ArrayList
private class Itr implements Iterator<E> {
        int cursor;       // index of next element to return
        int lastRet = -1; // index of last element returned; -1 if no such
        int expectedModCount = modCount; // The case is solved, where modCount is assigned to expectedModCount inside the iterator

        Itr() {}
       // Check whether cursor is equal to list size
        public boolean hasNext(a) {
            returncursor ! = size; }@SuppressWarnings("unchecked")
        public E next(a) {
          ExpectedModCount = modCount is checked before each next
            checkForComodification();
            int i = cursor;
            if (i >= size)
                throw new NoSuchElementException();
            Object[] elementData = ArrayList.this.elementData;
            if (i >= elementData.length)
                throw new ConcurrentModificationException();
            cursor = i + 1;
            return (E) elementData[lastRet = i];
        }

        public void remove(a) {
            if (lastRet < 0)
                throw new IllegalStateException();
            checkForComodification();

            try {
               // Remove calls the list method again, specifying subscripts to remove.
                ArrayList.this.remove(lastRet);
                cursor = lastRet;
                lastRet = -1;
              // modCount will be reassigned during remove.
                expectedModCount = modCount;
            } catch (IndexOutOfBoundsException ex) {
                throw newConcurrentModificationException(); }}@Override
        @SuppressWarnings("unchecked")
        public void forEachRemaining(Consumer<? super E> consumer) {
            Objects.requireNonNull(consumer);
            final int size = ArrayList.this.size;
            int i = cursor;
            if (i >= size) {
                return;
            }
            final Object[] elementData = ArrayList.this.elementData;
            if (i >= elementData.length) {
                throw new ConcurrentModificationException();
            }
            while(i ! = size && modCount == expectedModCount) { consumer.accept((E) elementData[i++]); }// update once at end of iteration to reduce heap write traffic
            cursor = i;
            lastRet = i - 1;
            checkForComodification();
        }

        final void checkForComodification(a) {
            if(modCount ! = expectedModCount)throw newConcurrentModificationException(); }}Copy the code

ModCount in arrayList is assigned to modCount in iterator when iterator is created. Each time at next, it will check whether the two are equal. If they are not equal, an error will be reported. When the iterator’s remove method is called, modCount is re-assigned to the expectedModCount.

The reason is found, let’s analyze the above situation, if 1 is changed to 2, an error will be reported, why?

If I go to 2

  @Test
    public void testArrayList(a){
        ArrayList<String> list = new ArrayList<>(0);
        list.add("1");
        list.add("2");
        Iterator<String> iterator = list.iterator();
        for(; iterator.hasNext();) {if("2".equals(iterator.next())){
                list.remove("1");
            }
        }
        System.out.println(list);
    }
ModCount =2 when we get the iterator (because we added it twice)
// If the first loop is not satisfied, nothing changes
// The modCount in the list will be ++ when the remove method is called. And the size will decrease. At the end of the first loop, lastRet becomes 0 and cursor=1. At the end of the second loop, lastRet becomes 1. At the end of the second loop, lastRet becomes 1. Cursor becomes 2, satisfying the iterator's HasNext method (CURSOR! If modCount and expectedModCount are not equal, an error is reported.
Copy the code

The same goes for deleting the first element if the array is of length 3


    @Test
    public void testArrayList(a){
        ArrayList<String> list = new ArrayList<>(0);
        list.add("1");
        list.add("2");
        list.add("3");
        Iterator<String> iterator = list.iterator();
        for(; iterator.hasNext();) {if("1".equals(iterator.next())){
                list.remove("1");
            }
        }
        System.out.println(list);
    }
Copy the code

In the first loop, the condition is satisfied, but the iterator inside the expectedModCount is not changed, the list inside the iterator is changed, the iterator inside the lastRet=0, cursor=1, and the list size is 2, which satisfies the hasNext condition. In the second loop, The next method checks that the two are different, so an error is reported.

Suddenly thought of

When I first learned Java, I heard people say that iterator traversal is a copy of the previous data. Now, it is really not so. I also wrote about the iterator traversal order in a previous Map blog post. I don’t see a copy operation.

Now that I think about it, why do I delete by iterator? To avoid this quick failure. Also, removing elements via iterators is essentially done by calling the remove (subscript) method on the List.

This mechanism is used a lot in Java collections, but what if I have to delete iterators while iterating through them?

Write one of your own, remove this judgment method is good.

CopyOnWriteArrayList doesn’t do that

    @Test
    public void testArrayList(a){
        CopyOnWriteArrayList<String> list = new CopyOnWriteArrayList<>();

        list.add("1");
        list.add("2");
        list.add("3");
        Iterator<String> iterator1 = list.iterator();
        while (iterator1.hasNext()){
            String next = iterator1.next();
            if("2".equals(next)){
                list.remove("2");
            }
        }
        
        System.out.println(list);
    }
Copy the code

There’s no modCount in it, expectedModCount.

So much for ArrayList analysis. Please point out any inaccuracies. thank you

ArrayList analysis

ArrayList analysis

1. ArrayList initial parameters and capacity expansion mechanism

grow(int minCapacity)

A few expansion and initialization points

2. Analysis of related methods of ADD

ensureCapacityInternal

3. Remove method analysis

4. AddAll method analysis

5. Fail fast

Source code analysis

Suddenly thought of

Related Posts

Kinaba for ElasticSearch

Object orientation of design patterns

Go daily library validator