This series of articles will be organized into my GitHub repository for the Java Interview Guide. Check out my repository for more highlights
https://github.com/h2pl/Java-Tutorial
If you like, please click Star
The article was first posted on my personal blog:
www.how2playlife.com
WeChat public is this article number of the Java technology river’s lake 】 【 one into the JavaWeb technology in the world, this part from the network, in order to put this article speaks with clarity theme, also integrates a lot I think good technology content, reference some good blog posts, if there are any copyright infringement, please contact the author.
This series of blog posts will show you how to learn the basics of JavaWeb from beginning to end, from servlets to frameworks, from SSM to SpringBoot, and get your feet wet. Then learn about the technologies and components commonly used in JavaWeb projects, including logging components, Maven, Junit, And so on, to give you a more complete understanding of the entire JavaWeb technology system, to form your own knowledge framework. In order to better summarize and test your learning results, this series of articles will also provide interview questions and reference answers for each point.
If you have any suggestions or questions about this series of articles, you can also contact the author on the public account “Java Technology Jianghu”. You are welcome to participate in the creation and revision of this series of blog posts.
At the end of this article, we will give you 8000G Learning materials for Java architects. If you need them, you can go to the end of this article to know how to get them. The materials include free learning materials for Java foundation, advanced Java, projects and architects, as well as popular technology learning videos such as database, distributed and micro-services. In addition, author’s original Java learning guide, Java programmer interview guide and other dry resources will be given as a gift.
// 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
Individual public number: programmer Huang Xiaoxi
Huang Xiaoxi, master of 985, is a Java engineer of Alibaba. She has rich experience and unique insights in self-learning programming, technical job hunting, Java learning and other aspects, hoping to help more programmers who want to engage in the Internet industry. The author focuses on the JAVA backend technology stack, and is keen to share the practical knowledge of programmers, learning experiences, job hunting tips, and self-taught programming and JAVA technology stack. 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!
Original e-book: Follow the wechat public number [programmer Huang Xiaoxi] and reply [Original e-book] to receive my original e-book “Novice Programmer Training Manual: From a technical novice to an Alibaba Java Engineer, this e-book summarizes my 2-year learning path of Java, including learning methods, technical summary, job hunting experience and interview skills, and has helped many programmers get the offer they want!
Programmer 3T technology learning resources: some programmers learning technology resources gift package, after paying attention to the public account, the background reply keyword “information” can be free of routine access, including Java, python, C++, big data, machine learning, front-end, mobile terminal and other directions of technical information.
Technical public number: Java technology arena
If you want to follow my updated articles and shared dry goods in real time, you can follow my wechat public number [Java technology Lake]
This is the technical station of an Ali Java engineer. Author Huang Xiaoxi, focus on Java related technology: SSM, SpringBoot, MySQL, distributed, middleware, cluster, Linux, network, multithreading, occasionally talk about Docker, ELK, but also share technical dry goods and learning experience, committed to Java full stack development!
Essential learning resources for Java engineers: follow the public account and reply “Java” to receive free learning materials such as Java foundation, advanced, project and architect, etc. There are also popular technology learning videos such as database, distributed and micro-service, with rich content and both principle and practice. In addition, the author’s original Java learning guide, Java programmer interview guide and other dry resources will be presented
