To understand this article, you must have some understanding of data structures, and understand the advantages and disadvantages of each data structure. Of course, it’s even better if you already know that the underlying data structure of HashMap is array + linked list + red-black tree. If you also know that a hashMap initializes an array of 16 by default, and each time you expand it by twice that size, then I can only say “you’re already a big guy.”

I’m a bit of an inquisitive person. I believe in “being there for a reason”, which usually pays off for me, but occasionally leads me into a corner. OK, let’s cut to the chase.

Below is the source code for HashMap in JDK1.8

(Array length -1) &key (hashCode); (array length -1)

Ps: Modular calculation is not explained here, you can baidu yourself if you want to know

The following program simply simulates the subscript positions of 100 elements when the array length is 15 and 16 respectively. The hashcodes for these 100 elements are incremented from 0 to 100

Public static void main(String[] args) {int[] length={15,16};for(int n : length){
                System.out.println("-- -- -- -- -- -- -- -- -- -- -- -- -- -"+n+"-- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- --");
                for(int hash= 0;hash< = 100;hash++){
                    System.out.print((hash & n-1)+"\t"); } System.out.println(); }}Copy the code

The result is as follows

It can be seen that when the length of the array is 16, 16 slots are calculated and evenly distributed in each position of the array. When the length of the array is 15, only 8 slots are calculated and a two-node linked list is placed in each slot, resulting in 8 slots in the idle state. This problem is commonly referred to as hash collisions, which can make HashMap queries inefficient. We take the data from the map, can be directly calculated by the key slot to take out the corresponding element is ok, because now the deposit slot is a linked list, so want to fetch the data have to traverse the list, in very extreme cases hashcode (all the elements are the same), a HashMap will degenerate into a linked list. So you lose the efficiency of random array lookups.

Therefore, making the length of the array equal to the second power can effectively reduce the probability of hash collisions.

There are many other features of HashMap that you can use to write your own HashMap in the JDK. Ps: 1.7 HashMap is relatively simple. If you want to explore the source of HashMap, it is recommended to start with JDk1.7

Finally, a simple HashMap blog.csdn.net/qq_39914581…