Hello, today I would like to share some common interview questions with you. Do you want to stand out in your job interview? Want to quickly master the core basic Knowledge of Java in the shortest time? Take out your notebook and write it down!

1. What is the difference between List, Set and Map?

List: An ordered container in which elements are placed in the same order as they are fetched. Elements can be repeated, multiple null elements can be inserted, and elements have indexes. Common implementation classes include ArrayList, LinkedList, and Vector Set: an unordered container that cannot store duplicate elements but only null elements, which must be unique. The common implementation classes of the Set interface are HashSet, LinkedHashSet, and TreeSet Map. Key unordered, unique; Value does not require order and allows repetition. Common implementation classes of Map include HashMap, TreeMap, HashTable, LinkedHashMap, and ConcurrentHashMap

2. Data structure underlying the collection framework

Arraylist and Vector use the Object array, LinkedList uses the two-way loop Set Set HashSet (unordered, unique) : TreeSet (ordered, unique) based on the HashMap implementation, where the value of the HashSet is the key, and the value is a constant of type Object LinkedHashSet that inherits the HashSet, and is implemented via LinkedHashMap: Red-black tree (self-balanced sorted binary tree) The HashMap set consists of an array + a linked list + a red-black tree. The array is the main body of the HashMap, and the linked list is mainly used to resolve hash conflicts. When the length of the list is greater than the threshold (8 by default) and the length of the array is greater than 64, LinkedHashMap (ordered) inherits from HashMap, and the bottom layer is still array + list + red-black tree. In addition, a bidirectional linked list is added between LinkedHashMap nodes on this basis, so that the insertion order of key-value pairs can be maintained. HashTable is unordered, composed of array + linked list, array is the main body of HashTable, and linked list is TreeMap order that exists mainly to solve hash conflicts. Red and black tree

3. Expansion of collection framework

The default initial capacity of ArrayList and Vector is 10. When the number of elements exceeds the initial capacity of ArrayList and Vector, the default initial capacity of ArrayList and Vector is 1.5 times that of Vector, while the default initial capacity of HashSet and HashMap is 16 and the loading factor is 0.75: That is, if the number of elements exceeds 0.75 times of the capacity length, expand the capacity by two times. HashTable: The default initial capacity is 11, the loading factor is 0.75, and the expansion policy is 2 times +1. For example, the initial capacity is 11, and after one expansion, the capacity is 23

4. How to implement HashMap and the difference between JDK1.7 and JDK1.8?

The characteristics of arrays are: easy to address, difficult to insert and delete; The characteristics of linked lists are: difficult to address, easy to insert and delete. We combine the characteristics of both to create a data structure hash table that is easy to address and easy to insert and delete. And use one of the most commonly used methods – zipper method to achieve hash table.

The element stored in an array is an Entry class that has three data fields: key, value (key-value pairs), and Next (pointing to the next Entry). When the index (index) calculated by two keys is the same, that is, hash conflict occurs, the chain address method is used to solve the hash conflict, that is, the next attribute is used to link together the indexes with the same value. As the size of the map or linked list grows, further optimizations are made, such as using red-black trees. The stored procedure HashMap has put() methods: the first step is to encapsulate k and v as nodes. The second step uses the hashCode() method to get the hash value and convert it to the index of the array. If there are no elements at the index position (no collisions), the Node Node is added to that position. Let’s say there’s a value at the location of the subscript. The value of the colliding element is the same as the key value of the element to be inserted. If the key values are different, then the list or tree grows. Determine whether to expand the capacity after the insertion. HashMap get() method: first call k’s hashCode() method to get the hash value and convert it to the array’s subscript. Step 2: Use array subscripts to quickly locate a location. If there is nothing at that location, null is returned. If there is data at this location, it equals the argument k and k of each node on the one-way linked list (red-black tree). If all equals methods return false, get returns null. If k equals true to one of the nodes, then the value of that node is returned. Difference JDK1.7 is array + linked list, no collision, store array; In case of conflict, store the linked list; Head insertion method is used. JDK1.8 is an array + linked list + red-black tree. If the length of the linked list is greater than the threshold (8 by default) and the length of the array is greater than 64, the linked list will be converted to a red black tree. When the tree element is less than or equal to 6, the tree structure is reduced to a linked list.

5. How does HashMap resolve hash conflicts?

Using linked addresses (linked lists) to link data with the same hash value; The quadratic perturbation function (hash function) is used to reduce the probability of hash conflict and make the data distribution more even. Red black tree is introduced to reduce the time complexity of traversal and make traversal faster. Interpretation of disturbance function: If only hashCode mod is used, then only the low part of hashCode will participate in the operation, and the high part will not play any role. Therefore, our idea is to let the high part of hashCode (xor with itself moved 16 bits to the right) also participate in the operation to obtain the hash value and further reduce the probability of hash collision. This makes the distribution of data more even, and we call this operation perturbation.

6. Why must both the default length and the expanded length be powers of 2

The array index is obtained by subtracting the hash value of the key from the length of the array by one bit and. When the length is a power of 2, the binary bits of the value subtracted by one must all be 1. In this way, the index of the array depends entirely on the last few bits of the hash value of the key, as long as the hash values of the key are evenly distributed. Nodes in a HashMap are as uniform as possible, so collisions between different hash values are less likely when the length is a power of 2.

7. Data migration mechanism of HashMap

Since the array is expanded by a power of two, the new location is either the original location or the original length + the original location. Since the array is twice as long, the hash value represented as the key has an extra bit of binary input to the array subscript. At this point, after an element is calculated using the hash coordinate conversion method, one phenomenon happens: if the highest bit is 0, the coordinate remains unchanged; if the highest bit is 1, the coordinate changes to “original length + original coordinate”. Therefore, when we extend the HashMap, we don’t need to recalculate the hash as we did in JDK1.7, just to see if the new bit is 1 or 0. For example, if HashMap is 16 before expansion, the binary value of Leng-1 is 01111. Similarly, the array length after expansion is 32, and the binary value of Leng-1 is 011111. We can see that after the expansion, there is only one bit difference, that is, the left-most 1 is added. So when passing h&(Length-1), as long as the left-most difference bit corresponding to H is 0, it will be in the original position. ConcurrentHashMap in JDK1.7, ConcurrentHashMap consists of the Segment array structure and the HashEntry array structure. Segment inherits a ReentrantLock and is a ReentrantLock. HashEntry is used to store key-value pair data. A ConcurrentHashMap contains an array of segments, and a Segment contains an array of Hashentries. Each HashEntry is an element of a linked list. Thus, the ConcurrentHashMap of JDK1.7 is an array + linked list structure. When modifying the data in a HashEntry array, we must first acquire the Segment lock corresponding to it. Thus, as long as each Segment is thread-safe, we achieve global thread-safety

8. ConcurrentHashMap low-level implementation

In JDK1.8, Node + CAS + Synchronized is used to ensure concurrency security. Synchronized only locks the first Node of the current linked list or red-black binary tree. If the Node is not initialized, CAS is called to insert the corresponding data. If the corresponding Node position is not empty, if the Node’s first.hash! =-1, add synchronized lock to the node, update the node or insert a new node; If first.hash of the node is -1, the system expands the capacity. Reads are unlocked, val and next on nodes are volatile, and arrays are volatile.

Well, that’s all for today’s article, and I hope I can help you on the screen!