Table of Contents

  • ArrayList
    • ArrayList overview
    • Inheritance of ArrayList
    • Underlying data structure
    • Add and delete
    • modCount
    • Initial capacity and expansion mode
    • Thread safety
  • Vector
    • Introduction of the Vector
    • Add and delete
    • Initial capacity and expansion
    • Thread safety
  • Stack
  • Stack

    • The difference between three collection classes

    • Refer to the article

      // The general discussion of collection classes is nothing more than. This is especially true for the two types of arrays // 1 underlying data structure // 2 Increase, delete, change, and search methods // 3 Initial capacity, expansion mode, and expansion time. // 4 is thread safe or not // 5 is empty allowed, is repeated allowed, is ordered

ArrayList

ArrayList overview

ArrayList is a dynamic array that implements the List interface. Dynamic means its size is variable. All optional list operations are implemented and all elements, including NULL, are allowed. In addition to implementing the List interface, this class also provides methods to manipulate the size of the array internally used to store the List.

Each ArrayList instance has a capacity, which is the size of the array used to store the elements of the list. The default initial capacity is 10. As you add more elements to an ArrayList, its capacity automatically grows.

Each time a new element is added, ArrayList checks whether a capacity expansion operation is needed. Capacity expansion operation causes data to be copied to the new array. Therefore, if we know the specific amount of service data, we can specify an initial capacity for ArrayList when constructing ArrayList, which will reduce the data copy problem during capacity expansion. Of course, an application can also use the ensureCapacity operation to increase the capacity of an ArrayList instance before adding a large number of elements, which reduces the amount of incremental reallocation.

Note that the ArrayList implementation is not synchronous. If multiple threads access an ArrayList instance simultaneously, and at least one of them structurally modifies the list, it must maintain external synchronization. So to ensure synchronization, it is best to do this at creation time to prevent accidental unsynchronized access to the list:

List list = Collections.synchronizedList(new ArrayList(...) );Copy the code

Inheritance of ArrayList

ArrayList inherits the AbstractList abstract parent class and implements the List interface (specifying the List operation specification), RandomAccess (RandomAccess), Cloneable (copy-able), Serializable (Serializable).

Underlying data structure

At the bottom of an ArrayList is an object array, decorated with Trasient.

//transient Object[] elementData; //
Copy the code

Non-private to simplify the serialization of class access //ArrayList

// Use the writeObject method for serialization. Why do you do this

// To sum up, only the positions with values in the array are copied. The other unassigned positions are not serialized to save space.

// 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

Add and delete

// Add, delete, modify and checkCopy the code

When adding elements, check whether the index is valid, then check whether expansion is needed, and finally use the System. Arraycopy method to complete the arraycopy.

This method simply copies the data from the C collection into the elementData array using the system.arrayCopy () method. I’ll cover system.arrayCopy () a little bit here, because I’ll be using it a lot more

. The prototype of this method is:

Public static void arrayCopy (Object SRC, int srcPos, Object Dest, int destPos, int length)Copy the code

Its basic purpose is to copy array elements. That is, copies an array from the specified source array, starting at the specified location and ending at the specified location of the destination array.

Copy the source array SRC from srcPos to dest with length of length. Paste the data from destPos in dest.

// public void add(int index, E element) { // rangeCheckForAdd(index); // // ensureCapacityInternal(size + 1); // Increments modCount!! // System.arraycopy(elementData, index, elementData, index + 1, // size - index); // elementData[index] = element; // size++; / / / /}Copy the code

When deleting an element, the index is also checked by moving the element to the right of the deleted element to the left, using the same method of System. Arraycopy.

//        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 code

ArrayList provides a way to empty an array by setting all elements to null so that the GC can automatically reclaim elements that are not referenced.

// // /** // * Removes all of the elements from this list. The list will // * be empty after this call returns. // */ //  public void clear() { // modCount++; // // // clear to let GC do its work // for (int i = 0; i < size; i++) // elementData[i] = null; // // size = 0; / /}Copy the code

When you modify an element, you simply check the subscript.

// public E set(int index, E element) { // rangeCheck(index); // // E oldValue = elementData(index); // elementData[index] = element; // return oldValue; // } // // public E get(int index) { // rangeCheck(index); // // return elementData(index); / / / /}Copy the code

All of these methods use the rangeCheck method, which simply checks the subscripts.

//        private void rangeCheck(int index) {
//            if (index >= size)
//                throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
//        }
Copy the code

modCount

//        protected transient int modCount = 0;
Copy the code

As can be seen from the above code, an iterator is initially assigned the mCount of the object calling the iterator. How to throw an exception if the mCount of the object is found to be different from the mCount stored in the iterator

Ok, here is the full explanation mechanism Fail – Fast We know Java. Util. ArrayList is not thread-safe, ArrayList, and then will throw ConcurrentModificationException, This is known as the Fail-fast strategy.

This strategy is implemented in the source code via the modCount field, which as the name indicates, is the number of changes. Any changes to the contents of the ArrayList increase this value, which is then assigned to the expectedModCount of the iterator during initialization.

During iteration, test whether modCount and expectedModCount are equal. If they are not equal, it indicates that other threads have modified the ArrayList.

So I recommend that you use iterators when traversing non-thread-safe data structures

Initial capacity and expansion mode

The initial capacity is 10. Here’s how to expand it. First of all a turn

// private static final int DEFAULT_CAPACITY = 10; Public Boolean add(E E) {ensureCapacityInternal(size + 1); // Increments modCount!! elementData[size++] = e; return true; Private static Final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {}; private static Final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {}; If the array is still an initial array, then the minimum expansion size is the larger of size+1 and the initial capacity, which is 10. Because the addall method also calls this function, you need to make a judgment call at this point. private void ensureCapacityInternal(int minCapacity) { if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) { minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity); } ensureExplicitCapacity(minCapacity); } private void ensureExplicitCapacity(int minCapacity) {modCount++; // overflow-conscious code Executes grow if the size of the array is larger than the size of the array. if (minCapacity - elementData.length > 0) grow(minCapacity); }Copy the code

Actually perform the expansion method grow

The new capacity is equal to 1.5 tons of the old capacity.

When the new array capacity is greater than the maximum array capacity, a large array capacity expansion is performed

//        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

When the new capacity is greater than the maximum array length, there are two cases, one is overflow, throw exceptions, one is not overflow, return the maximum value of the integer.

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

There is a question here, why is it that each expansion process is 1.5 times instead of 2.5, 3, 4 times? Through Google search, it was found that 1.5 times expansion is the best multiple. This is because a large expansion at one time (e.g. 2.5 times) can waste more memory (1.5 times at most wastes 33%, 2.5 times at most wastes 60%, 3.5 times at most wastes 71%…) . However, one time capacity expansion is too small, requiring multiple array memory reallocation, which is a serious performance consumption. So 1.5x is just right, satisfying performance requirements without consuming a lot of memory.

In addition to dealing with the ensureCapacity() expansion array, ArrayList also gives us the ability to adjust the capacity of the underlying array to the size of the actual elements that the current list holds. This can be done with the trimToSize() method. This method minimizes the storage capacity of an ArrayList instance.

public void trimToSize() { modCount++; int oldCapacity = elementData.length; if (size < oldCapacity) { elementData = Arrays.copyOf(elementData, size); }}Copy the code

Thread safety

ArrayList is thread-unsafe. In its iterator Iteator, Fastfail is executed if a multi-threaded operation causes the Modcount to change. Throw an exception.

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

Vector

Introduction of the Vector

Vector implements a growable array of objects. Like an array, it contains components that can be accessed using integer indexes. However, the size of a Vector can be increased or decreased to accommodate additions or deletions after it is created.

Vector implements the List interface and inherits the AbstractList class, so we can think of it as a queue, supporting addition, deletion, modification, traversal, etc.

Vector implements the RandmoAccess interface, which provides random access and fast access. In Vector we can access elements directly.

Vector implements the Cloneable interface and supports the clone() method, which can be cloned.

The underlying array of vector is not transient and is copied when serialized

 protected Object[] elementData;



//        private void writeObject(java.io.ObjectOutputStream s)
//            throws java.io.IOException {
//            final java.io.ObjectOutputStream.PutField fields = s.putFields();
//            final Object[] data;
//            synchronized (this) {
//                fields.put("capacityIncrement", capacityIncrement);
//                fields.put("elementCount", elementCount);
//                data = elementData.clone();
//            }
//            fields.put("elementData", data);
//            s.writeFields();
//        }
Copy the code

Vector also provides Enumeration methods in addition to iterator, which is now outdated.

// public Enumeration<E> elements() { // return new Enumeration<E>() { // int count = 0; // // public boolean hasMoreElements() { // return count < elementCount; // } // // public E nextElement() { // synchronized (Vector.this) { // if (count < elementCount) { // return elementData(count++); // } // } // throw new NoSuchElementException("Vector Enumeration"); / / / /}}; / / / /}Copy the code

Add and delete

Vector provides its own implementation and inherits some methods of the abstractList abstract class. The following methods are implemented by Vector itself.

//
//    public synchronized E elementAt(int index) {
//        if (index >= elementCount) {
//            throw new ArrayIndexOutOfBoundsException(index + " >= " + elementCount);
//        }
//
//        return elementData(index);
//    }
//
//

//    public synchronized void setElementAt(E obj, int index) {
//        if (index >= elementCount) {
//            throw new ArrayIndexOutOfBoundsException(index + " >= " +
//                    elementCount);
//        }
//        elementData[index] = obj;
//    }
//


//    public synchronized void removeElementAt(int index) {
//        modCount++;
//        if (index >= elementCount) {
//            throw new ArrayIndexOutOfBoundsException(index + " >= " +
//                    elementCount);
//        }
//        else if (index < 0) {
//            throw new ArrayIndexOutOfBoundsException(index);
//        }
//        int j = elementCount - index - 1;
//        if (j > 0) {
//            System.arraycopy(elementData, index + 1, elementData, index, j);
//        }
//        elementCount--;
//        elementData[elementCount] = null; /* to let gc do its work */
//    }


//    public synchronized void insertElementAt(E obj, int index) {
//        modCount++;
//        if (index > elementCount) {
//            throw new ArrayIndexOutOfBoundsException(index
//                    + " > " + elementCount);
//        }
//        ensureCapacityHelper(elementCount + 1);
//        System.arraycopy(elementData, index, elementData, index + 1, elementCount - index);
//        elementData[index] = obj;
//        elementCount++;
//    }
//

//    public synchronized void addElement(E obj) {
//        modCount++;
//        ensureCapacityHelper(elementCount + 1);
//        elementData[elementCount++] = obj;
//    }
Copy the code

Initial capacity and expansion

The expansion method is basically the same as ArrayList, but instead of 1.5x expansion, there is an expansion increment.

//    protected int elementCount;

//    protected int capacityIncrement;
//
//
//    }
//    public Vector() {
//        this(10);
//    }
Copy the code

CapacityIncrement: The amount of a vector whose size is greater than its capacity that is automatically increased. If capacityIncrement is specified when creating the Vector; Then, each time the dynamic array capacity in the Vector increases >, the increment is capacityIncrement. If the increment in capacity is less than or equal to zero, the capacity of the vector doubles each time it needs to increase capacity.

//        public synchronized void ensureCapacity(int minCapacity) {
//            if (minCapacity > 0) {
//                modCount++;
//                ensureCapacityHelper(minCapacity);
//            }
//        }
//        private void ensureCapacityHelper(int minCapacity) {
//            // overflow-conscious code
//            if (minCapacity - elementData.length > 0)
//                grow(minCapacity);
//        }
//
//        private void grow(int minCapacity) {
//            // overflow-conscious code
//            int oldCapacity = elementData.length;
//            int newCapacity = oldCapacity + ((capacityIncrement > 0) ?
//                    capacityIncrement : oldCapacity);
//            if (newCapacity - minCapacity < 0)
//                newCapacity = minCapacity;
//            if (newCapacity - MAX_ARRAY_SIZE > 0)
//                newCapacity = hugeCapacity(minCapacity);
//            elementData = Arrays.copyOf(elementData, newCapacity);
//        }
Copy the code

The following is a schematic diagram of the expansion process

Thread safety

Most methods in vector use the synchronized modifier, so it is a line-level safe collection class.

Stack

One of the most common data structures we use is probably the stack. In the actual program execution, method call process are inseparable from stack. So what does it look like in a mature class library? Maybe we’ll try to write an implementation of stack in practice. Here, we will carefully analyze the detailed implementation in the JDK.

Stack

If we look in the JDK documentation, we’ll see that stack is in the java.util package. It corresponds to a rough class diagram as follows:

The Stack class can easily implement its own functions by inheriting from Vector. Because most of the functionality is already supported in Vector. In Java, the Stack class represents a last in, first out (LIFO) Stack of objects. The stack is a very common data structure, which is implemented in a typical fifo manner.

Stack extends a Vector with five operations that allow a Vector to be treated as a Stack. The five operations are as follows:

empty()

Tests whether the stack is empty.

peek()

View the object at the top of the stack without removing it from the stack.

pop()

Removes the object at the top of the stack and returns it as the value of this function.

push(E item)

Push items onto the top of the stack.

search(Object o)

Returns the position of the object in the stack, base 1.

Stack inherits Vector with a simple extension:

The implementation of public Class Stack extends Vector Stack is very simple. It has only one constructor, five implementation methods (methods inherited from a Vector do not count), and the source code for the implementation is very simple

Public E push(E item) {// Public E push(E item) {// Public E push(E item) {// Public E push(E item) { // The implementation of addElement() in vector.java addElement(item); return item; } /** * synchronized E pop() {synchronized E pop(); int len = size(); obj = peek(); RemoveElementAt () is implemented in vector.java removeElementAt(len-1); return obj; } public synchronized E peek() {int len = size(); if (len == 0) throw new EmptyStackException(); // Return elementAt(len-1); // Return elementAt(len-1); } public Boolean empty() {return size() == 0; } /** * find the position of "element o" in stack: Public synchronized int search(Object o) {public synchronized int search(Object o) { if (i >= 0) { return size() - i; } return -1; }Copy the code

Much of the source code for Stack is based on Vector, so I won’t cover it here

The difference between three collection classes

Pros and cons of ArrayList

Summarize the pros and cons of ArrayList from the above procedures. ArrayList has the following advantages:

1. ArrayList is implemented as an array, which is a RandomAccess mode, plus it implements the RandomAccess interface, so lookups (get) are very fast

2. Arraylists are very convenient for adding elements sequentially, just adding an element to an array

But the disadvantages of ArrayList are also obvious:

1. When deleting an element, it involves a copy of the element. If there are many elements to copy, it will cost performance

2. When inserting an element, it involves a copy of the element. If there are many elements to copy, it will cost performance

Therefore, ArrayList is suitable for sequential addition and random access scenarios.

Difference between an ArrayList and a Vector

An ArrayList is thread-unsafe, which is obvious because none of the methods in an ArrayList are synchronized, and thread-safe problems are bound to occur in concurrent conditions. So what if we want to use ArrayList and make it thread-safe? . One way is to use the Collections synchronizedList methods make your ArrayList a thread safe List, such as:

List<String> synchronizedList = Collections.synchronizedList(list);
synchronizedList.add("aaa");
synchronizedList.add("bbb");
for (int i = 0; i < synchronizedList.size(); i++)
{
    System.out.println(synchronizedList.get(i));
}
Copy the code

Another method is Vector, which is a thread-safe version of ArrayList. Its implementation is 90% identical to ArrayList, except that:

1. Vector is thread-safe. ArrayList is thread-safe

2. Vector can specify a growth factor. If the growth factor is specified, each new array size is added to the original array size. If you do not specify a growth factor, then give the original array size *2. The source code looks like this:

int newCapacity = oldCapacity + ((capacityIncrement > 0) ?
                                 capacityIncrement : oldCapacity);
Copy the code

Refer to the article

www.cnblogs.com/williamjie/…

www.cnblogs.com/shenzhichip…

www.cnblogs.com/rnmb/p/6553…

Blog.csdn.net/u011419651/…

www.jianshu.com/p/c4027084a…