— — — — — —
As you know, a HashMap is a collection of key-value pairs, each of which is also called an Entry. These key-value pairs are scattered in an array that is the backbone of a HashMap.
The initial value for each element of the HashMap array is Null.
For a HashMap, we most often use two methods: Get and Put.
1. Principle of the Put method
What happens when YOU call the Put method?
For example, call hashmap.put (“apple”, 0) and insert an element with a Key of “apple”. In this case, we need to use a hash function to determine the Entry position (index) :
Index = Hash (” apple “)
Assuming the final index is 2, the result is as follows:
However, the length of a HashMap is limited. As more and more entries are inserted, the perfect Hash function will inevitably have index conflicts. Like this:
What to do at this point? We can solve this with linked lists.
Each element of the HashMap array is not only an Entry object, but also the head node of a linked list. Each Entry object points to its Next Entry node through the Next pointer. When a new Entry is mapped to a conflicting array location, just insert it into the corresponding linked list:
Note that the new Entry node is inserted into the linked list using a “header” method. Why not insert the end of the list will be explained later.
2. Principle of Get method
What happens when you use the Get method to find a Value based on a Key?
First, the input Key will be Hash mapped to obtain the corresponding index:
Index = Hash (” apple “)
Because of the Hash conflict mentioned above, the same position may match multiple entries. In this case, you need to search down the head node of the corresponding linked list one by one. Let’s say the Key we’re looking for is “apple” :
The first step is to look at the head node Entry6. The Key of Entry6 is banana, which is obviously not the result we are looking for.
In the second step, we look at the Next node Entry1. The Entry1 Key is Apple, which is exactly what we are looking for.
Entry6 is placed in the head node because HashMap’s inventors believe that post-inserted entries are more likely to be found.
— — — — — —
As mentioned earlier, we use a Hash function to map from Key to the corresponding position in the HashMap array:
Index = Hash (” apple “)
How do you implement a Hash function that is as evenly distributed as possible? We do something by using the HashCode value of the Key.
Index = HashCode (Key) % Length?
How do you do bitwise operations? There is the following formula (Length is the Length of the HashMap) :
Index = HashCode (Key) & (length-1)
Here’s a Key with a value of “book” to illustrate the process:
1. Calculate the hashcode of book and the result is 3029737 in decimal and 101110001110101110 1001 in binary.
2. Assuming that the HashMap Length is 16 by default, the result of calculating Leng-1 is 15 in decimal and 1111 in binary.
101110001110101110 100&1111 = 1001, 101110001110101110 100&1111 = 1001, index=9
The final index result of the Hash algorithm depends entirely on the last few bits of the Hashcode of the Key.
Assuming the length of the HashMap is 10, repeat the procedure:
Looking at this result alone, there is nothing wrong on the surface. Let’s try a new HashCode 101110001110101110 1011:
Let’s try HashCode 101110001110101110 1111:
Yes, even though the second-to-last and third bits of HashCode have changed from 0 to 1, the result of the operation is 1001. That is, when the HashMap length is 10, some index results are more likely to occur, and some index results will never occur (like 0111)!
This does not comply with the principle of uniform distribution of Hash algorithms.
In terms of Length 16 or any power of two, length-1 is a value where all binary bits are 1, in which case the result of index is the same as the value of the last few bits of HashCode. The result of the Hash algorithm is uniform as long as the input HashCode itself is evenly distributed.
— — the END — — –
If you like this article, please long click the picture below to follow the subscription number programmer Xiao Grey and watch more exciting content
