JDK1.8

conclusion

Positioning elements

The location of elements in HashMap is to obtain the hash value after the key is perturbed by the perturbation function, and then to locate elements by replacing the modulo with hash(key) & (length - 1).

The load factor

The load factor of a HashMap represents the level of use (or utilization) of the hash table space. The larger the load factor, the higher the load of the HashMap. In other words, more elements can be accommodated. If there are more elements, the probability of hash collision will be increased, and the linked list will be elongated. At this time, the query efficiency will be reduced. When the load factor is smaller, the data amount in the linked list will be more sparse, which will cause a waste of space, but the query efficiency is high at this time.

capacity

Resize () does two things: it doubles the size and copies 1.7 headers. Multithreading causes an endless loop of 1.8 headers. There is no guarantee that the last put value will be the same value the next second

The tree is changed conditions

When the list length is greater than 8, the array length is greater than or equal to 64. TreeIfyBin method will be called when the list length is greater than 8. However, there is a rule inside TreeIfyBin method that only when the array length is greater than 64, the tree will be performed, otherwise it is just resize expansion. Since the list is too long and the array is too short, hash collisions will often occur. In this case, tree is actually a symptom rather than a cure, because the root cause of the long list is the short array. The length of the array is checked before the tree is performed, and if the length is less than 64, the array is expanded rather than treed

0.75 16 8, 64

0.75 improve space utilization and reduce the cost of compromise, mainly is the poisson distribution, 0.75 minimum 16 collision theory, a power of 2 is fine, but if it is 2, 4 or 8 will is a little small, can't add how much data will be expanded, which is frequently expands, so not affect performance, if it is a 32 or more, It's a waste of space, so 16 is a good rule of thumb to keep the power of 2 as 1. If length is a power of 2 then length-1 must be 11111... 2. Uniform hashing of the last bit of an odd number is 1, thus ensuring that the last bit of h&(length-1) is either 0 or 1 (depending on the value of h), and that the sum result may be even or odd. If length is odd, then obviously length-1 is even and the last bit of it is 0, then h&(length-1) must be 0 and can only be even, so any hash value will only be hashed to the even index position of the array. This wastes nearly half of the space. Therefore,length is raised to an integer power of 2 in order to minimize the probability of collisions between different hash values, so that the elements can be hashed evenly in the hash table. 8 * 0: 0.60653066 * 1: 0.30326533 * 2: 0.07581633 * 3: 0.01263606 * 4: 0.00157952 * 5: 0.00015795 * 6: 0.00001316 * 7: If hashCode's distribution is well discrete, red-black trees are rarely used because the values are evenly distributed and the list is rarely long. In the ideal case, the length of the linked list is in line with the Poisson distribution, and the hit probability of each length decreases in turn. The note shows us the specific hit probability of length 1-8. When the length is 8, the probability is only 0.00000006, so the red-black tree transformation of HashMap will almost never happen. Because we don't store that much data for everyday use, would you store tens of millions of data into a HashMap? Of course, this is an ideal algorithm, but if the HashMap process is used by a user and results in a poorly distributed HashCode, then switching to a red-black tree is a good compromise strategy. When the length of the 64 list is greater than 8, the treeIfyBin method will be called to convert it into a red-black tree. However, there is a rule inside the treeIfyBin method that the tree will only be performed if the length of the array is greater than 64, otherwise it will only be resize expansion. Since the list is too long and the array is too short, hash collisions will often occur. In this case, tree is actually a symptom rather than a cure, because the root cause of the long list is the short array. The length of the array is checked before the tree is performed, and if the length is less than 64, the array is expanded rather than treed

The illustration

Array + linked list + red-black tree

thinking

In the case of HashMap, does overriding the equals method require overriding the hashCode method?

When two objects equals() returns true, their hashCode() values need to be equal; If two objects' hashCode() values are equal, then their equals() values are not necessarily true; So in this case, if you want to determine whether two objects are equal, you have to override hashCode() as well as equals(), otherwise unexpected problems will occur.

See here is some a great 👇 share more technical articles, to help more people, here are all my knowledge base oh ~ 🐌 https://www.yuque.com/yingwen…