Q0: How does HashMap locate subscripts? A: Get the Key, hash the Key, get A hash value, and then use the hash value to mod the capacity of the HashMap (not actually mod, but bitwise and, see Q6 for reasons), and finally get the subscript.
Q1: What does a HashMap consist of? When the number of linked list nodes exceeds 8 (m default value), we start to use red black tree. Using red black tree is an optimal choice. Compared with other data structures, red black tree has higher query and insert efficiency. When the number of nodes in a red-black tree is less than 6 (the default value), the linked list is used again. Why are these two thresholds different? Mainly in order to prevent frequent nodes in the same numerical switching back and forth, an extreme example, singly linked list of nodes is 9 now, started to become red and black tree, then the red-black tree nodes into 8, will again become a singly linked list, then nodes into 9, will again become a red-black tree, it consumes waste, So simply stagger the two thresholds so that it’s “not so easy” to go back to a single-linked list after becoming a red-black tree, and it’s also “not so easy” to go back to a red-black tree.
Q2: Why doesn’t a Java HashMap store data in residuals? A: In fact, the indexFor method of A HashMap uses bitwise summing with the capacity -1 of the HashMap, not %. (There is a hard requirement here, the capacity must be an exponential of 2, for the reason of Q6)
Q3: How does a HashMap insert a node into a list? A: In jdK1.7, there is A header interpolation method, in jdK1.8, there is A tail interpolation method, in jdK1.7, there is A tail interpolation method, in jdK1.8, there is A tail interpolation method, in jdK1.7, there is A head interpolation method, in JDK1.8, there is A tail interpolation method. It is also because of the tail insertion method that the HashMap can determine whether there are duplicate nodes when inserting nodes.
Q4: What is the default capacity and load factor size for HashMap? A: Before JDK1.7, the default capacity was 16 and the load factor was 0.75.
Q5: What is the actual size of a HashMap if you specify a capacity size of 10 when it is initialized? A: 16, since the initialization function of HashMap specifies that the capacity is an exponential multiple of 2, namely, 2, 4, 8, 16, so when the specified capacity is 10, the actual capacity is 16.
Q6: Why is the capacity exponential of 2? A: There are two reasons: 1, to improve computing efficiency: because exponential times of 2 have only one binary, and exponential times of -2 have all zeros on the left and all ones on the right. So if you do the bitwise sum with (2^n – 1), you’re going to get something in the range 0, (2^n – 1), and that’s going to be just right for the size of the hash table, because when you insert something into the hash table, you’re going to mod it to get the index. So if we use 2^n as the capacity size, we can replace the mod operation with bitwise and operation to improve computing efficiency. 2. It is convenient to distribute elements evenly when recalculating hash position after dynamic expansion: Since dynamic expansion is still an exponential of 2, the change in bitwise and operation values is the binary high +1, for example, from 16 to 32, the binary change is 0000 1111 (15) to 0001 1111 (31). Then this change will make the hash value of the elements of the expansion and need again after the bitwise and operator under the coordinate values or the same, or + 16 (i.e., move the location of the expansion after half capacity), so you can make the elements of the uniform on the same list (half) separated by expansion after the capacity of the distribution to the new hash table. (Note: Reason 2 (also known as advantage 2) was discovered and used after JDK1.8)
Q7: How to calculate the size of HashMap that meets expansion conditions (namely, expansion threshold)? A: Capacity expansion threshold =min(capacity load factor,MAXIMUM_CAPACITY+1). MAXIMUM_CAPACITY is very large, so the capacity load factor is generally used.
Q8: Does HashMap support null elements? A: Yes.
Q9: In the hash(obejject k) method of the HashMap, why not just mod the hash directly after calling k.hashcode (), but move the hash right and xOR? A: If the HashMap capacity is small and the hash value is large, hash conflicts tend to increase. The underlying design of hashMap-based indexFor, assuming a capacity of 16, is to perform bitwise and bitwise operations on binary 0000 1111 (i.e., 15), so that the higher 28 bits of the hash binary are meaningless because they will be 0&, 0 and 0. So it’s easy to get more hash collisions. H ^=(h20)^(h12); h^=(h20)^(h12); h^=(h20)^(h12); What’s the use? First, H20 and H12 shift the high binary of H to the low binary. The second xOR operation is to make use of the characteristics: the principle of same 0 different 1, as far as possible to make H20 and H12 in the future do mod (by bit and operation mode) to participate in the operation. So, in a nutshell, h^=(h20)^(h12); To reduce hash conflicts by making the higher bits of the binary hash value obtained by the k.hashcode () method participate in bitwise and operations as much as possible.
Q10: The same hash value, must the object be the same? Does the hash value have to be the same if the object is the same? A: Not necessarily. A certain.
Q11: HashMap expansion and insert elements in order? A: Before JDK1.7, you need to expand capacity and then insert capacity. After JDK1.8, you need to expand capacity and then insert capacity.
Q12: Why is HashMap expanded? A: Improve the efficiency of get, PUT and other methods of HashMap, because if you do not expand the list, the linked list will become longer and longer, resulting in low efficiency of insert and query.
Q13: jdk1.8 introduces red-black tree, if the number of single-linked list nodes exceeds 8, will it be tree-like? A: Not necessarily. It determines whether the current number of nodes is greater than the threshold for capacity expansion. If the capacity expansion condition is met, the system directly expands the capacity.