Comparison of several ways to judge the same elements of HashMap, HashSet, TreeMap, and TreeSet in Java
1.1 HashMap
Let’s first take a look at how elements are stored in HashMap. Each element stored in the map is a key-value pair like key-value, and is added through the put method. In addition, the same key will only have a value associated with it in the map. The put method is defined in the Map as follows.
V put(K key, V value);
It is used to store a key-value pair like key-value. The return value is the old value stored in the map by the key. If it does not exist before, it will return null. This is how HashMap put method is implemented.
public V put(K key, V value) { if (key == null) return putForNullKey(value); int hash = hash(key); int i = indexFor(hash, table.length); for (Entry<K,V> e = table[i]; e != null; e = e.next) { Object k; if (e.hash == hash && ((k = e.key) == key || key.equals(k))) { V oldValue = e.value; e.value = value; e.recordAccess(this); return oldValue; } } modCount++; addEntry(hash, key, value, i); return null; }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 changed directly and the old value will be returned. When judging whether the key exists, the hashCode of the key is first compared, and then the hashCode of the key is compared with equals or equals. We may not be able to see it here. From the above code, we compare the hashCode of Map.Entry and the hashCode of key. In fact, we can see that Map.Entry hashCode is actually the hashCode of its key. If the corresponding key does not exist originally, addEntry will be called to add the corresponding key-value to the map. The parameter hash passed by addEntry is the hashCode corresponding to the key. Next, let’s take a look at the method definition of addEntry.
void addEntry(int hash, K key, V value, int bucketIndex) { if ((size >= threshold) && (null != table[bucketIndex])) { resize(2 * table.length); hash = (null != key) ? hash(key) : 0; bucketIndex = indexFor(hash, table.length); } createEntry(hash, key, value, bucketIndex); } void createEntry(int hash, K key, V value, int bucketIndex) { Entry<K,V> e = table[bucketIndex]; table[bucketIndex] = new Entry<>(hash, key, value, e); size++; }The core of addEntry is to call createEntry to create a Map.Entry object representing the corresponding key-value and store it. Obviously, the above table is an array of Map.Entry. Map.Entry uses a property hash to save the hashCode of the corresponding key. Let’s take a look at the constructor of Map.Entry called above.
Entry(int h, K k, V v, Entry<K,V> n) { value = v; next = n; key = k; hash = h; }Obviously, it saves the hashCode corresponding to the corresponding key, value and key.
After understanding how HashMap stores elements, it is easier to see how HashMap stores elements. There are two main methods in HashMap to determine whether the elements are the same. One is to determine whether the key is the same, and the other is to determine whether the value is the same. In fact, when introducing how HashMap stores elements, we have introduced how HashMap determines whether the element key is the same. That is, first of all, the hashCode is the same, and secondly, the keys are equal or equals. The determination of whether the key is the same in the Map is performed through the containsKey() method, and its implementation in HashMap is as follows.
public boolean containsKey(Object key) { return getEntry(key) != null; } final Entry<K,V> getEntry(Object key) { int hash = (key == null) ? 0 : hash(key); for (Entry<K,V> e = table[indexFor(hash, table.length)]; e != null; e = e.next) { Object k; if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) return e; } return null; }It is obvious that it first determines whether the hashCode of the key is the same, and then determines whether the key is equal or equals.
The value used in Map is judged by the containsValue method, and its implementation in HashMap is as follows.
public boolean containsValue(Object value) { if (value == null) return containsNullValue(); Entry[] tab = table; for (int i = 0; i < tab.length ; i++) for (Entry e = tab[i] ; e != null ; e = e.next) if (value.equals(e.value)) return true; return false; }Obviously, the value of non-null form is judged by the equals of the value, and the null form is as long as it is equal, that is, the value in the saved element is null.
1.2 HashSet
After knowing how HashMap stores elements and determines whether elements are the same, it is easier to see how HashSet determines whether elements are the same.
The elements in the HashSet are actually saved through HashMap. Each HashSet object holds a reference to the corresponding HashMap object. When adding and deleting elements to the HashSet, it is performed 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 when saving it, it uses the logic of determining whether the elements are the same. When determining whether an element is included, it also calls the containsKey method of the HashMap held to make judgments.
public boolean contains(Object o) { returnmap.containsKey(o); }Friends who are interested can check out the source code of HashSet.
1.3 TreeMap
The elements stored in TreeMap are ordered and sorted according to the key. TreeMap has two ways to sort stored elements. One is to sort through the Comparator it holds, and the other is to sort through the key that implements the Comparable interface. The first method is preferred. When the held Comparator (the default is null) is null, the second method is used. TreeMap has several constructors, through which the Comparator it holds can be initialized. Let’s first look at how TreeMap saves elements. The put method is implemented as follows.
public V put(K key, V value) { Entry<K,V> t = root; if (t == null) { compare(key, key); // type (and possible null) check root = new Entry<>(key, value, null); size = 1; modCount++; return null; } int cmp; Entry<K,V> parent; // split comparator and comparable paths Comparator<? super K> cpr = comparator; if (cpr != null) { do { parent = t; cmp = cpr.compare(key, t.key); if (cmp < 0) t = t.left; elseif (cmp > 0) t = t.right; else return t.setValue(value); } while (t != null); } else { if (key == null) thrownew NullPointerException(); Comparable<? super K> k = (Comparable<? super K>) key; do { parent = t; cmp = k.compareTo(t.key); if (cmp < 0) t = t.left; elseif (cmp > 0) t = t.right; else return t.setValue(value); } while (t != null); } Entry<K,V> e = new Entry<>(key, value, parent); if (cmp < 0) parent.left = e; else parent.right = e; fixAfterInsertion(e); size++; modCount++; return null; }From the above implementation we can see that the first element will be stored directly. The following elements are divided into two situations, one is the case where the Comparator held is not empty, and the other is the case where the Comparator held is empty. When Comparator is not empty, Comparator will determine the location of the stored element. One important thing is that when the result of comparing the key of the existing element with the key of the current stored element is 0, it will be considered that the key of the currently stored element already exists in the original map, and then the value corresponding to the original key is changed to the new value, and then the old value is returned directly. When the held Comparator is empty, the location of the element will be determined by the compareTo method of the key that implements the Comparable interface. One thing similar to using Comparator is that when the original key is compared with 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 changed directly, and the key-value pair will no longer be stored. In fact, the main implementation logic of the containsKey method that determines whether the element exists is similar, and the specific implementation is as follows.
public boolean containsKey(Object key) { return getEntry(key) != null; } final Entry<K,V> getEntry(Object key) { // Offload comparator-based version for sake of performance if (comparator != null) return getEntryUsingComparator(key); if (key == null) thrownew NullPointerException(); Comparable<? super K> k = (Comparable<? super K>) key; Entry<K,V> p = root; while (p != null) { int cmp = k.compareTo(p.key); if (cmp < 0) p = p.left; elseif (cmp > 0) p = p.right; else return p; } return null; }Because the logic of TreeMap to determine whether an element exists is to determine whether the result after comparing Comparator or Comparable is 0, we should be particularly careful when using TreeMap to implement some logic similar to element equals.
The logic of TreeMap containsValue is to determine whether the corresponding value is equals? Similar to HashMap. Interested friends can check the source code of TreeMap.
1.4 TreeSet
TreeSet is also an implementation of Set. The elements stored are not repeated and are ordered. By default, the elements stored must implement the Comparable interface, because by default, the elements will be compared as Comparable objects. TreeSet can also be used to compare the elements stored in it through Comparator. This can be achieved by passing in a Comparator object or a TreeMap holding a Comparator object when constructing a TreeSet. The implementation of TreeSet is similar to that of HashSet. It also holds a reference to a Map, but it does not refer to a HashMap, but TreeMap. The addition and deletion of elements in TreeSet are all implemented by the TreeMap they hold. Therefore, similar to HashSet, the way to determine whether elements in TreeSet is the same is consistent with TreeMap, and is also determined through Comparator or Comparable, rather than the traditional equals method. Interested friends can check the source code of TreeSet.
Thank you for reading, I hope it can help you. Thank you for your support for this site!