编程知识 cdmana.com

Explanation of hash conflict

WeChat search 「 Yard farmland, Xiao Qi 」, Focus on this program in New York , reply 「01-05」 You can get a selection of computer books 、 Personal writing notes 、 Big factory surface 、 Interview materials and other resources , mua ~

Hash conflict details

Generally speaking, there are two types of hash conflicts Solution

  1. Separate chaining
  2. Open addressing

Java The first is used in Separate chaining, I.e. add another one at the back of the bucket in collision “ chain ” To store , So this “ chain ” What data structure is used , Different versions are slightly different :

stay JDK1.6 and 1.7 in , Yes, it is Linked list Stored , So if there's a lot of collisions , It becomes a search on the linked list ,worst case Namely O(n);

stay JDK 1.8 optimized , When the chain length is large ( exceed 8), Will be used Red and black trees To store , This greatly improves the search efficiency .

( Words , I really like it , I've been asked in many interviews , And the interviewer asked why it was more than “8” Only red and black trees )

The second method open addressing It's also a very important thought , Because in a real distributed system , There are many places to use it hash But it's not suitable for use seprate chaining.

This is a sequential search , If this bucket is already occupied , Then according to “ In some way ” Keep looking for the next unoccupied bucket , Until you find the first empty .

As shown in the figure ,John Smith and Sandra Dee Hash conflict occurred , All calculated to 152 Bucket number , therefore Sandra I went to the next vacancy - 153 Bucket number , Of course, it will be right after that key Impact :Ted Baker The calculation result should have been 153 The no. , But whereas Sandra Account for the , We'll have to go to the next vacancy , So here we are. 154 Number .

This way is called Linear probing Linear probe , As shown above , Follow them one by one to find the next vacancy . There are other ways , For example, find the square number , perhaps Double hashing.


If you like this article , Remember to leave me a like message ~ Your support and recognition , It's the biggest driving force of my creation , See you in the next article !

This is Qi , New York program , Lifelong learners , Every night 9 spot , Let's meet you in the cloud study room !

See my... For more dry articles Github: https://github.com/xiaoqi6666/NYCSDE

版权声明
本文为[Yard farmland]所创,转载请带上原文链接,感谢

Scroll to Top