In java HashMap HashSet TreeMap and TreeSet are compared in several ways to judge the same elements

In java, HashMap, HashSet, TreeMap and TreeSet are compared in several ways to judge the same elements

1.1 HashMap

So let's take a look at 1 and see how HashMap stores elements. Each element stored in Map is a key-value pair such as key-value, which is added through the put method, and there is only one value associated with the same key in Map. The put method is defined in Map as follows.

  V put(K key, V value);

It is used to store a key-value pair such as key-value. The return value is the old value that key stored in Map, or null if it did not exist before. The put method for HashMap is implemented this way.

 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;

  }

It can be seen from the above that when adding the corresponding combination of key-value, if the corresponding key already exists, the corresponding value will be directly changed and the old value will be returned. When judging whether key exists, key's hashCode will be compared first, and then the same or equals's hashCode will be compared. We may not be able to see it here, but we can see from the code above that the hashCode of Map.Entry is compared with the hashCode of key. In fact, we can see that the hashCode of Map.Entry is actually the hashCode of key. If the corresponding key does not already exist, addEntry will be called to add the corresponding key-value to Map. The parameter hash passed by addEntry is hashCode corresponding to key. Then let's 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 and store Map.Entry objects that correspond to key-value. Obviously, table above is an array of Map.Entry. Map. Entry USES a property hash to save hashCode corresponding to key. Let's look at the Map.Entry constructor called above.

   Entry(int h, K k, V v, Entry<K,V> n) {

      value = v;

      next = n;

      key = k;

      hash = h;

    }

Apparently, it holds hashCode for key, value, and key internally.

Now that you know how HashMap stores elements, let's look at how HashMap stores elements. In HashMap, there are two main methods to judge whether the elements are the same, one is to judge whether key is the same, the other is to judge whether value is the same. In fact, when we talked about how HashMap stores elements, we already talked about how HashMap determines whether the element Key is the same, that is, hashCode is the same, key is the same, equals is the same, key is the same, or equals is the same. Map determines whether key is the same as containsKey(), which is implemented in HashMap 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;

  }

Obviously, it is to judge whether hashCode of key is the same, and then whether key is the same or equals.

Map is used to determine whether value is the same as containsValue. 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, value in non-null form is judged by equals in value form, while null form is judged by equals, as long as it is equal to null form, that is, value is null in the saved element.

1.2 HashSet

Now that you know how HashMap stores elements and how to determine if they are the same, it's easier to see how HashSet determines if they are the same.

The elements in HashSet are actually saved by HashMap, and each HashSet object holds a reference to a corresponding HashMap object. When adding or deleting elements of HashSet, HashMap is held by HashMap. When saving an element, it will save the corresponding element as the key of HashMap it holds, and the corresponding value is a constant Object. Therefore, when saving an element, it will use HashMap to judge whether the element is the same or not. It also calls the containsKey method of the HashMap it holds to determine whether or not it contains a 1 element.

 public boolean contains(Object o) {

    returnmap.containsKey(o);

  }

Interested friends can go to see 1 HashSet source.

1.3 TreeMap

The elements stored in TreeMap are ordered and sorted according to key. There are two ways for TreeMap to sort the stored elements. One is to sort by Comparator held by itself, and the other is to sort by key which implements Comparable interface. The first way is preferred, and the second way is used when Comparator held (null by default) is null. TreeMap has several constructors whose constructors can be used to initialize the Comparator they hold. Let's take a look first 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 possibly 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;

  }

As you can see from the implementation above, the first element will be stored directly. The following elements are carried out in two cases, 1 in which the holding Comparator is not empty, and 1 in which the holding Comparator is empty. Comparator not empty through Comparator determines the location of the storage elements, including 1 point is very important when using Comparator compared the existing elements key and the result of the current storage element key to 0, will think that the current storage elements key already exist in the original Map, then change the original key corresponding value for new value, then returned to the old value directly. When holding Comparator is empty will by implementing the Comparable interface key compareTo method to decide the position of elements stored, there is 1 point and use Comparator similar place is that when the original key as Comparable comparing with new deposit key 0 will consider the result of the new deposit key already exist in the original Map, will change the corresponding original key value directly, instead of new deposit key - value on. In fact, the main implementation logic of the containsKey method to determine whether an element exists is similar. 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 that TreeMap USES to determine whether an element exists is by comparing Comparator or Comparable to see if the result is 0, we need to be particularly careful when using TreeMap in hopes of implementing some kind of logic similar to the element equals.

TreeMap containsValue logic or determine whether the corresponding value equals, similar to HashMap, interested friends can see 1 TreeMap source.

1.4 TreeSet

TreeSet is also an implementation of Set. The elements stored in TreeSet are not repeated and are in order. By default, the elements stored in Comparable must implement the Comparable interface, since the elements are compared as Comparable objects by default. TreeSet can also be used to compare the elements stored in it with Comparator, which can be done when constructing TreeSet by passing in an Comparator object or an TreeMap that holds an Comparator object. The implementation of TreeSet is similar to that of HashSet in that it also holds a reference to Map internally, except that instead of referring to HashMap, it refers to TreeMap. The addition, deletion and other operations of elements in TreeSet are all realized by TreeMap held by HashSet. Therefore, similar to HashSet, the way to judge whether elements in TreeSet are the same as TreeMap is 1, and it is also determined by Comparator or Comparable, instead of the traditional equals method. If you are interested, you can check the source code of TreeSet.

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