java TreeMap源碼解析詳解

 在介紹TreeMap之前，我們來了解一種數(shù)據(jù)結(jié)構(gòu)：排序二叉樹。相信學(xué)過數(shù)據(jù)結(jié)構(gòu)的同學(xué)知道，這種結(jié)構(gòu)的數(shù)據(jù)存儲(chǔ)形式在查找的時(shí)候效率非常高。

如圖所示，這種數(shù)據(jù)結(jié)構(gòu)是以二叉樹為基礎(chǔ)的，所有的左孩子的value值都是小于根結(jié)點(diǎn)的value值的，所有右孩子的value值都是大于根結(jié)點(diǎn)的。這樣做的好處在于：如果需要按照鍵值查找數(shù)據(jù)元素，只要比較當(dāng)前結(jié)點(diǎn)的value值即可（小于當(dāng)前結(jié)點(diǎn)value值的，往左走，否則往右走），這種方式，每次可以減少一半的操作，所以效率比較高。在實(shí)現(xiàn)我們的TreeMap中，使用的是紅黑樹（一種優(yōu)化了的二叉排序樹）。

     一、TreeMap的超接口 

     TreeMap主要繼承了類AbstractMap（一個(gè)對(duì)Map接口的實(shí)現(xiàn)類）和 NavigableMap（主要提供了對(duì)TreeMap的一些高級(jí)操作例如：返回第一個(gè)鍵或者返回小于某個(gè)鍵的視圖等）。主要的一些操作有：put添加元素到集合中，remove根據(jù)鍵值或者value刪除指定元素，get根據(jù)指定鍵值獲取某個(gè)元素，containsValue查看是否包含某個(gè)指定的值，containsKey 查看是否包含某個(gè)指定的key數(shù)值等。

     二、構(gòu)造函數(shù) 

           TreeMap 的構(gòu)造函數(shù)主要有以下幾種：

 private final Comparator<? super K> comparator;

  public TreeMap() {comparator = null;}

  public TreeMap(Comparator<? super K> comparator) {
    this.comparator = comparator;
  } 

          因?yàn)樵谖覀兊膬?nèi)部存儲(chǔ)結(jié)構(gòu)中，是需要對(duì)兩個(gè)節(jié)點(diǎn)的元素的鍵值進(jìn)行比較的，所以就必須要實(shí)現(xiàn)Comparable接口來具有比較功能。第一個(gè)構(gòu)造函數(shù)默認(rèn)無參，內(nèi)部將我們的比較器賦值為null，表明：在內(nèi)部集合中不需要接受來自外部傳入的比較器，默認(rèn)使用Key的比較器（例如：Key是Integer類型就會(huì)默認(rèn)使用它的比較器）。第二種構(gòu)造函數(shù)就是從外部傳入指定的比較器，指定TreeMap內(nèi)部在對(duì)鍵進(jìn)行比較的時(shí)候使用我們從外部傳入的比較器。

     三、內(nèi)部存儲(chǔ)的基本原理 

          從源碼中摘取部分代碼，能說明內(nèi)部結(jié)構(gòu)即可。

private final Comparator<? super K> comparator;
private transient Entry<K,V> root;
private transient int modCount = 0;
//靜態(tài)成員內(nèi)部類
static final class Entry<K,V> implements Map.Entry<K,V> {
    K key;
    V value;
    Entry<K,V> left;
    Entry<K,V> right;
    Entry<K,V> parent;
    boolean color = BLACK;
    .........
   }

          從代碼中，我們可以很容易的看出來，內(nèi)部包含一個(gè) comparator 比較器（或值被置為Key的比較器，或是被置為外部傳入的比較器），根結(jié)點(diǎn) root （指向紅黑樹的跟結(jié)點(diǎn)），記錄修改次數(shù) modCount （用于對(duì)集合結(jié)構(gòu)性的檢查和前面文章說的一樣），還有一個(gè)靜態(tài)內(nèi)部類（其實(shí)可以理解為一個(gè)樹結(jié)點(diǎn)），其中有存儲(chǔ)鍵和值的key和value，還有指向左孩子和右孩子的“指針”，還有指向父結(jié)點(diǎn)的“指針”，最后還包括一個(gè)標(biāo)志 color（這個(gè)暫時(shí)不用知道）。也就是說，一個(gè)root指向樹的跟結(jié)點(diǎn)，而這個(gè)跟根結(jié)點(diǎn)又鏈接為一棵樹，最后通過這個(gè)root可以遍歷整個(gè)樹。

     四、put添加元素到集合中 

          在了解了TreeMap的內(nèi)部結(jié)構(gòu)之后，我們可以看看他是怎么將一個(gè)元素結(jié)點(diǎn)掛到整棵樹上的。由于put方法的源碼比較多，請(qǐng)大家慢慢看。

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;
        else if (cmp > 0)
          t = t.right;
        else
          return t.setValue(value);
      } while (t != null);
    }
    else {
      if (key == null)
        throw new NullPointerException();
      @SuppressWarnings("unchecked")
        Comparable<? super K> k = (Comparable<? super K>) key;
      do {
        parent = t;
        cmp = k.compareTo(t.key);
        if (cmp < 0)
          t = t.left;
        else if (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;
  }

          首先判斷根結(jié)點(diǎn)是否是空的，如果是空的直接創(chuàng)建一個(gè)結(jié)點(diǎn)并將parent賦null，將其作為該樹的跟結(jié)點(diǎn)，返回null跳過余下代碼。如果跟結(jié)點(diǎn)不是空的，就去判斷 comparator 是否為null（也就是判斷comparator的值是默認(rèn)key的比較器還是外部傳入的比較器），如果comparator的值是外部傳入的，通過循環(huán)比較key的值計(jì)算將要添加的結(jié)點(diǎn)的位置（過程中如果發(fā)現(xiàn)有某個(gè)結(jié)點(diǎn)的key值和將要添加的key的值相等，說明這是修改操作，修改其value值返回舊value值）。 

          如果在創(chuàng)建對(duì)象的時(shí)候并沒有從外部傳入比較器，首先判斷key的值是否為null（如果是就拋出空指針異常），那有人說：為什么要對(duì)key是否為空做判斷呢？上面不是也沒有做判斷么？ 答案是：如果 comparator 是外部傳入的，那么沒問題，但是如果是key的默認(rèn)比較器，那如果key為null 還要調(diào)用比價(jià)器 必然拋空指針異常。接下來做的事情和上面一樣的。 

          程序執(zhí)行到最后了，我們要知道一點(diǎn)的是：parent指向的是最后一個(gè)結(jié)點(diǎn)也就是我們將要添加的結(jié)點(diǎn)的父結(jié)點(diǎn)。最后根據(jù)key和value和parent創(chuàng)建一個(gè)幾點(diǎn)（父結(jié)點(diǎn)是parent），然后根據(jù)上面的判斷確定此結(jié)點(diǎn)是parent的左孩子還是右孩子。 

          這個(gè)方法中有一個(gè) fixAfterInsertion(e); 是用于紅黑樹的構(gòu)造的，調(diào)用這個(gè)函數(shù)可以將我們剛剛創(chuàng)建完成之后的樹通過挪動(dòng)重新構(gòu)建成紅黑樹。

          最后總結(jié)一下整個(gè)put方法的執(zhí)行過程：

1. 判斷此樹是否是空的，空樹的操作就很簡(jiǎn)單了
2. 判斷比較器的來源做不同的操作（比較value值確定位置）
3. 構(gòu)建新結(jié)點(diǎn)掛上樹
4. 調(diào)用方法重構(gòu)紅黑樹
   

其中，我們要區(qū)分一點(diǎn)的是，為什么有時(shí)候返回的null，有時(shí)候返回的是舊結(jié)點(diǎn)的value，主要區(qū)別還是在于，put方法作為添加元素和修改元素的兩種功能，添加元素的時(shí)候統(tǒng)一返回的是null，修改元素的時(shí)候統(tǒng)一返回的是別修改之前的元素的value。

     五、根據(jù)鍵的值刪除結(jié)點(diǎn)元素 

          添加元素直到是怎么回事了之后，我們來看看刪除元素是怎么被實(shí)現(xiàn)的，首先看remove方法：

 public V remove(Object key) {
    Entry<K,V> p = getEntry(key);
    if (p == null)
      return null;

    V oldValue = p.value;
    deleteEntry(p);
    return oldValue;
  }

          從代碼中可以看出來，刪除的操作主要還是兩個(gè)操作的結(jié)合，一個(gè)是獲取指定元素，一個(gè)是刪除指定元素。我們先看如何獲取指定元素。

 final Entry<K,V> getEntry(Object key) {
    // Offload comparator-based version for sake of performance
    if (comparator != null)
      return getEntryUsingComparator(key);
    if (key == null)
      throw new NullPointerException();
    @SuppressWarnings("unchecked")
      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;
      else if (cmp > 0)
        p = p.right;
      else
        return p;
    }
    return null;
  }

          這段代碼不難理解，依然是分兩種情況比較器的來源（由于兩種情況下的處理方式類似，此處指具體說其中一種），p指向根結(jié)點(diǎn)root，循環(huán)遍歷，比較key和當(dāng)前循環(huán)到的key是否相等，不相等就根據(jù)大小向左或者向右，如果相等執(zhí)行return p; 返回此結(jié)點(diǎn)。如果整棵樹遍歷完成之后，沒有找到指定鍵值的結(jié)點(diǎn)就會(huì)返回null表示未找到該結(jié)點(diǎn)。這就是查找方法，下面我們看看刪除指定結(jié)點(diǎn)的方法。

          在看代碼之前我們先了解一下整體的思路，將要?jiǎng)h除的結(jié)點(diǎn)可能有以下三種情況：

• 該結(jié)點(diǎn)為葉子結(jié)點(diǎn)，即無左孩子和右孩子
• 該結(jié)點(diǎn)只有一個(gè)孩子結(jié)點(diǎn)
• 該結(jié)點(diǎn)有兩個(gè)孩子結(jié)點(diǎn)

第一種情況，直接將該結(jié)點(diǎn)刪除，并將父結(jié)點(diǎn)的對(duì)應(yīng)引用賦值為null

第二種情況，跳過該結(jié)點(diǎn)將其父結(jié)點(diǎn)指向這個(gè)孩子結(jié)點(diǎn)

第三種情況，找到待刪結(jié)點(diǎn)的后繼結(jié)點(diǎn)將后繼結(jié)點(diǎn)替換到待刪結(jié)點(diǎn)并刪除后繼結(jié)點(diǎn)（將問題轉(zhuǎn)換為刪除后繼結(jié)點(diǎn)，通過前面兩種可以解決）

找到后繼結(jié)點(diǎn)

替換待刪結(jié)點(diǎn)

刪除后繼結(jié)點(diǎn)

     下面我們看代碼：

/*代碼雖多，我們一點(diǎn)一點(diǎn)看*/
  private void deleteEntry(Entry<K,V> p) {
    modCount++;
    size--;

    // If strictly internal, copy successor's element to p and then make p
    // point to successor.
    if (p.left != null && p.right != null) {
      Entry<K,V> s = successor(p);
      p.key = s.key;
      p.value = s.value;
      p = s;
    } // p has 2 children

    // Start fixup at replacement node, if it exists.
    Entry<K,V> replacement = (p.left != null ? p.left : p.right);

    if (replacement != null) {
      // Link replacement to parent
      replacement.parent = p.parent;
      if (p.parent == null)
        root = replacement;
      else if (p == p.parent.left)
        p.parent.left = replacement;
      else
        p.parent.right = replacement;

      // Null out links so they are OK to use by fixAfterDeletion.
      p.left = p.right = p.parent = null;

      // Fix replacement
      if (p.color == BLACK)
        fixAfterDeletion(replacement);
    } else if (p.parent == null) { // return if we are the only node.
      root = null;
    } else { // No children. Use self as phantom replacement and unlink.
      if (p.color == BLACK)
        fixAfterDeletion(p);

      if (p.parent != null) {
        if (p == p.parent.left)
          p.parent.left = null;
        else if (p == p.parent.right)
          p.parent.right = null;
        p.parent = null;
      }
    }
  }

     首先，判斷待刪結(jié)點(diǎn)是否具有兩個(gè)孩子，如果有調(diào)用函數(shù) successor返回后繼結(jié)點(diǎn)，并且替換待刪結(jié)點(diǎn)。對(duì)于這條語句：Entry>K,V< replacement = (p.left != null ? p.left : p.right); ，我們上述的三種情況下replacement的取值值得研究，如果是第一種情況（葉子結(jié)點(diǎn)），那么replacement取值為null，進(jìn)入下面的判斷，第一個(gè)if過，第二個(gè)判斷待刪結(jié)點(diǎn)是否是根結(jié)點(diǎn)（只有根結(jié)點(diǎn)的父結(jié)點(diǎn)為null），如果是說明整個(gè)樹只有一個(gè)結(jié)點(diǎn)，那么直接刪除即可，如果不是根結(jié)點(diǎn)就說明是葉子結(jié)點(diǎn)，此時(shí)將父結(jié)點(diǎn)賦值為null然后刪除即可。 

     對(duì)于第二種情況下（只有一個(gè)孩子結(jié)點(diǎn)時(shí)候），最上面的if語句是不做的，如果那一個(gè)結(jié)點(diǎn)是左孩子 replacement為該結(jié)點(diǎn)，然后將此結(jié)點(diǎn)跳過父結(jié)點(diǎn)掛在待刪結(jié)點(diǎn)的下面，如果那一個(gè)孩子是右孩子，replacement為該結(jié)點(diǎn)，同樣操作。 

     第三種情況（待刪結(jié)點(diǎn)具有兩個(gè)孩子結(jié)點(diǎn)），那肯定執(zhí)行最最上面的if語句中代碼，找到后繼結(jié)點(diǎn)替換待刪結(jié)點(diǎn)（后繼結(jié)點(diǎn)一定沒有左孩子），成功的將問題轉(zhuǎn)換為刪除后繼結(jié)點(diǎn)，又因?yàn)楹罄^結(jié)點(diǎn)一定沒有左孩子，整個(gè)問題已經(jīng)被轉(zhuǎn)換成上述兩種情況了，（假如后繼結(jié)點(diǎn)沒有右孩子就是第一種，假如有就是第二種）所以replacement = p.right，下面分情況處理。刪除方法結(jié)束。 

     小結(jié)一下，刪除結(jié)點(diǎn)難點(diǎn)在于刪除指定鍵值的結(jié)點(diǎn)，主要分為三種情況，葉子結(jié)點(diǎn)，一個(gè)孩子結(jié)點(diǎn)，兩個(gè)孩子結(jié)點(diǎn)。而對(duì)于不同的情況，jdk編寫者將最難的兩個(gè)孩子結(jié)點(diǎn)轉(zhuǎn)換為前兩種較為簡(jiǎn)單的方式，可見大神之作。欽佩。

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

最新評(píng)論