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
- Separate chaining
- 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
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