Comparison of several methods for judging the same elements in HashMap, HashSet, treemap and TreeSet in Java

Comparison of several methods for judging the same elements in HashMap, HashSet, treemap and TreeSet in Java

1.1 HashMap

Let's take a look at how elements are stored in HashMap. Each element stored in the map is a key value pair, which is added through the put method, and only one value associated with the same key exists in the map. The put method is defined in the map as follows.

It is used to store a key value pair such as key value. The return value is the old value stored by the key in the map. If it does not exist before, it returns null. The put method of HashMap is implemented in this way.

From the above, we can see that when adding the corresponding key value combination, if the corresponding key already exists, the corresponding value will be directly changed and the old value will be returned. When judging whether the key exists, we first compare the hashcode of the key, and then compare the values of equality or equals. We may not see it here. From the above code, it is the corresponding map for comparison The hashcode of the entry and the hashcode of the key. In fact, we can see the map later The hashcode of an entry is actually the hashcode in which the key is stored. If the corresponding key does not exist, addentry will be called to add the corresponding key value to the map. The parameter hash passed by addentry is the hashcode of the corresponding key. Next, let's look at the method definition of addentry.

The core of addentry is to call createentry to create a map representing the corresponding key value The entry object and store it. Obviously, the above table is a map An array of entries. Map. The hashcode of the corresponding key is saved with an attribute hash in the entry. Let's take a look at the map called above The construction method of entry.

Obviously, the corresponding key, value and hashcode corresponding to key are saved inside.

After knowing how HashMap stores elements, it's easier to see how HashMap stores elements. There are two main methods to judge whether elements are the same in HashMap: one is to judge whether keys are the same, and the other is to judge whether values are the same. In fact, when introducing how HashMap stores elements, we have introduced how HashMap judges whether the element keys are the same, that is, first get the same hashcode, followed by equal or equal keys. The containskey () method is used to determine whether the keys in the map are the same. Its implementation in HashMap is as follows.

Obviously, it is to judge whether the hashcode of the key is the same, and then judge whether the key is equal or equal.

The containsvalue method is used to judge whether the values in the map are the same. Its implementation in HashMap is as follows.

Obviously, the non null form of value is judged by the equals of value, and the null form is as long as it is equal, that is, value in the saved element is null.

1.2 HashSet

After knowing how HashMap stores elements and how to judge whether elements are the same, let's see how HashSet judges whether elements are the same.

In fact, the elements in the HashSet are saved through the HashMap. Each HashSet object holds a reference to the corresponding HashMap object. When adding and deleting elements in the HashSet, they are carried out through the HashMap it holds. When saving an element, it will save the corresponding element as the key of the held HashMap. The corresponding value is a constant object, so it uses the logic of HashMap to judge whether the elements are the same or not. When judging whether an element is included, it also calls the containskey method of the held HashMap to judge.

Interested friends can take a look at the source code of HashSet.

1.3 TreeMap

The elements stored in the treemap are ordered and sorted by key. There are two ways for treemap to sort the stored elements. One is to sort through its own comparator, and the other is to sort through the key that implements the comparable interface. The first method is preferred, The second method is used when the held comparator (null by default) is null. Treemap has several construction methods, which can be used to initialize the held comparator. Let's first take a look at how treemap saves elements, and the implementation of its put method is as follows.

From the above implementation, we can see that the first element will be stored directly. The following elements are divided into two cases: one is when the held comparator is not empty, and the other is when the held comparator is empty. When the comparator is not empty, the location of the stored element will be determined through the comparator. One important point is that when the result of comparing the key of the existing element with the key of the currently stored element through the comparator is 0, it will be considered that the currently stored element key already exists in the original map, and then change the value corresponding to the original key to a new value, Then the old value is returned directly. When the held comparator is empty, the element storage location will be determined through the CompareTo method of the key implementing the comparable interface. One thing similar to using the comparator is that when the comparison result between the original key as comparable and the newly stored key is 0, it will be considered that the newly stored key already exists in the original map, and the value of the corresponding original key will be directly changed, Instead of saving new key value pairs. In fact, the main implementation logic of the containskey method for judging whether an element exists is similar. The specific implementation is as follows.

Because treemap judges whether an element exists by judging whether the result of comparator or comparable comparison is 0, we should be careful when using treemap to realize some logic similar to element equals.

The logic of containsvalue of treemap is to judge whether the corresponding value is equal. Similar to HashMap, interested friends can check the source code of treemap.

1.4 TreeSet

TreeSet is also an implementation of set. The stored elements are non repetitive and orderly. By default, the stored elements must implement the comparable interface, because by default, the elements will be compared as comparable objects. TreeSet can also compare the elements stored in it through comparator, which can be realized by passing in a comparator object or a treemap holding the comparator object when constructing TreeSet. The implementation of TreeSet is similar to that of HashSet. It also holds a reference to map, but it refers to treemap instead of HashMap. The addition, deletion and other operations of elements in TreeSet are realized by the treemap held by TreeSet. Therefore, similar to HashSet, the way to judge whether elements are the same in TreeSet is consistent with treemap, and it is also determined by comparator or comparable, rather than the traditional equals method. Interested friends can check the source code of TreeSet.

Thank you for reading, hope to help you, thank you for your support to this site!