— — — — — —
As you know, a HashMap is a collection of key-value pairs, each of which is called an Entry. These entries are stored in an array, which is the backbone of the HashMap.
Each element of a HashMap array starts with a value of Null.
For HashMap, we use two methods most often: Get and Put.
1. Principle of the Put method
What happens when I call the Put method?
For example, call hashMap.put(“apple”, 0) and insert an element with Key “apple”. We need to use a hash function to determine the Entry’s insertion location (index) :
Index = Hash (” apple “)
Assuming the final index is 2, the result is as follows:
However, since the length of a HashMap is limited, when more and more entries are inserted, even a perfect Hash function will inevitably encounter index conflicts. Like this:
What to do? We can do that with a linked list.
Each element of a HashMap array is not only an Entry object, but also a linked list header node. Each Entry object points to its Next Entry node through the Next pointer. When a new Entry maps to a conflicting array location, simply insert it into the corresponding linked list:
It is important to note that new entries are inserted into the list using the “header” method. Why not insert the end of the list will be explained later.
2. The principle of Get method
What happens when you use the Get method to look for Value based on Key?
First, we will Hash the input Key and get the corresponding index:
Index = Hash (” apple “)
Because of the Hash conflict just mentioned, multiple entries may be matched at the same location. In this case, you need to search down the corresponding head nodes of the linked list one by one. Suppose the Key we’re looking for is “apple” :
In the first step, we look at the head node Entry6. The Key of Entry6 is banana, which is obviously not what we are looking for.
In the second step, we look at the Next node Entry1. The Key of Entry1 is Apple, which is exactly what we are looking for.
The Entry6 was placed in the head node because the inventors of HashMap believed that later inserted entries would have a better chance of being looked up.
— — — — — —
As mentioned earlier, to map from the Key to the corresponding position in the HashMap array, we use a Hash function:
Index = Hash (” apple “)
How do you implement a Hash function that is as evenly distributed as possible? We do some kind of operation by using the HashCode value of the Key.
The index = HashCode (Key) % Length?
How do we do bit operations? Here is the formula (Length is the Length of the HashMap) :
The index = HashCode (Key) & (Length 1)
Let’s use the Key with the value “book” to illustrate the whole process:
1. Calculate the Hashcode of book. The result is 3029737 in decimal and 101110001110101110 1001 in binary.
2. Assuming that the default Length of the HashMap is 16, calculate length-1 as 15 in decimal and 1111 in binary.
101110001110101110 1001&1111 = 1001, decimal is 9, so index=9.
The index result of the Hash algorithm depends entirely on the last few bits of the Key’s Hashcode value.
Assuming that the length of the HashMap is 10, repeat the procedure:
Taken alone, this result does not appear to be a problem. Let’s try a new HashCode 101110001110101110 1011:
Let’s try another HashCode 101110001110101110 1111:
Yes, although the second to last and third bits of HashCode change from 0 to 1, the result of the operation is 1001. That is, when the length of the HashMap is 10, some index results are more likely to occur, and some index results will never occur (such as 0111)!
In this case, the uniform distribution of Hash algorithms is obviously inconsistent.
In the case of Length 16 or any other power of 2, the value of length-1 is one for all bits, in which case the result of index is equal to the last few bits of HashCode. The result of the Hash algorithm is uniform as long as the input HashCode itself is evenly distributed.
For those of you who like this article, please long click on the image below to follow the subscription account Programmer Grey for more exciting content
