This article provides a very detailed introduction to the three Java collection classes ArrayList,Vector, and Stack
The Java Collections In Detail series is a new series I’ve been working on since I finished a series of blog posts on building a Solid Foundation for Java.
These articles will be curated into my GitHub repository for the Java Interview Guide. Check out my repository for more highlights
https://github.com/h2pl/Java-Tutorial
Click Star, fork if you like
The article was first posted on my personal blog:
www.how2playlife.com
// 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 orderedCopy the codeArrayList
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 codeInheritance 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 codeNon-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 codeAdd and delete
// Add, delete, modify and checkCopy the codeWhen 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 codeIts 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 codeWhen 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 codeArrayList 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 codeWhen 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 codeAll 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 codemodCount
// protected transient int modCount = 0;Copy the codeAs 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’s a full explanation of this
The mechanism of Fail – Fast
We know Java. Util. ArrayList is not thread-safe, ArrayList, and then will throw ConcurrentModificationException, this is called 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;Copy the codePublic Boolean add(E E) {ensureCapacityInternal(size + 1); // Increments modCount!! elementData[size++] = e; return true; }Copy the codePrivate Static Final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};Copy the codeIf 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); }Copy the code ensureExplicitCapacity(minCapacity);
}Copy the codePrivate void ensureExplicitCapacity(int minCapacity) {modCount++;Copy the code// 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 codeActually 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 codeWhen 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 codeThere 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); }} ### thread safetyCopy the codeArrayList 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 codeVector
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;
Copy the code // 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 codeVector 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 codeAdd 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); / / / / / /}Copy the code// public synchronized void setElementAt(E obj, int index) { // if (index >= elementCount) { // throw new ArrayIndexOutOfBoundsException(index + " >= " + // elementCount); // } // elementData[index] = obj; / / / /}Copy the code // 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 */
// }
Copy the code// 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++; / / / /}Copy the code // public synchronized void addElement(E obj) {
// modCount++;
// ensureCapacityHelper(elementCount + 1);
// elementData[elementCount++] = obj;
// }Copy the codeInitial 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;Copy the code // protected int capacityIncrement;
//
//
// }
// public Vector() {
// this(10);
// }Copy the codeCapacityIncrement: 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 codeThe 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 VectorStack is very simple. It has only one constructor, five implementation methods (methods inherited from a Vector are not included), and the source code for the implementation is very simple
/** * public Stack() {}Copy the codePublic E push(E item) {// Push (E item) {// Push (E item) {// Push (E item); // The implementation of addElement() in vector.java addElement(item);Copy the code return item;
}Copy the code*/ public synchronized E pop() {E obj; int len = size();Copy the codeobj = peek(); RemoveElementAt () is implemented in vector.java removeElementAt(len-1);Copy the code return obj;
}Copy the code*/ public synchronized E peek() {int len = size();Copy the codeif (len == 0) throw new EmptyStackException(); // Return elementAt(len-1); // Return elementAt(len-1); }Copy the codePublic Boolean empty() {return size() == 0; }Copy the code/** * find the position of "element o" in stack: Public synchronized int search(Object o) {public synchronized int search(Object o) {Copy the code if (i >= 0) {
return size() - i;
}
return -1;
}Copy the codeMuch 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 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 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 codeRefer to the article
https://www.cnblogs.com/williamjie/p/11158523.html
https://www.cnblogs.com/shenzhichipingguo/p/10075212.html
https://www.cnblogs.com/rnmb/p/6553711.html
https://blog.csdn.net/u011419651/article/details/83831156
https://www.jianshu.com/p/c4027084ac43
Wechat official account
Java Technology
If you want to follow my updated articles and share dry goods in real time, you can follow my public account [Java Technology Jianghu] an Ali Java engineer technical station, the author huang Xiaoxi, focus on Java related technology: SSM, SpringBoot, MySQL, distributed, middleware, cluster, Linux, network, multithreading, occasionally speak point Docker, ELK, but also share technology dry goods and learning experience, committed to Java full stack development!
Necessary learning resources for Java engineers: Some Java engineers commonly use learning resources. After following the public account, the background replies with the keyword “Java” for free.
Personal public account: Huang Xiaoxi
Huang Xiaoxi has a 985 master’s degree in software engineering. She has taught herself Java for two years and has received offers from BAT and other nearly ten big factories. She has grown from a technical white to an engineer in Ali.
The author focuses on JAVA backend technology stack, and is keen on sharing programmers’ practical knowledge, learning experience, job hunting experience and program life. At present, Huang xiaoxi’s CSDN blog has more than one million + visits, and zhihu has more than 2 million fans, and the whole network has more than 10 million readers.
Huang Xiaoxi is a slash youth, insist on learning and writing, believe in the power of lifelong learning, hope to make friends with more programmers, progress and growth together! After following the public account [Huang Xiaoxi] and replying to [original e-book], you can receive my original e-book “Rookie Programmer Training Manual: From technical novice to Alibaba Java Engineer”.
Programmer 3T technology learning resources: some programmers learning technology resources gift package, after paying attention to the public number, the background reply keyword “information” can be free without routine access.
This article is published by OpenWrite!