How to solve hash conflict problem with HashMap in Java

1. Hash algorithm and Hash table

To understand Hash conflict, first understand the Hash algorithm and Hash table

• ##The Hash algorithm is Turn an input of any length into a fixed-length output through a hash algorithm. The output result is a hash value. To access the data structure of the memory storage location, in the specific implementation, we use the Hash function to map the key to a certain location in the table to obtain the data at this location, thereby speeding up the data search

• 2. Hash conflict
  Hash conflict is due to the hash algorithm. The calculated data is infinite, and the range of the calculated result is limited. There will always be different data. After If the values ​​obtained after calculation are the same, then a so-called hash conflict will occur in this case

3. There are four methods to resolve Hash conflicts

The open addressing method is also called the linear detection method. It starts from the position where the conflict occurs, finds a free position from the Hash table in a certain order, and then stores the conflicting elements into this position. In Java, ThreadLocal uses linear detection to resolve Hash conflicts

As shown in the figure, key=name is stored in the Hash table index 1, and when key=hobby is added to it, assuming that the calculated index is also 1, then this happens Hash conflict, and the open open addressing method is to find a free location in order to store the conflicting key

Chain addressing method, this is a common method, a simple understanding is to Keys with Hash conflicts are stored in a one-way linked list, such as HashMap

As shown in the figure, conflicting keys are directly stored in a one-way linked list

The Hash method is to calculate the key through a certain Hash function. When there is a conflict, another Hash function can be used to hash the key until no more conflicts occur. This method will increase the calculation. time, there will be some impact on performance

Establishing a public removal area is to divide the Hash table into two parts: the basic table and the benefit table. All conflicting elements will be placed in the benefit table.

4. Optimization of HashMap in JDK1.8 version

HashMap in JDK1.8 version solves the problem of Hash conflict through chain addressing method and red-black tree. Among them, red-black The tree is to optimize the problem of increased time complexity caused by the long linked list of the Hash table. When the length of the linked list is greater than or equal to 8 and the capacity of the Hash table is greater than 64, adding elements to the linked list will trigger the linked list to a red-black tree. Conversion

The above is the detailed content of How to solve hash conflict problem with HashMap in Java. For more information, please follow other related articles on the PHP Chinese website!