This article gives a very detailed introduction to three collection classes in Java
Array List, Vector and Stack

The Java Collection Detailed Series is a new series that I am going to start after I have completed a series of blogs that consolidate the Java Foundation Chapter.

These articles will be sorted out into my Java Interview Guide warehouse on GitHub, and more exciting content can be found in my warehouse.

https://github.com/h2pl/Java-...

If you like, please click Star, fork Ha

The article was first published on my personal blog:

www.how2playlife.com

// Generally speaking, the discussion of set classes is nothing more than that. This is especially true for the two types of arrays here
 // 1 underlying data structure
 // 2. Addition, deletion and modification of checking methods
 // 3. Initial capacity, expansion mode and expansion opportunity.
// 4 Thread Safety or Not
 // Whether to allow empty, whether to allow duplication, whether orderly 

ArrayList

Overview of ArrayList

ArrayList is a dynamic array that implements the List interface. The so-called dynamic is that 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 some ways to manipulate the size of the array used internally to store lists.

Each ArrayList instance has a capacity, which refers to the size of the array used to store list elements. The default initial capacity is 10. As the number of elements in ArrayList increases, its capacity will continue to grow automatically.

Every time a new element is added, ArrayList checks whether an expansion operation is needed. The expansion operation brings a new copy of the data to the new array. So if we know the specific amount of business data, we can assign an initial capacity to the ArrayList when constructing the ArrayList, which will reduce the problem of data copy during expansion. Of course, before adding a large number of elements, the application can also use the ensureCapacity operation to increase the capacity of ArrayList instances, which can reduce the number of incremental redistributions.

Note that the ArrayList implementation is not synchronous. If multiple threads access an ArrayList instance at the same time, and at least one thread modifies the list structurally, it must keep external synchronization. So the best way to ensure synchronization is to complete it at creation time to prevent accidental asynchronous access to lists:

    List list = Collections.synchronizedList(new ArrayList(...)); 
    

Inheritance of ArrayList

ArrayList inherits AbstractList Abstract parent class and implements List interface (specifying the operation specification of List), Random Access (random access), Cloneable (copiable), Serializable (serializable).

### underlying data structure

The bottom of the ArrayList is an array of object s, and is decorated by trasient.

//transient Object[] elementData; //

non-private to simplify nested class access
// The ArrayList underlying array does not participate in serialization, but uses another way of serialization.

// Use the writeobject method for serialization, and why? Welcome to my previous article on serialization.

// To sum up, just copy the position of value in the array, and other unassigned positions are not serialized, which can 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();
//            }
//        }

Additions and deletions

// Addition, deletion and revision

When adding elements, we first judge whether the index is legitimate, then detect whether expansion is needed, and finally use the System.arraycopy method to complete the replication of the array.

This method is nothing more than using the System.arraycopy() method to copy the data in the C set (which must be changed into an array first) into the elementData array. Here's a little introduction to System.arraycopy(), because this method will be used extensively in the following sections

. The prototype of this method is:

public static void arraycopy(Object src, int srcPos, Object dest, int destPos, int length). 

Its fundamental purpose is to replicate array elements. That is, an array is copied from the specified source array, starting at the specified location and ending at the specified location of the target array.

The source array src is copied from the srcPos t location to the dest array. The length of the replication is length, and the data is pasted from the destPos t location of the 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++;
//        }
//

When deleting an element, the index is also judged to be legal. The way to delete the element is to move the element to the right of the deleted element to the left. The method is also to copy the element using 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;
//        }

ArrayList provides a way to empty the array by setting all elements to null so that 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;
//        }

When modifying elements, only the subscripts need to be checked to modify the operation.

//        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);
//        }
//

The above methods all use the range Check method, which is simply checking subscriptions.

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

modCount

//        protected transient int modCount = 0;

As can be seen from the above code, at the beginning of an iterator, it is given mCount of the object invoking the iterator. How to throw an exception once the mcount of the object is found to be different from the mcount stored in the iterator during iterator traversal?

Okay, here's a complete explanation of this.
Fail-Fast mechanism
We know that java.util.ArrayList is not thread-safe, ArrayList, then we will throw Concurrent ModificationException, which is the so-called fail-fast policy.

This strategy is implemented in the source code through the modCount field. modCount, as its name implies, is the number of modifications. Modifications to the ArrayList content will increase this value, which will be assigned to the expectedModCount of the iterator in the initialization process.

In the iteration process, determine whether modCount and expectedModCount are equal, if not, it means that other threads have modified ArrayList.

So here's a suggestion to use iterators whenever you're traversing non-thread-safe data structures

Initial capacity and expansion mode

The initial capacity is 10. Here is the expansion method.
First of all, take first.

//        private static final int DEFAULT_CAPACITY = 10;

When the expansion occurs at the add element, the current element capacity is added by one.
   public boolean add(E e) {
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    elementData[size++] = e;
    return true;
}


Here is an array for initialization.
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

This shows that if the array is still the initial array, then the smallest expansion size is size+1 and the larger of the initial capacity, the initial capacity is 10.
Because the addall method also calls the function, judgment needs to be made at this point.
private void ensureCapacityInternal(int minCapacity) {
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
    }

    ensureExplicitCapacity(minCapacity);
}

// Start accurately expanding
private void ensureExplicitCapacity(int minCapacity) {
    modCount++;

    // overflow-conscious code
        If the expansion capacity is larger than the array length at this time, grow is executed, otherwise it is not executed.
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}

Real implementation of expansion methods grow

The expansion method is to make the new capacity equal to 1.5 of the old capacity.

When the new capacity is larger than the maximum array capacity, large number 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);
//        }

When the new capacity is larger than the maximum array length, there are two cases, one is overflow, throwing an exception, the other is no overflow, returning 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;
}

There is a question here. Why is it that each expansion process is 1.5 times, not 2.5, 3, 4 times? Through google search, we found that 1.5 times expansion is the best multiple. Because one-time expansion is too large (for example, 2.5 times) may waste more memory (1.5 times wastes up to 33%, 2.5 times wastes up to 60%, 3.5 times wastes 71%... ) However, one-time expansion is too small, requiring multiple reallocations of memory to arrays, which consumes a lot of performance. So 1.5 times is just right, it can meet the performance requirements, and will not cause a lot of memory consumption.

In addition to handling this ensureCapacity() expanded array, ArrayList also provides us with the ability to resize the capacity of the underlying array to the size of the actual elements stored in the current list. It can be implemented by trimToSize() method. This method can minimize the storage of ArrayList instances.

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

Thread safety

ArrayList is thread insecure. In its iterator, fastfail is performed if a multithreaded operation causes a modcount change. Throw an exception.

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

Vector

Vector introduction

Vector implements an incremental array of objects. Like arrays, it contains components that can be accessed using an integer index. However, the size of Vector can be increased or reduced to accommodate adding or deleting operations after creating Vector.

Vector implements the List interface and inherits the AbstractList class, so we can consider it as a queue, supporting the relevant add, delete, modify, traverse and other functions.

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

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

vector underlying arrays are replicated when serialized without transient

 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();
//        }

Vector also provides an Enumeration enumeration method in addition to iterator, but it's outdated now.

//        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");
//                }
//            };
//        }
//

Additions and deletions

vector's add-delete checking not only provides its own implementation, but also inherits some methods of abstractList Abstract class.
The following method is 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;
//    }

Initial capacity and expansion

The expansion mode is basically the same as that of ArrayList, but the expansion is not 1.5 times as large as that of ArrayList, but has an increment.

//    protected int elementCount;

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

Capacity Increment: The amount of capacity automatically increases when the size of the vector is larger than its capacity. If the size of capacityIncrement is specified when a Vector is created; then each time the dynamic array capacity in Vector increases >, the increased size is capacityIncrement. If the increment of capacity is less than or equal to zero, the capacity of the vector will be doubled each time the capacity needs to be increased.

//        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);
//        }

Here is a diagram of the expansion process.

Thread safety

vector uses synchronized modifiers for most of its methods, so it is a line-safe collection class.

Stack

One of our most common data structures is probably stack. In the process of actual program execution and method call, stack is indispensable. So, in a mature class library, how is its implementation? Maybe we will try to write a stack implementation to play when we practice. Here, we will carefully analyze the detailed implementation in jdk.

Stack

If we go to the jdk documentation, we will find that stack is in the java.util package. Its corresponding general class diagram is as follows:

By inheriting the vector class, the Stack class can easily implement its own functions. Because most of the functions are already supported in Vector.
In Java, the Stack class represents the object stack of LIFO. Stack is a very common data structure, which is accomplished by a typical "first-in-last-out" mode of operation.

Stack extends Vector through five operations, allowing vectors to be considered stacks. The five operations are as follows:

empty()

Test whether the stack is empty.

peek()

View the object at the top of the stack, but do not remove it from the stack.

pop()

Remove the object at the top of the stack and return it as the value of the function.

push(E item)

Press the item onto the top of the stack.

search(Object o)

Returns the location of the object on the stack, based on 1.

Stack inherits Vector, which he extends simply:

public class Stack<E> extends Vector<E>
The implementation of Stack is very simple. There is only one construction method, five implementation methods (the method inherited from Vector does not count among them), and the source code of its implementation is very simple.

/**
 * Constructor
 */
public Stack() {
}

/**
 *  push Function: Store elements at the top of the stack
 */
public E push(E item) {
    // Store elements on the top of the stack.
    // The implementation of addElement() in Vector.java
    addElement(item);

    return item;
}

/**
 * pop Function: Returns the top element of the stack and deletes it from the stack
 */
public synchronized E pop() {
    E    obj;
    int    len = size();

    obj = peek();
    // Delete the top element of the stack, removeElementAt() is implemented in Vector.java
    removeElementAt(len - 1);

    return obj;
}

/**
 * peek Function: Returns the top element of the stack without deleting it
 */
public synchronized E peek() {
    int    len = size();

    if (len == 0)
        throw new EmptyStackException();
    // Returning to the top element of the stack, elementAt() is implemented in Vector.java
    return elementAt(len - 1);
}

/**
 * Is the stack empty?
 */
public boolean empty() {
    return size() == 0;
}

/**
 *  Find the location of "element o" in the stack: the number of directions from the bottom to the top of the stack
 */
public synchronized int search(Object o) {
    // Get the element index, elementAt() is implemented in Vector.java
    int i = lastIndexOf(o);

    if (i >= 0) {
        return size() - i;
    }
    return -1;
}

Stack's source code is mostly based on Vector, so I won't repeat it here.

Differences among Three Collection Classes

Advantages and disadvantages of ArrayList

Summarize the advantages and disadvantages of ArrayList from the above processes. The advantages of ArrayList are as follows:

1. The bottom of ArrayList is implemented as an array, which is a random access mode. In addition, it implements the Random Access interface, so the search time is very fast.

2. ArrayList is very convenient to add an element in order, but only to add an element to the array.

However, the drawbacks of ArrayList are obvious:

1. When deleting elements, it involves an element replication. If there are many elements to replicate, it will consume performance.

2. When inserting elements, it involves one element replication. If there are many elements to replicate, it will consume performance.

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

The difference between ArrayList and Vector

ArrayList is thread insecure, which is obvious, because all methods in ArrayList are not synchronized, and there will be thread security problems next to concurrency. So what if we want to use ArrayList and make it thread safe? One way is to use the Collections. synchronized List method to turn your ArrayList into 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));
}

Another approach is Vector, which is a thread-safe version of ArrayList, which implements 90% exactly the same as ArrayList, except that:

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

2. Vector can specify the growth factor. If the growth factor is specified, the new array size will be added to the original array size every time it expands. If the growth factor is not specified, then the original array size * 2 will be given. The source code is as follows:

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

Reference articles

https://www.cnblogs.com/willi...

https://www.cnblogs.com/shenz...

https://www.cnblogs.com/rnmb/...

https://blog.csdn.net/u011419...

https://www.jianshu.com/p/c40...

Wechat Public Number

Java Technology

If you want to pay real-time attention to my updated articles and shared dried goods, you can pay attention to my public number (Java Technology Jianghu), a technology station of an Ali Java engineer, by Huang Xiaoxiao, focusing on Java related technologies: SSM, Spring Boot, MySQL, distributed, middleware, cluster, Linux, network, multi-threading, occasionally talking about Docker, ELK, and sharing at the same time. Technical dry goods and learning experience, dedicated to Java stack development!

Java Engineers Necessary Learning Resources: Some Java Engineers commonly use learning resources. After paying attention to the public number, the keyword "Java" can be answered in the background for free without routine access.

Personal Public No. Huang Xiaoxiao

Huang Xiaoxiao is a 985 master of cross-examination software engineering. He has taught himself Java for two years. He has been offer ed by nearly ten big factories, such as BAT, and has grown from a technical Xiaobai to an Ali engineer.

The author concentrates on JAVA backend technology stack, and is keen to share programmers'dry goods, learning experience, job hunting experience and programmer life. At present, Huang Xiaoxiao's CSDN blog has millions of + visits, and he knows that fans are 2+. There are 10W + readers on the whole network.

Huang Xiaoxiao is a slash youth, who insists on learning and writing. He believes in the power of lifelong learning. He hopes to make friends with more programmers and make progress and grow together. Pay attention to the public number [Huang Xiaoxiao], and then reply [original e-book]. You can get my original e-book `The Training Manual for Rookie Programmers: From Technical Xiaobai to Alibaba Java Engineer'.

Programmer 3T technology learning resources: Some programmers learn technology resources package, after paying attention to the public number, the background reply keyword "information" can be free of charge without routine access.

​

This article by the blog article multiple platform OpenWrite Release!