1. Do you know HashMap?

A: HashMap uses an array of entries to store key-values. Each key-value pair forms an Entry entity (JDK1.7, JDK1.8 changed to Node). An Entry class is actually a one-way linked list structure with a next pointer to connect to the next Entry entity. In JDK1.8, if the list length is greater than 8, the list will turn into a red-black tree! HashMap is thread safe, and Hashtable is thread safe. A HashMap can accept null keys and values, but a Hashtable cannot: HashMap is not thread safe. In a multi-threaded environment, using HashMap for put operations will cause an infinite loop, resulting in CPU utilization approaching 100%. Therefore, HashMap cannot be used in concurrent situations. All operations associated with get/ PUT are synchronized, which is equivalent to adding one lock to the entire hash table. When multiple threads access the object, as long as one thread accesses or operates on the object, the other threads can only block. This is equivalent to serializing all operations, which leads to poor performance in competitive concurrent scenariosCopy the code

**2. Can you describe the whole process of its put method? 阿鲁纳恰尔邦

A: The general process: 2. If the array index is empty, encapsulate it into an enty object (1.7 is called an entry object, 1.8 is called a node object) and place it in that position. 3. If the array index is not empty, discuss a. If the value is 1.7, check whether expansion is required. If expansion is required, expand the capacity. If expansion is not required, generate an entry object and insert it into b in the current linked list. If it is 1.8, first determine whether the Node type of the current position is a linked list or a red-black tree I: If it is a red-black tree Node, then encapsulate key and value into a red-black tree Node and add it to the red-black tree. During this process, it will determine whether there is a key value, and update Value II if there is: If the Node object on this object is a linked list Node, then key and value are encapsulated into a list Node and added to the last position of the list through tail interpolation. Because of tail interpolation, it is necessary to traverse the list. In the process of traversing the list, judge whether there is a key, and update value if there is. After traversing the list, insert the new Node into the list. After inserting into the list, the number of nodes in the current list will be seen. If the number is greater than or equal to 8, the list will be transformed into a red-black tree III: After encapsulating key and value as nodes and inserting them into a linked list or red-black tree, it determines whether to expand the capacity. If so, expand the capacity. If not, it calls the hash function of the object to obtain the hash value corresponding to the key, and then calculates its array subscript. If there is no hash conflict, it is put into the array. If there is a hash conflict, it is put behind the list as a linked list. If the list length exceeds the THRESHOLD (TREEIFY THRESHOLD==8), the list is turned into a red-black tree. When the length of the list is less than 6, the red-black tree is transferred back to the list; If the key of the node already exists, replace the value; If the number of key-value pairs in the collection is greater than 12, the resize method is called to expand the array. The get method calls equals () through the chain object, and the put method calls hashCode to calculate the hashcode. After calculating the hashcode, the address is found to store the entry objectCopy the code

3. Why is HashMap thread unsafe

A: When two threads A and B perform the PUT operation at the same time, B calculates the hash index value first and inserts the data. As a happens, THE hash index value calculated by A is the same as that calculated by B. In this case, A overwrites the data of B, resulting in a thread safety problem and an infinite loop caused by resize. Two threads at the same time to modify a list structure will produce a circular list, the next get, will appear according to the source code with their own understanding, step by step to say it is goodCopy the code

4. How does it expand? Let’s talk about the expansion mechanism

A: The default capacity is 16 and loadfactor is 0.75f. After threshold = Capacity * loadfactor, the value is doubled. Then I rehash, recalculate the indices. Based on the rehash results, the low - and high-rank linked lists are rehashCopy the code

5. How is the code implemented?

Answer: shift one bit to the left of the original size by bit operationCopy the code

**6. Why should the expansion be a power of 2? * * 2.

A: Because of the and operation, the efficiency of hash value calculation is improved. Because the algorithm of finding the corresponding bucket in HashMap uses the and operation instead of the traditional modulus operation hash % length == hash&(length-1). The premise is that length is a power of 2. In order to ensure that the new array index is consistent with the old array index, the initial capacity of HashMap is 2 to the NTH power, and the expansion is also carried out in the form of 2 times. Because the capacity is 2 to the NTH power, the added elements can be evenly distributed on the array of HashMap, reducing hash collisions and avoiding forming a linked list structure. 2. In the case of rehash, the relationship between hash % length == hash & (length - 1) is only valid when length is equal to the power of two. Bit operation can be much more efficient than %Copy the code

7. What is the search time complexity of red-black trees?

A: O (logN)Copy the code

8. Do you know CocurrentHashMap?

A: ConcurrentHashMap is designed to deal with the insecurity of hashMap in the concurrent environment. It uses volatile, final and other lock-free technologies to reduce the impact of lock competition on performance. ConcurrentHashMap uses segmented locking technology to divide data into segments for storage. Then each piece of data is configured with a lock. When a thread uses the lock to access one piece of data, the other pieces of data can also be accessed by other threads. To achieve true concurrent access, ConcurrentHashMap requires two Hash operations to locate an element. Jdk1.7: array + linked list + Segment Segment lock jdk1.8: array + linked list + Segment Segment lock (CAS = compare Short for and swap, what we call comparative exchange. Cas is a lock-based operation, and it is optimistic locking.Copy the code

9. Can we use CocurrentHashMap instead of Hashtable?

A: We know that Hashtable is synchronized, but ConcurrentHashMap synchronization performs better because it locks only a portion of the map based on the synchronization level. ConcurrentHashMap can, of course, replace HashTable, but HashTable provides greater thread-safetyCopy the code