51. Implementation principle of HashMap

The backbone of a HashMap is an array of entries. Entry is the basic unit of a HashMap, and each Entry contains a key-value pair. HashMap is based on hashing, where we store and retrieve objects using the put() and get() methods. When we pass the key-value pair to the put() method, it calls the key object's hashCode() method to compute the hashCode, and then finds the bucket location to store the value object. When an object is retrieved, the correct key-value pair is found through the equals() method of the key object, and the value object is returned. A HashMap uses a linked list to solve collisions, and when a collision occurs, the object is stored in the next node in the list. HashMap stores key-value pair objects in each linked list node. What happens when two different key objects have the same Hashcode? They are stored in a linked list at the same bucket location. The equals() method of key objects is used to find key-value pairs. Because of the benefits of HashMap, I have used HashMap as a cache in e-commerce applications. Because Java is heavily used in finance, and for performance reasons, we often use HashMap and ConcurrentHashMap. HashMap is composed of array + linked list. Array is the main body of HashMap, while linked list exists mainly to solve hash conflicts. If the array position located to does not contain the next of the current entry of the linked list points to NULL, then search, add and other operations are very fast, and only need one address. If the array to be located contains a linked list, the time complexity of the add operation is O(n), and the linked list is first traversed. If it exists, it will be overwritten; otherwise, it will be added. For lookups, you still need to traverse the linked list and then compare lookups one by one through the Equals method of the key object. Therefore, for performance purposes, the fewer linked lists in a HashMap, the better the performance.Copy the code

52. Differences between List, Set and Map

List and Set are subinterfaces that implement Collection interface. Map is another collection interface. 1 Element repeatability: The List allows repeating elements. Any number of duplicate elements can be inserted into the List collection without affecting the values and indexes of existing duplicate elements; The Set does not allow elements to be duplicated. Set and all classes that implement the Set interface do not allow the insertion of duplicate values. If the same element is inserted more than once, only one element is displayed in the Set. A Map stores elements as key-value pairs. Map does not allow duplicate keys, but does allow duplicate values for different keys. 2. Element ordering: List and all of its implementation classes maintain the insertion order of each element; The elements in a Set are unordered; But some implementation classes of a Set sort the elements in a special way. For example, LinkedHashSet sorts the elements in the order they were inserted. Map stores elements unordered like Set, but some of its implementation classes sort the elements. For example, TreeMap sorts the elements in ascending order by key. 1.List allows any number of null values; 2.Set allows at most one null value. When multiple NULL values are added to a Set, only one NULL element is displayed in the Set. 3.Map allows only one empty key, but any number of null values. -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- summary: the elements in the List: orderly and repeatable, can is empty; Elements in a Set: unordered, non-repetitive, with only one empty element; Elements in Map: unordered, key not heavy, value repeatable, can have one empty key, can have many empty values;Copy the code

53. Why is the length of a HashMap a power of 2

If the length of the current Entry array is len, we need to hash the key's hashcode twice when inserting the node. Then we need to hash the key's hashcode with Len-1 to ensure that the value is less than len. If len is 2 to the power of N, So the last N bits of len-1 must be all ones. Suppose there are two keys, and they have different hashcodes, code1 and code2, and code1 and code2 will have different results, but, If code1 and code2 are matched with a binary with the last N bits not all ones, the result may be the same. That is, if len is 2^N, the array subscripts computed by different hashCodes must be different. Otherwise, the keys of different Hashcodes must compute the same array index. Therefore, the length of HashMap is all 1, which can reduce the probability of hash conflict. -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- 2. Improve the efficiency of computing the subscript If len when n bits of binary 1, facies and len - 1, 0 and 1 phase need to invert. If the last n bits of len are all ones, you don't need to invert them at all. If len is 2 to the N, then len minus 1 is the same thing as mod len, which is more efficient than mod len. If len is not 2 to the N, that's the same thing as len minus 1, that's not the same thing as mod len.Copy the code

54. What are the advantages of generics in the collection framework?

First, take a look at Java's concept of generics. Generics, known as templates in C++, are an abstract way of programming. When we define classes and methods, we can define them in a general way, rather than writing out specific classes. These unknowns will be determined when they are actually used. For collection classes, they can hold various types of elements. If you can determine the type of an element before storing it, it's much more intuitive and makes the code much cleaner. Note: Java generics are compile-level, which means that the JVM still treats generic data as Object, but the JVM automatically helps us to convert them when we use them. Conclusion: The use of generics in collections enables explicit element types, avoids manual conversion, and allows us to be more specific about what type of data the container holds.Copy the code

55. Can we use any class as the Map key?

1. Yes, but the data as key has the following requirements: 2. First of all, Map sets store data for lookup. List sets store data for output. Map sets store data for lookup. At least overriding equals() is simple: A self-defined class must override equals() if it wants to compare objects, or it must override equals() if it wants to compare objects. 6, according to the standard development, you will feel twice the result with half the effort, do not have nothing to find trouble for themselves, of course, the spirit of learning is worth affirmation.Copy the code

56. What are the different collection views provided by the Map interface?

The Map interface provides three Set views: 1.Set KeySET () : Returns a Set view of all keys contained in the Map. Collections are supported by maps, and changes to maps are reflected in collections and vice versa. When an iterator is iterating over a collection, the result of the iterator becomes undefined if the map is modified (except for the iterator's own removal operation). Remove, set. Remove, removeAll, retainAll, and clear Iterator operations to Remove elements from the map. It does not support add and addAll operations. 2.Collection Values () : Returns a Collection view of all the values contained in a map. This collection is supported by a map, and changes to the map are reflected in the collection and vice versa. When an iterator is iterating over a collection, if the map is modified (except for the iterator's own removal operation), the result of the iterator becomes undefined. Remove, set. Remove, removeAll, retainAll, and clear Iterator operations to Remove elements from the map. It does not support add and addAll operations. 3.Set> entrySet() : Returns a Set view of all mappings contained in a map clock. This collection is supported by map, and changes to the map are reflected in the Collection and vice versa. When an iterator iterates over a collection, the result of the iterator becomes undefined if the map is modified except for removing the iterator itself and setValue on the entry returned by the iterator. Remove, set. Remove, removeAll, retainAll, and clear Iterator operations to Remove elements from the map. It does not support add and addAll operations.Copy the code

57. Which collection classes are thread-safe?

In the collections framework, there are classes that are thread-safe, which are emerging in jdk1.1. Since jdk1.2, there have been many, many non-thread-safe classes. Here are the classes for thread-safe synchronization: Vector: has one more synchronization mechanism than ArrayList (thread-safe), which is less efficient and less recommended today. In Web applications, especially foreground pages, efficiency (page response speed) is often a priority. Statck stack class, hashtable, hashtable, hashtable, hashtable, hashtable, hashtable, hashtable, hashtable, hashtable, hashtable, hashtable, hashtable. Thread-safe classes have synchronized methods that can only be accessed one at a time. It is a heavyweight object and is less efficient.Copy the code

58. What are queues and stacks? List the differences?

A Queue is a linear list that can only be inserted at one end and deleted at the other. Stack: A linear table that limits insertion and deletion operations to one end of the table. 1. Queue: First In First Out (FIFO) 2. Stack: First In Last Out FILO 2, different restrictions on insert and delete operations 1. Queue: Can only be inserted at one end of the table, and deleted at the other end of the table; 2. Stack: Insert and delete only at one end of the table. 1. Queue: traversal is based on address pointer, and traversal can be carried out from the head or tail, but not at the same time. There is no need to open up space, because the data structure is not affected in the traversal process, so the traversal speed is fast; 2. Stack: Data can only be fetched from the top, that is to say, the data that enters the bottom of the stack first needs to be traversed through the whole stack before being retrieved. In addition, temporary space should be created for data while traversing data to maintain the consistency of data before traversing.Copy the code

59. Which List implements the fastest insertion?

LinkedList and ArrayList are implementations of a different list of variables. The advantage of an ArrayList is that it is a dynamically growing array, perfect for situations where the initial total length is unknown. The advantage of LinkedList is that inserts and deletions are fastest in the middle. LinkedList implements the List interface, allowing null elements. Additionally LinkedList provides additional get, remove, and INSERT methods at the beginning or end of LinkedList. These operations enable the LinkedList to be used as a stack, queue, or deque. ArrayList implements variable-size arrays. It allows all elements, including NULL. Each ArrayList instance has a Capacity, which is the size of the array used to store elements. This capacity can be automatically increased as new elements are added, but the growth algorithm is not defined. When a large number of elements need to be inserted, the ensureCapacity method can be called to increase the capacity of the ArrayList before insertion to improve insert efficiency.Copy the code

60. When to use ConcurrentHashMap?

Fail fast Java iterator may cause ConcurrentModifcationException iteration in the underlying collection is modified. Fail-safe iteration as a copy occurring in an instance does not throw any exceptions. The fail-safe paradigm of fast failure defines how the system responds when a failure is encountered. For example, ArrayList, a fast iterator for failure, and ConcurrentHashMap, an iterator for fail-safe. ConcurrentHashMap is used as an instance of a fail-safe iterator that allows full concurrent retrieval and updates. ConcurrentHashMap can be used when there are a large number of concurrent updates. This is very similar to Hashtable, but ConcurrentHashMap does not lock the entire table to provide concurrency, so ConcurrentHashMap seems to perform better at this point. So ConcurrentHashMap should be used when there are lots of updates.Copy the code