This article is participating in the “Java Theme Month – Java Brush questions punch card”, see the activity link for details

Please implement the simplest HashMap

We use HashMap a lot, and after iteration after iteration, the source code looks pretty big

Let’s implement HashMap ourselves this time to see what we can get!

Second, code demonstration

Problem description

A set of seven strings that need to be stored in an array, requiring O(1) time to fetch each element. That is, instead of iterating through the array, you get the element directly from the index of the array.

The solution

If we need to get an element from an array by ID, then we need to calculate an ID for each string’s position in the array. What can you think of to get an ID for a string? The most direct way to get numeric information for a string is with HashCode, but the range of HashCode values is too large [-2147483648, 2147483647] to use directly. Then you need to use HashCode and the length of the array to get a position that can appear in the array. If two elements have the same ID, then the array ID contains two strings.

Code implementation
Public static void main(String[] args) {// Initialize a List of strings List<String> List = new ArrayList<>(); List.add (" Iron Man "); List. The add (" hulk "); List. The add (" thor "); List.add (" Captain America "); List.add (" Captain Marvel "); List.add (" spiderman "); List. The add (" black panther "); [] TAB = new String[8]; For (String key: list) {int idx = key.hashCode() & (tab.length - 1); System.out.println(string. format("key =% Idx=%d", key, Idx)); if (null == tab[idx]) { tab[idx] = key; continue; } tab[idx] = tab[idx] + "->" + key; }}Copy the code
  1. Initializes a collection of strings, 7 of which are initialized.
  2. Define an array to hold strings. Note that the length is 8, which is a multiple of 2. That’s what gives you the character that 0111 is always one except for the high bits, also for hashing.
  3. The next step is to loop through the data, figuring out where each string is in the array. Key.hashcode () & (tab.length – 1).
  4. When a string is stored in an array, if the same element is encountered, the concatenation operation mimics the process of a linked list.
  5. Finally output storage results
The test results
Key value = Iron Man Idx=1 Key value = Hulk Idx=2 Key value = Thor Idx=7 Key value = Captain America Idx=7 Key value = Captain Marvel Idx=5 Key value = spiderman Idx=5 Key value = Black Panther Idx=0 [" panther ", "iron man", "hulk", null, null, "captain marvel - > spider-man", null, "thor - > captain America"]Copy the code

Third, thinking and analysis

The test results are first calculated for each element in the Idx of the array, and there are also repeated positions occurring

Finally, the output of the test result, 3, 4, 6, is empty 5, 7, and there are two elements linked to the position of Captain Marvel -> Spider-Man & Thor -> Captain America

This achieves one of our most basic requirements, hash the string elements into the array, and finally get the corresponding string by the index ID of the string element. This is one of the most basic principles of HashMap, and with this foundation it will be easier to understand the source implementation of HashMap.

Four,

HashMap HashMap HashMap HashMap HashMap HashMap HashMap HashMap HashMap HashMap HashMap HashMap HashMap HashMap HashMap HashMap HashMap