background

On the one hand, the original intention of writing the blog is to record some of my previous interview experience and common questions, to review the previous knowledge, more systematic learning, and also want to exchange learning experience with everyone

1. Architecture of collections

The diagram above shows the inheritance and implementation relationships of some common tools, and many derived classes are also inherited or implemented on this basis.

The Java collection consists primarily of the following interfaces

1. Collection: The Collection interface is the parent of sets, lists, and queues. The main implementation classes are ArrayList, LinkedList, HashSet, etc
2. Map: is the basic interface of a mapping table. The main implementation classes are HashMap, Hashtable, TreeMap, etc
3. Iterator: Iterator interface. Iterators are used to traverse the data in a collection

The following is a detailed description of these three key interfaces

2. Collection system

2.1 the List system

2.1.1 List Common implementation classes

The main implementation classes are ArrayList, LinkedList, Vector, Stack, etc. ArrayList and LinkedList are thread-unsafe collection classes, and the bottom-layer methods of Vector and Stack add the keyword Synchronize to ensure thread-safe. The underlying LinkedList is a two-way LinkedList structure to store data

ArrayList, Vector, and Stack all use object arrays to store data

2.1.2 What are the differences between ArrayList and LinkedList

The characteristics of the ArrayList

1. ArrayList implements List, RandomAccess, Cloneable, java.io.Serializable interfaces.
2. ArrayList is an array data structure that supports random access, continuous memory, and an initial size of 10.
3. Before adding elements to the container, the capacity and subscript are checked. When the capacity exceeds the original capacity, it is expanded by 1.5 times and the data is copied to the new array.
4. If the inserted element is not at the end of the array, the data after the inserted element is moved to the right. If the element is not at the end of the array, it needs to be moved to the left, and the element at the end is empty. The garbage collector will reclaim the memory

When it comes to scaling, there are a few steps to the scaling mechanism of ArrayList

1. Call ensureCapacityInternal to determine the minimum extension capacity

2. Expansion is triggered when the minimum expansion capacity is less than the actual element capacity

---

The characteristics of the LinkedList

1. Linked implements List, Deque, Cloneable, Java.io.Serializable interfaces
2. LinkedList uses a Node data structure with two Pointers before and after the LinkedList. Compared with array, linked list insertion efficiency is higher, only need to change the front and back two Pointers; In addition, linked lists do not have the problem of capacity expansion, because linked lists do not require continuous storage space, each insertion of data only changes the last pointer; In addition, linked lists require more memory than arrays because they maintain two Pointers; It is suitable for deleting, inserting more scenarios. In addition, LinkedList implements the Deque interface.

---

Common features of ArrayList and LinkedList

1. FailFast mechanism: many not thread-safe collection classes in an iterator and a for loop has the mechanism, if one thread in a container, iteration to modify a container will lead to another thread modCount inconsistencies, thus throw ConcurrentModificationException “exception
2. Scaling, neither of which actively triggers scaling, but instead empties the element for garbage collection when it is deleted

---

2.2 the Set system

2.2.1 Common implementation classes of Set and their implementation principles

Set common implementation class HashSet

The main implementation of a set is shown in the figure above. At the bottom, a HashMap is used to store data. Adding elements to a set is actually adding elements to a HashMap

2.3 the Queue system

2.3.1 Common implementation classes of Queue

Common implementation classes of Queue include PriorityQueue, LinkedList, etc

The characteristics of PriorityQueue

The underlying priority queue also uses an array of objects to hold elements

The mechanism of capacity expansion is graded capacity expansion

In addition, the underlying PriorityQueue uses the data structure of the heap to achieve

        ArrayList<Integer> list = new ArrayList<>();
        PriorityQueue<Integer> priorityQueue = new PriorityQueue(11);
        priorityQueue.add(36);
        priorityQueue.add(10);
        priorityQueue.add(12);
        priorityQueue.add(89);
        priorityQueue.add(56);
        priorityQueue.add(27);
        priorityQueue.add(43);
        priorityQueue.add(38);
        priorityQueue.add(98);
        priorityQueue.add(73);
        priorityQueue.add(37);
        Iterator<Integer> iterator = priorityQueue.iterator();
        while (iterator.hasNext()) {
            System.out.println(priorityQueue);
            System.out.println(priorityQueue.poll());
        }
Copy the code

Output result [10.36.12.38.37.27.43.89.98.73.56]
10 
[12.36.27.38.37.56.43.89.98.73]
12 
[27.36.43.38.37.56.73.89.98]
27 
[36.37.43.38.98.56.73.89]
36 
[37.38.43.89.98.56.73]
37 
[38.73.43.89.98.56]
38 
[43.73.56.89.98]
43 
[56.73.98.89]
56 
[73.89.98]
73 
[89.98]
89 
[98]
98 
Copy the code

It can be seen from the above that the sorting inside the array is not orderly, but the header element is always the smallest in each poll. Of course, this is also related to the compareTo method

Heap of introduction can look at other blogs, online here but more redundancy www.cnblogs.com/chengxiao/p…

3. Map system

3.1 the Map system

3.1.1 Map Common implementation classes

The main implementation classes include HashMap, TreeMap and other implementation classes.

3.1.2 Features of HashMap and differences between JDK 1.7 and 1.8

The initial capacity is 16, the maximum capacity is 2^30, the default load factor is 0.75, the list tree capacity is 8, the red black tree non-tree capacity is 6, and the tree minimum capacity is 64 (i.e., the total capacity is greater than 64 and the list tree capacity is 8).

Differences between HashMap1.7 and 1.8

Put method parsing

1. To determine whether the capacity is empty, the HashMap takes the form of lazy loading. The capacity is initialized only on the first PUT

   

2. The hash method is called to compute the array subscript, and a new object is created if the element does not exist in the array

   

   A. The hash method obtains the hashCode of the key and moves the hashCode unsigned 16 bits to the right to perform xOR with the original hashCode. If you do not do this, the high hash value of (n-1) &hash will be almost zero when the capacity is small, increasing the probability of hash collisions. This operation can mix the high level features into the low level, reducing the probability of Hash collisions

   This is the hash function for version 1.8

   static final int hash(Object key) {
        int h;
        return (key == null)?0 : (h = key.hashCode()) ^ (h >>> 16);
   }
   Copy the code

   This is the hash function for version 1.7

   static int hash(int h) {
        h ^= (h >>> 20) ^ (h >>> 12);
        return h ^ (h >>> 7) ^ (h >>> 4);
    }
   Copy the code

   Compared with 1.8, a large number of disturbance operations are reduced and xOR of high and low positions are adopted to reduce collision probability

3. Otherwise, if there is a value

   A. Determine whether the first element is the same as it and replace it if so

   

   B. If no, check whether the node is a red-black book node. If yes, insert the node into the red-black tree

   

   C. If not, traverse the list and insert data into the end of the list

   

   If the tree threshold is reached, red-black tree conversion will be carried outCopy the code

   D. Check whether capacity expansion is required. Then call the resize method

Resize method parsing

1. Check whether the array capacity reaches the maximum threshold
2. If it does not reach the maximum value, expand the capacity by 2 times
3. If it is not already initialized, set some initialized capacity
4. Scaling requires copying the old data to the new storage location

    int oldCap = (oldTab == null)?0 : oldTab.length;
    int oldThr = threshold;
    int newCap, newThr = 0;
    if (oldCap > 0) {
        // If it exceeds the maximum value, it will no longer be expanded
        if (oldCap >= MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return oldTab;
        }
        // If the value is not higher than the maximum value, the value is doubled
        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY)
            newThr = oldThr << 1; // double threshold
    }
    else if (oldThr > 0) // initial capacity was placed in threshold
        newCap = oldThr;
    else {
        // signifies using defaults
        newCap = DEFAULT_INITIAL_CAPACITY;
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
    }
    // Calculate the new resize upper limit
    if (newThr == 0) {
        float ft = (float)newCap * loadFactor;
        newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ? (int)ft : Integer.MAX_VALUE);
    }
Copy the code