1: The data structure of HashMap?
A: Hash table structure (linked list hash: array + linked list) implementation, combining the advantages of array and linked list. When the list length exceeds 8, the list is converted to a red-black tree.
transient Node<K,V>\[\] table;
Copy the code2: How does HashMap work?
The underlying HashMap is a hash array and a one-way linked list. Each element in the array is a linked list, which is implemented by Node internal classes (which implement the Map.Entry interface). A HashMap is stored and retrieved using put & get methods.
To store an object, pass the K/V key to the put() method:
(1) Call the hash(K) method to calculate the hash value of K, and then calculate the array subscript based on the array length;
Adjust the array size (when the number of elements in the container is greater than capacity * loadfactor, the container will be expanded to 2N).
I. If the hash value of K does not exist in the HashMap, insert it; if it does, a collision occurs;
Ii. update the key-value pair if K’s hash value exists in the HashMap and their equals returns true;
Iii. If K’s hash value exists in the HashMap, and their equals returns false, then insert into the end of the list (tail interpolation) or into a red-black tree (tree addition).
When a collision causes the list to be larger than TREEIFY_THRESHOLD = 8, convert the list to a red-black tree.
To get an object, pass K to the get() method: (1) Call the hash(K) method to get the array index of the list where the key value is; Equals () = V (K) = V (K)
HashCode is located, stored somewhere; Equals is qualitative, comparing whether two things are equal.
3. What happens when two objects have the same hashCode?
Since hashCode is the same, not necessarily equal (equals method comparison), the array subscripts of the two objects are the same, and a “collision” occurs. Since HashMap uses a linked list to store objects, this Node will be stored in the list.
4. Do you know the implementation of Hash? Why is it implemented this way?
In JDK 1.8, this is done with the high or low 16 bits of hashCode() : (h = k.hashcode ()) ^ (h >>> 16), mainly from the speed, efficiency and quality of consideration, reduce the overhead of the system, will not cause because the high level does not participate in the calculation of subscript, thus causing collisions.
5. Why use xOR operators?
Guarantees that the entire hash() return value will change if one bit of the object’s hashCode 32-bit value changes. Minimize collisions as much as possible.
6. How to determine the capacity of the HashMap table? What is loadFactor? How does this capacity change? What problems will this change bring?
Table array size is determined by capacity. The default value is 16, and the maximum value can be 1<<30.
The default value is 0.75. For example, when the table array size is 16 and the loadFactor is 0.75, the threshold is 12. When the actual size of the table exceeds 12, Table needs to be dynamically expanded;
③ Call resize() to double the size of the table (note that this is the table length, not threshold)
(4) If the data is very large, scaling will cause a performance penalty, which can be fatal where performance requirements are high.
7. Put method in HashMap?
A: “Call the hash function to get the hash value of the Key and compute its array index;
If there are no hash conflicts, it goes directly to the array; If a hash conflict occurs, it is placed after the list as a linked list.
If the list length exceeds the TREEIFY THRESHOLD (TREEIFY THRESHOLD==8), the list is converted to a red-black tree; if the list length is below 6, the red-black tree is converted back to the list.
If the key of a node already exists, replace its value.
If the set has a key-value pair greater than 12, call resize to expand the array.
8. Array expansion process?
Create a new array with twice the size of the old one and recalculate where the nodes in the old array are stored. There are only two positions of the node in the new array, the original subscript position or the original subscript + the size of the old array.
9. Why not use binary search tree instead of red black tree to solve the problem of too deep list caused by zipper method? Why not always use red black trees?
The red-black tree was chosen to solve the problem of binary lookup trees, which in special cases can become a linear structure (as with the original linked list structure, causing deep problems), and traversal lookup can be very slow. I turned green when asked about the red-black tree.
And red and black tree after inserting new data may need to be by a left-handed, right-handed, color changing these operations to maintain a balance, the introduction of a red-black tree is to find data quickly, solve the problems of the chain table query depth, we know that the red-black tree to balanced binary tree, but in order to maintain the “balance” is the need to pay the price, but the price is the depletion of the resources less than traverse linear list, So when the length is greater than 8, we use a red-black tree, but if the list length is very short, we don’t need to introduce a red-black tree at all, it will be slow.
10. What do you think of red black trees?
- Each node is either red or black
- The root node is always black
- If a node is red, its children must be black (not necessarily vice versa)
- Every leaf node is a black NIL node
- Each path from root node to leaf node or empty child node must contain the same number of black nodes (that is, the same black height)
11. What changes have been made to HashMap in JDK8?
In Java 1.8, if the length of a list exceeds 8, the list is converted to a red-black tree. (The number of buckets must be greater than 64. If the number of buckets is smaller than 64, the buckets will only be expanded.)
When a hash collision occurs, Java 1.7 inserts at the head of the list, while Java 1.8 inserts at the tail
In Java 1.8, Entry is replaced by Node (with a vest).
12. What is the difference between HashMap, LinkedHashMap, and TreeMap?
The LinkedHashMap holds the insertion order of the records. In Iterator traversal, the first records retrieved must be inserted first. Traversal is slower than HashMap;
TreeMap implements the SortMap interface to sort the records it stores by key (the default key value is sorted in ascending order, and you can specify a comparator for sorting)
13. How to use HashMap & TreeMap & LinkedHashMap?
In general, the most used is a HashMap.
HashMap: When inserting, deleting, and positioning elements in a Map;
TreeMap: in cases where keys need to be traversed in natural or custom order;
LinkedHashMap: In the case where the order of output is required is the same as the order of input.
14. What is the difference between HashMap and HashTable?
HashMap is thread-safe, HashTable is thread-safe.
(2) HashTable is not as efficient as HashMap because it is thread safe;
(3) HashMap allows only one record to be null, and HashTable does not allow multiple records to be NULL.
(4) The default array size of HashMap is 16, and the default array size of HashTable is 11.
(5) A HashMap recalculates the hash value, whereas a HashTable uses the object’s hashCode directly
15. What is another thread-safe class in Java that is very similar to HashMap? Also thread-safe, how does it differ from HashTable in thread synchronization?
ConcurrentHashMap class (a thread-safe and efficient implementation of HashMap provided in Java and distributed in java.util.concurrent).
HashTable uses the synchronize keyword to lock an object.
For ConcurrentHashMap, segmented locking is used in JDK 1.7. JDK 1.8 uses CAS + synchronized directly.
16. The difference between HashMap and ConcurrentHashMap?
There is not much difference in principle except for locking. In addition, a HashMap allows NULL key-value pairs, but ConCurrentHashMap does not.
17. Why is ConcurrentHashMap more efficient than HashTable?
A HashTable uses a single lock to handle concurrency. Multiple threads compete for a lock and block easily.
ConcurrentHashMap
- JDK 1.7 uses ReentrantLock + Segment + HashEntry, which is equivalent to dividing a HashMap into segments and assigning one lock to each Segment, to support multithreaded access. Lock granularity: Based on Segment and contains multiple Hashentries.
- JDK 1.8 uses CAS + synchronized + Node + red-black tree. Lock granularity: Node (the first Node) (implementing Map.Entry). Lock granularity has been reduced.
The ConcurrentHashMap lock mechanism (JDK 1.7 VS JDK 1.8)
In JDK 1.7, the mechanism of Segment locking is adopted to realize concurrent update operations. The underlying storage structure of array + linked list is adopted, including two core static internal classes Segment and HashEntry.
The Segment inherits a ReentrantLock that acts as a lock. Each Segment object guards buckets in each hash map.
(2) HashEntry is used to encapsulate key-value pairs of the mapping table;
③ Each bucket is a linked list of HashEntry objects
In JDK 1.8, Node + CAS + Synchronized is used to ensure concurrency security. Delete class Segment, use table array to store key-value pairs. When the length of a HashEntry list exceeds TREEIFY_THRESHOLD, the list is converted to a red-black tree to improve performance. The bottom layer changes to array + linked list + red-black tree.
In JDK 1.8, why use synchronized instead of ReentrantLock?
(1) The particle size is reduced;
(2) The JVM development team did not give up synchronized, and synchronized optimization based on JVM has more space and is more natural.
(3) ApI-based ReentrantLock can consume more memory for the JVM’s memory stress due to a large number of data operations.
20.ConcurrentHashMap
①, important constants:
private transient volatile int sizeCtl;
If the value is negative, -1 indicates that initialization is underway, and -n indicates that N-1 threads are expanding.
When the value is 0, the table is not initialized.
If the value is another positive value, it indicates the initial size or the next capacity expansion size.
② Data structure:
Node is the basic unit of storage structure, inheriting Entry from HashMap, used to store data.
TreeNode inherits Node, but its data structure is changed into a binary tree structure, which is used to store data in a red-black tree.
The TreeBin is a container that encapsulates the TreeNode and provides control over conditions and locks for converting red-black trees.
Put (); put();
If not, the initTable() method is called to initialize it;
If there is no hash conflict, CAS is inserted without lock.
If you need to expand capacity, expand capacity first.
If there is hash conflict, lock is added to ensure thread safety. There are two situations: one is to iterate to the end of the linked list and insert, and the other is to insert according to the red-black tree structure.
If the list is larger than the threshold of 8, it is converted to a red-black tree structure and break enters the loop again
If the addition succeeds, the addCount() method is called to count the size and check whether it needs to be expanded.
Transfer () : The default capacity is 16. During expansion, the capacity becomes two times of the original capacity.
HelpTransfer () : It is more efficient to call multiple worker threads to help with capacity expansion.
Get ();
Calculate hash value, locate the index position of the table, return if the first node matches;
If expansion occurs, the forwardingNode.find () method is called to mark the node being expanded, and the node is searched.
If none of the above is true, the node is traversed and returns if it matches, otherwise null is returned.
21. What is the concurrency of ConcurrentHashMap?
The maximum number of threads that can simultaneously update ConccurentHashMap without lock contention. The default is 16 and can be set in the constructor.
When the user sets the concurrency, ConcurrentHashMap uses a minimum power of 2 greater than or equal to the value as the actual concurrency (if the user sets the concurrency to 17, the actual concurrency is 32).
[HashMap_ – _ -] [HashMap_ – _ -] [HashMap_ – _ -] [HashMap_ – _ -] [HashMap_ – _ –
Concern public number: Java baodian
