[Java interview] how does HashMap resolve hash conflicts?

Hi, Hello everyone , I am a Mic.

Today, let's share an interview question about one year's work .

Recently, many fans have encountered this problem during the interview

The problem is ：“HashMap Is how to solve Hash Conflicting ”？

Many people think this problem is very simple , But I think the expert's answer will be better .

Let's take a look at the answers of ordinary people and experts to this question .

Need expert interview documents （ A 100000 word interview document inside Alibaba is attached ） Or if you have technical interview questions you don't understand and want to consult, you can send private letters backstage 【Mic】 Or leave a message in the comment area .

Ordinary people ：

HashMap solve hash Ways of conflict I remember using the one-way linked list to say if you admit hash Conflict between , It will save the conflicting key value pairs to the end of the linked list .

master ：

well , I need to answer this question from several aspects .

First ,HashMap The bottom layer uses an array structure to store data elements , The default length of an array is 16, When we go through put Method to add data ,HashMap according to Key Of hash Value for modulo .

Finally save to the specified location of the array .

But this design will exist hash The question of conflict , That's two different things hash It's worth it key, The final module will fall into the same array subscript .

therefore HashMap Chain addressing method is introduced to solve hash The question of conflict , For conflicting key,HashMap Put these key Form a one-way linked list .

Then use the tail interpolation method to put this key Save to the end of the linked list .

in addition , In order to avoid the problem that the linked list is too long , When the chain length is greater than 8 And the array length is greater than or equal to 64 When ,

HashMap Will transform the linked list into a red black tree .

So as to reduce the time complexity of linked list data query , Improve query performance .

Last , I'll add that , solve hash There are many ways to solve conflict problems , such as

• Again hash Law , It's if one of them hash Function conflicts , And another one hash Calculate , For example, bloom filter adopts this method .

• Open addressing , It is to directly find an empty array subscript from the conflicting array position for data storage , This is in ThreadLocal It's used to .

• Establish a common overflow area , That is to say, the conflicting key Put them in a common overflow area .

The above is my understanding of this problem .

summary

hash The problem of conflict , In the process of business development, we seldom encounter .

But from the solution , Can learn a lot of technical design ideas

Whether for interview or long-term career development , I think this technical point is the basic knowledge that needs to be deeply understood .

Friends who like my works , Remember to like the collection and pay attention

Need expert interview documents （ A 100000 word interview document is attached ） Or if you have technical interview questions you don't understand, you can scan the QR code below

↓↓↓↓↓↓↓↓↓↓↓↓↓↓