java 中HashMap、HashSet、TreeMap、TreeSet判斷元素相同的幾種方法比較

1.1     HashMap

       先來看一下HashMap里面是怎么存放元素的。Map里面存放的每一個(gè)元素都是key-value這樣的鍵值對，而且都是通過put方法進(jìn)行添加的，而且相同的key在Map中只會(huì)有一個(gè)與之關(guān)聯(lián)的value存在。put方法在Map中的定義如下。

  V put(K key, V value);

       它用來存放key-value這樣的一個(gè)鍵值對，返回值是key在Map中存放的舊value，如果之前不存在則返回null。HashMap的put方法是這樣實(shí)現(xiàn)的。

 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;

  }

       從上我們可以看到在添加對應(yīng)的key-value這樣的組合時(shí)，如果原本已經(jīng)存在對應(yīng)的key，則直接改變對應(yīng)的value，并返回舊的value，而在判斷key是否存在的時(shí)候是先比較key的hashCode，再比較相等或equals的。這里可能我們還看不出來，直接從上面代碼來看是比較的對應(yīng)Map.Entry的hashCode和key的hashCode，而實(shí)際上在后面我們可以看到Map.Entry的hashCode其實(shí)就是其存放key的hashCode。而如果對應(yīng)的key原本不存在的話將調(diào)用addEntry將對應(yīng)的key-value添加到Map中。addEntry傳遞的參數(shù)hash就是對應(yīng)key的hashCode。接著我們來看一下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++;

  }

        addEntry的核心是調(diào)用createEntry來建立表示對應(yīng)key-value的Map.Entry對象并進(jìn)行存放，很顯然上述table是一個(gè)Map.Entry的數(shù)組。Map.Entry中用一個(gè)屬性hash保存了對應(yīng)key的hashCode。還是來看一下上面調(diào)用的Map.Entry的構(gòu)造方法吧。

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

      value = v;

      next = n;

      key = k;

      hash = h;

    }

       很顯然，其內(nèi)部保存了對應(yīng)key、value和key對應(yīng)的hashCode。

       了解了HashMap是怎樣存放元素的以后，我們再來看HashMap是怎樣存放元素的就比較簡單了。HashMap中判斷元素是否相同主要有兩個(gè)方法，一個(gè)是判斷key是否相同，一個(gè)是判斷value是否相同。其實(shí)在介紹HashMap是怎樣存放元素時(shí)我們已經(jīng)介紹了HashMap是怎樣判斷元素Key是否相同的，那就是首先得hashCode相同，其次是key相等或equals。Map中判斷key是否相同是通過containsKey()方法進(jìn)行的，其在HashMap中的實(shí)現(xiàn)如下。

 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;

  }

       很明顯，它就是先判斷key的hashCode是否相同，再判斷key是否相等或equals的。

       Map中用來判斷value是否相同是通過containsValue方法來判斷的，其在HashMap中的實(shí)現(xiàn)如下。

  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;

  }

       很顯然，對于非null形式的value是通過value的equals來進(jìn)行判斷的，而null形式的只要相等即可，即保存的元素中有value為null即可。

1.2     HashSet

       知道了HashMap是如何存放元素和判斷元素是否相同的方式以后，我們再來看HashSet是如何判斷元素是否相同就比較簡單了。

       HashSet中的元素其實(shí)是通過HashMap來保存的，在每個(gè)HashSet對象中都持有一個(gè)對應(yīng)的HashMap對象的引用，在對HashSet進(jìn)行元素的添加、刪除等操作時(shí)都是通過其持有的HashMap來進(jìn)行的。在保存元素時(shí)其會(huì)將對應(yīng)的元素作為持有的HashMap的key來進(jìn)行保存，對應(yīng)的value是一個(gè)常量Object，所以其在保存的時(shí)候判斷元素是否相同所使用的是HashMap判斷key是否相同的邏輯。其在判斷是否包含某一元素時(shí)也是調(diào)用了所持有的HashMap的containsKey方法來進(jìn)行判斷的。

 public boolean contains(Object o) {

    returnmap.containsKey(o);

  }

       有興趣的朋友可以去看一下HashSet的源碼。 

1.3     TreeMap

       TreeMap中存放的元素都是有序的，而且是根據(jù)key進(jìn)行排序的。TreeMap在對存放的元素進(jìn)行排序時(shí)有兩種方式，一種是通過自身持有的Comparator進(jìn)行排序，另一種是通過實(shí)現(xiàn)了Comparable接口的key進(jìn)行排序，優(yōu)先使用第一種方式，當(dāng)持有的Comparator（默認(rèn)為null）為null時(shí)則采用第二種方式。TreeMap好幾個(gè)構(gòu)造方法，可以通過其構(gòu)造方法來初始化其持有的Comparator。我們還是先來看一下TreeMap是如何保存元素的，其put方法實(shí)現(xiàn)如下。

  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;

  }

        從上述實(shí)現(xiàn)我們可以看到，第一個(gè)元素將直接存進(jìn)去。之后的元素分兩種情況進(jìn)行，一種是持有的Comparator不為空的情況，一種是持有的Comparator為空的情況。Comparator不為空的時(shí)候?qū)⑼ㄟ^Comparator來確定存放元素的位置，其中有一點(diǎn)很重要的是當(dāng)通過Comparator比較了現(xiàn)有元素的key與當(dāng)前存放元素的key的結(jié)果為0時(shí)，將認(rèn)為當(dāng)前存放的元素key在原有Map中已經(jīng)存在，然后改變原有的key對應(yīng)的value為新value，然后就直接返回了舊value。當(dāng)持有的Comparator為空時(shí)將通過實(shí)現(xiàn)了Comparable接口的key的compareTo方法來決定元素存放的位置，有一點(diǎn)與使用Comparator類似的地方是當(dāng)原有key作為Comparable與新存入的key進(jìn)行比較的結(jié)果為0時(shí)將認(rèn)為新存入的key在原Map中已經(jīng)存在，將直接改變對應(yīng)的原key的value，而不再新存入key-value對。實(shí)際上其判斷元素是否存在的containsKey方法的主要實(shí)現(xiàn)邏輯也是類似的，具體實(shí)現(xiàn)如下。

 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;

  }

        因?yàn)門reeMap判斷元素是否存在的邏輯是通過判斷Comparator或Comparable進(jìn)行比較后的結(jié)果是否為0，所以我們在使用TreeMap希望實(shí)現(xiàn)某種類似于元素equals的邏輯時(shí)要特別小心。

       TreeMap的containsValue的邏輯還是判斷的對應(yīng)的value是否equals，與HashMap類似，有興趣的朋友可以查看一下TreeMap的源碼。

1.4     TreeSet

       TreeSet也是的Set的一種實(shí)現(xiàn)，其存放的元素是不重復(fù)的，而且是有序的，默認(rèn)情況下所存放的元素必須實(shí)現(xiàn)Comparable接口，因?yàn)槟J(rèn)情況下將把元素當(dāng)做Comparable對象進(jìn)行比較。TreeSet也是可以通過Comparator來比較其中存放的元素的，這可以在構(gòu)造TreeSet的時(shí)候通過傳入一個(gè)Comparator對象或一個(gè)持有Comparator對象的TreeMap來實(shí)現(xiàn)。TreeSet的實(shí)現(xiàn)與HashSet的實(shí)現(xiàn)類似，其內(nèi)部也持有了一個(gè)Map的引用，只不過它引用的不是HashMap，而是TreeMap。TreeSet中元素的新增、刪除等操作都是由其持有的TreeMap來實(shí)現(xiàn)的，所以與HashSet類似，TreeSet中判斷元素是否相同的方式與TreeMap是一致的，也是通過Comparator或Comparable來判定的，而不是傳統(tǒng)的equals方法。有興趣的朋友可以去查看一下TreeSet的源碼。

感謝閱讀，希望能幫助到大家，謝謝大家對本站的支持！

最新評論