hashMap
Conflict is not thread-safe, hash zipper method is used to solve the problem of multithreaded operations result in infinite loop under the main reason is that concurrent Rehash will cause between elements can form a circular linked list https://coolshell.cn/articles… This is not very well written
Four construction methods
1. Set the load factor variable to the default value of 0.75 (by default, the initial capacity of HashMap is 16, and the default load factor is 0.75 because of the trade-off between time and space costs) 2. Passing in the initial capacity (there is no field in the HashMap to hold the initial capacity, the constructor sets the threshold to a power of 2 greater than the initial capacity, and when initializing the bucket array, the initial capacity = threshold) + sets the load factor to the default value of 3. Pass in the initial capacity and load factor 4. Copy the Map from the other Map into your own storage structure
To find the
The buckets are located based on (n-1)&hash, and then a linked list or red-black tree lookup is performed
The length of the size of the bucket array in a HashMap is always a power of 2 (bitwise can be used to calculate the position faster), in which case, (n-1) &hash is equivalent to mod length. Residual is not as efficient as bit operation. Only if n is a power of 2 can 1111 be used as a bit operation.
Recalculated hash
The hash in the graph is generated by the hashCode of the key. When calculating the remainder, because n is relatively small, only the lower four bits of the hash are involved in the calculation, leading to the failure of the high data. To address this defect, we perform XOR operations with the hash of the high 4-bit data and the low 4-bit data, i.e., hash ^ (hash >>> 4). In this way, the randomness of low level information is increased and the high level data can be participated in the calculation in a disguised way.
traverse
The traversal order is stable, but not the same as the insertion order
insert
When the bucket array table is empty, initialize table 1 by expanding capacity to find whether the key-value pair to be inserted already exists. If so, judge whether to replace the old value with a new value according to the condition. 2 If not, chain the key-value pair into the linked list. And decide whether to turn the list into a red-black tree according to the length of the linked list. 3 Determine whether the number of key value pairs is greater than the threshold value. If it is greater than the threshold value, expand the capacity
capacity
1 calculates the capacity of the new bucket array newCap and the new threshold newThr 2 creates a new bucket array based on the newly calculated newCap, and the bucket array table is initialized here. 3 remaps the key-value pair nodes into the new bucket array. If the node is of type TreeNode, you need to tear down the dividend black tree. If it is a normal node, the nodes are grouped in their original order.
The process of remapping a key to a node
For the tree node, split the bonus black tree and then map. For the linked list type nodes, the lists need to be grouped first and then mapped. If we have a map of 16 buckets, each hash value is in 16 buckets according to the last four bits. When the number of buckets is expanded to 32, each hash is divided into 32 buckets according to the last five bits, so elements from the original bucket will only go into two new buckets with the same relative position. 1.7 In order to prevent collision, random seeds are added to the hash to increase the randomness of the hash. In the process of capacity expansion, random seeds are determined whether to be regenerated according to the capacity. 1.8 Since the red-black tree is not afraid of collision, random seeds are not added, and there is no need to re-hash when capacity expansion, which is more efficient.
The tree,
Treealization occurs when the length of the linked list is greater than or equal to the TREEIFY_THRESHOLD bucket array capacity is greater than or equal to MIN_TREEIFY_CAPACITY
Tree node comparison
HashMap was not designed with red-black trees in mind for later optimization. As a result, the key class is not required to implement the Comparable interface or provide a corresponding comparator, as is the case with TreeMap. However, since treeing requires comparing the sizes of two key objects, to solve this problem, HashMap does three steps to ensure that the two key sizes can be compared, as follows: 1 Compare the size of the hash between keys. If the hash is the same, proceed to the comparison. 2 Check that the key class has implemented the Comparable interface. The arbitration method is tieBreakOrder (see the source code for yourself). Tie break is a tennis term that means to play overtime, which is a fun name for it. ? Why does comparing key hash sizes allow you to compare key sizes?
The red-black tree splits
When converting a normal linked list to a red-black tree, HashMap preserves the order of the nodes in the original linked list with two additional references next and prev. In this way, when remapping the red-black tree, it can be done in the way of mapping linked lists. If the new list is too long, tree it again.
Buckets cannot be serialized
The bucket array Table is declared transient. Transient means mutable. In Java, variables modified by this keyword are not serialized by the default serialization mechanism. Instead of using the default serialization mechanism, HashMap customizes the serialized content by implementing the readObject/writeObject methods. However, there are two problems with serializing talbe: the table will not be full in most cases, and it will waste space by serializing unused parts. The same key-value pair may be in different buckets in different JVMs, and deserializing the table in different JVMs may result in an error. If the key does not override the hashCode method, the hashCode method in Object is eventually called when the hash is evaluated. The hashCode method in Object is native, and different JVMs may have different implementations and produce different hashes. In other words, the same key may generate different hashes on different platforms.