歡迎光臨
每天分享高質量文章

Map 大家族的那點事兒 ( 3 ) :TreeMap

(點擊上方公眾號,可快速關註)


來源:SylvanasSun’s Blog ,

sylvanassun.github.io/2018/03/16/2018-03-16-map_family/

TreeMap

TreeMap是基於紅黑樹(一種自平衡的二叉查找樹)實現的一個保證有序性的Map,在繼承關係結構圖中可以得知TreeMap實現了NavigableMap接口,而該接口又繼承了SortedMap接口,我們先來看看這兩個接口定義了一些什麼功能。

SortedMap

首先是SortedMap接口,實現該接口的實現類應當按照自然排序保證key的有序性,所謂自然排序即是根據key的compareTo()函式(需要實現Comparable接口)或者在建構式中傳入的Comparator實現類來進行排序,集合視圖遍歷元素的順序也應當與key的順序一致。SortedMap接口還定義了以下幾個有效利用有序性的函式:

package java.util;

public interface SortedMap extends Map {

    /**

     * 用於在此Map中對key進行排序的比較器,如果為null,則使用key的compareTo()函式進行比較。

     */

    Comparator super K> comparator();

    /**

     * 傳回一個key的範圍為從fromKey到toKey的區域性視圖(包括fromKey,不包括toKey,包左不包右),

     * 如果fromKey和toKey是相等的,則傳回一個空視圖。

     * 傳回的區域性視圖同樣是此Map的集合視圖,所以對它的操作是會與Map互相影響的。

     */

    SortedMap subMap(K fromKey, K toKey);

    /**

     * 傳回一個嚴格地小於toKey的區域性視圖。

     */

    SortedMap headMap(K toKey);

    /**

     * 傳回一個大於或等於fromKey的區域性視圖。

     */

    SortedMap tailMap(K fromKey);

    /**

     * 傳回當前Map中的第一個key(最小)。

     */

    K firstKey();

    /**

     * 傳回當前Map中的最後一個key(最大)。

     */

    K lastKey();

    Set keySet();

    Collection values();

    Set> entrySet();

}

NavigableMap

然後是SortedMap的子接口NavigableMap,該接口擴展了一些用於導航(Navigation)的方法,像函式lowerEntry(key)會根據傳入的引數key傳回一個小於key的最大的一對鍵值對,例如,我們如下呼叫lowerEntry(6),那麼將傳回key為5的鍵值對,如果沒有key為5,則會傳回key為4的鍵值對,以此類推,直到傳回null(實在找不到的情況下)。

public static void main(String[] args) {

    NavigableMap map = new TreeMap<>();

    for (int i = 0; i < 10; i++)

        map.put(i, i);

 

    assert map.lowerEntry(6).getKey() == 5;

    assert map.lowerEntry(5).getKey() == 4;

    assert map.lowerEntry(0).getKey() == null;

}

NavigableMap定義的都是一些類似於lowerEntry(key)的方法和以逆序、升序排序的集合視圖,這些方法利用有序性實現了相比SortedMap接口更加靈活的操作。

package java.util;

public interface NavigableMap extends SortedMap {

    /**

     * 傳回一個小於指定key的最大的一對鍵值對,如果找不到則傳回null。

     */

    Map.Entry lowerEntry(K key);

    /**

     * 傳回一個小於指定key的最大的一個key,如果找不到則傳回null。

     */

    K lowerKey(K key);

    /**

     * 傳回一個小於或等於指定key的最大的一對鍵值對,如果找不到則傳回null。

     */

    Map.Entry floorEntry(K key);

    /**

     * 傳回一個小於或等於指定key的最大的一個key,如果找不到則傳回null。

     */

    K floorKey(K key);

    /**

     * 傳回一個大於或等於指定key的最小的一對鍵值對,如果找不到則傳回null。

     */

    Map.Entry ceilingEntry(K key);

    /**

     * 傳回一個大於或等於指定key的最小的一個key,如果找不到則傳回null。

     */

    K ceilingKey(K key);

    /**

     * 傳回一個大於指定key的最小的一對鍵值對,如果找不到則傳回null。

     */

    Map.Entry higherEntry(K key);

    /**

     * 傳回一個大於指定key的最小的一個key,如果找不到則傳回null。

     */

    K higherKey(K key);

    /**

     * 傳回該Map中最小的鍵值對,如果Map為空則傳回null。

     */

    Map.Entry firstEntry();

    /**

     * 傳回該Map中最大的鍵值對,如果Map為空則傳回null。

     */

    Map.Entry lastEntry();

    /**

     * 傳回並刪除該Map中最小的鍵值對,如果Map為空則傳回null。

     */

    Map.Entry pollFirstEntry();

    /**

     * 傳回並刪除該Map中最大的鍵值對,如果Map為空則傳回null。

     */

    Map.Entry pollLastEntry();

    /**

     * 傳回一個以當前Map降序(逆序)排序的集合視圖

     */

    NavigableMap descendingMap();

    /**

     * 傳回一個包含當前Map中所有key的集合視圖,該視圖中的key以升序(正序)排序。

     */

    NavigableSet navigableKeySet();

    /**

     * 傳回一個包含當前Map中所有key的集合視圖,該視圖中的key以降序(逆序)排序。

     */

    NavigableSet descendingKeySet();

    /**

     * 與SortedMap.subMap基本一致,區別在於多的兩個引數fromInclusive和toInclusive,

     * 它們代表是否包含from和to,如果fromKey與toKey相等,並且fromInclusive與toInclusive

     * 都為true,那麼不會傳回空集合。

     */

    NavigableMap subMap(K fromKey, boolean fromInclusive,

                             K toKey,   boolean toInclusive);

    /**

     * 傳回一個小於或等於(inclusive為true的情況下)toKey的區域性視圖。

     */

    NavigableMap headMap(K toKey, boolean inclusive);

    /**

     * 傳回一個大於或等於(inclusive為true的情況下)fromKey的區域性視圖。

     */

    NavigableMap tailMap(K fromKey, boolean inclusive);

    /**

     * 等價於subMap(fromKey, true, toKey, false)。

     */

    SortedMap subMap(K fromKey, K toKey);

    /**

     * 等價於headMap(toKey, false)。

     */

    SortedMap headMap(K toKey);

    /**

     * 等價於tailMap(fromKey, true)。

     */

    SortedMap tailMap(K fromKey);

}

NavigableMap接口相對於SortedMap接口來說靈活了許多,正因為TreeMap也實現了該接口,所以在需要資料有序而且想靈活地訪問它們的時候,使用TreeMap就非常合適了。

紅黑樹

上文我們提到TreeMap的內部實現基於紅黑樹,而紅黑樹又是二叉查找樹的一種。二叉查找樹是一種有序的樹形結構,優勢在於查找、插入的時間複雜度只有O(log n),特性如下:

  • 任意節點最多含有兩個子節點。

  • 任意節點的左、右節點都可以看做為一棵二叉查找樹。

  • 如果任意節點的左子樹不為空,那麼左子樹上的所有節點的值均小於它的根節點的值。

  • 如果任意節點的右子樹不為空,那麼右子樹上的所有節點的值均大於它的根節點的值。

  • 任意節點的key都是不同的。

儘管二叉查找樹看起來很美好,但事與願違,二叉查找樹在極端情況下會變得並不是那麼有效率,假設我們有一個有序的整數序列:1,2,3,4,5,6,7,8,9,10,…,如果把這個序列按順序全部插入到二叉查找樹時會發生什麼呢?二叉查找樹會產生傾斜,序列中的每一個元素都大於它的根節點(前一個元素),左子樹永遠是空的,那麼這棵二叉查找樹就跟一個普通的鏈表沒什麼區別了,查找操作的時間複雜度只有O(n)。

為瞭解決這個問題需要引入自平衡的二叉查找樹,所謂自平衡,即是在樹結構將要傾斜的情況下進行修正,這個修正操作被稱為旋轉,通過旋轉操作可以讓樹趨於平衡。

紅黑樹是平衡二叉查找樹的一種實現,它的名字來自於它的子節點是著色的,每個子節點非黑即紅,由於只有兩種顏色(兩種狀態),一般使用boolean來表示,下麵為TreeMap中實現的Entry,它代表紅黑樹中的一個節點:

// Red-black mechanics

private static final boolean RED   = false;

private static final boolean BLACK = true;

/**

 * Node in the Tree.  Doubles as a means to pass key-value pairs back to

 * user (see Map.Entry).

 */

static final class Entry implements Map.Entry {

    K key;

    V value;

    Entry left;

    Entry right;

    Entry parent;

    boolean color = BLACK;

    /**

     * Make a new cell with given key, value, and parent, and with

     * {@code null} child links, and BLACK color.

     */

    Entry(K key, V value, Entry parent) {

        this.key = key;

        this.value = value;

        this.parent = parent;

    }

    /**

     * Returns the key.

     *

     * @return the key

     */

    public K getKey() {

        return key;

    }

    /**

     * Returns the value associated with the key.

     *

     * @return the value associated with the key

     */

    public V getValue() {

        return value;

    }

    /**

     * Replaces the value currently associated with the key with the given

     * value.

     *

     * @return the value associated with the key before this method was

     *         called

     */

    public V setValue(V value) {

        V oldValue = this.value;

        this.value = value;

        return oldValue;

    }

    public boolean equals(Object o) {

        if (!(o instanceof Map.Entry))

            return false;

        Map.Entry,?> e = (Map.Entry,?>)o;

        return valEquals(key,e.getKey()) && valEquals(value,e.getValue());

    }

    public int hashCode() {

        int keyHash = (key==null ? 0 : key.hashCode());

        int valueHash = (value==null ? 0 : value.hashCode());

        return keyHash ^ valueHash;

    }

    public String toString() {

        return key + “=” + value;

    }

}

任何平衡二叉查找樹的查找操作都是與二叉查找樹是一樣的,因為查找操作並不會影響樹的結構,也就不需要進行修正,代碼如下:

public V get(Object key) {

    Entry p = getEntry(key);

    return (p==null ? null : p.value);

}

final Entry getEntry(Object key) {

    // 使用Comparator進行比較

    if (comparator != null)

        return getEntryUsingComparator(key);

    if (key == null)

        throw new NullPointerException();

    @SuppressWarnings(“unchecked”)

        Comparable super K> k = (Comparable super K>) key;

    Entry p = root;

    // 從根節點開始,不斷比較key的大小進行查找

    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; // 沒有相等的key,傳回null

}

而插入和刪除操作與平衡二叉查找樹的細節是息息相關的,關於紅黑樹的實現細節,我之前寫過的一篇博客紅黑樹的那點事兒已經講的很清楚了,對這方面不瞭解的讀者建議去閱讀一下,就不在這裡重覆敘述了。

集合視圖

最後看一下TreeMap的集合視圖的實現,集合視圖一般都是實現了一個封裝了當前實體的類,所以對集合視圖的修改本質上就是在修改當前實體,TreeMap也不例外。

TreeMap的headMap()、tailMap()以及subMap()函式都傳回了一個靜態內部類AscendingSubMap,從名字上也能猜出來,為了支持倒序,肯定也還有一個DescendingSubMap,它們都繼承於NavigableSubMap,一個繼承AbstractMap並實現了NavigableMap的抽象類:

  abstract static class NavigableSubMap extends AbstractMap

      implements NavigableMap, java.io.Serializable {

      private static final long serialVersionUID = -2102997345730753016L;

      final TreeMap m;

      /**

       * (fromStart, lo, loInclusive) 與 (toEnd, hi, hiInclusive)代表了兩個三元組,

       * 如果fromStart為true,那麼範圍的下限(絕對)為map(被封裝的TreeMap)的起始key,

       * 其他值將被忽略。

       * 如果loInclusive為true,lo將會被包含在範圍內,否則lo是在範圍外的。

       * toEnd與hiInclusive與上述邏輯相似,只不過考慮的是上限。

       */

      final K lo, hi;

      final boolean fromStart, toEnd;

      final boolean loInclusive, hiInclusive;

      NavigableSubMap(TreeMap m,

                      boolean fromStart, K lo, boolean loInclusive,

                      boolean toEnd,     K hi, boolean hiInclusive) {

          if (!fromStart && !toEnd) {

              if (m.compare(lo, hi) > 0)

                  throw new IllegalArgumentException(“fromKey > toKey”);

          } else {

              if (!fromStart) // type check

                  m.compare(lo, lo);

              if (!toEnd)

                  m.compare(hi, hi);

          }

          this.m = m;

          this.fromStart = fromStart;

          this.lo = lo;

          this.loInclusive = loInclusive;

          this.toEnd = toEnd;

          this.hi = hi;

          this.hiInclusive = hiInclusive;

      }

      // internal utilities

      final boolean tooLow(Object key) {

          if (!fromStart) {

              int c = m.compare(key, lo);

              // 如果key小於lo,或等於lo(需要lo不包含在範圍內)

              if (c < 0 || (c == 0 && !loInclusive))

                  return true;

          }

          return false;

      }

      final boolean tooHigh(Object key) {

          if (!toEnd) {

              int c = m.compare(key, hi);

              // 如果key大於hi,或等於hi(需要hi不包含在範圍內)

              if (c > 0 || (c == 0 && !hiInclusive))

                  return true;

          }

          return false;

      }

      final boolean inRange(Object key) {

          return !tooLow(key) && !tooHigh(key);

      }

      final boolean inClosedRange(Object key) {

          return (fromStart || m.compare(key, lo) >= 0)

              && (toEnd || m.compare(hi, key) >= 0);

      }

      // 判斷key是否在該視圖的範圍之內

      final boolean inRange(Object key, boolean inclusive) {

          return inclusive ? inRange(key) : inClosedRange(key);

      }

      /*

       * 以abs開頭的函式為關係操作的絕對版本。

       */

      /*

       * 獲得最小的鍵值對:

       * 如果fromStart為true,那麼直接傳回當前map實體的第一個鍵值對即可,

       * 否則,先判斷lo是否包含在範圍內,

       * 如果是,則獲得當前map實體中大於或等於lo的最小的鍵值對,

       * 如果不是,則獲得當前map實體中大於lo的最小的鍵值對。

       * 如果得到的結果e超過了範圍的上限,那麼傳回null。

       */

      final TreeMap.Entry absLowest() {

          TreeMap.Entry e =

              (fromStart ?  m.getFirstEntry() :

               (loInclusive ? m.getCeilingEntry(lo) :

                              m.getHigherEntry(lo)));

          return (e == null || tooHigh(e.key)) ? null : e;

      }

      // 與absLowest()相反

      final TreeMap.Entry absHighest() {

          TreeMap.Entry e =

              (toEnd ?  m.getLastEntry() :

               (hiInclusive ?  m.getFloorEntry(hi) :

                               m.getLowerEntry(hi)));

          return (e == null || tooLow(e.key)) ? null : e;

      }

      // 下麵的邏輯就都很簡單了,註意會先判斷key是否越界,

      // 如果越界就傳回絕對值。

      final TreeMap.Entry absCeiling(K key) {

          if (tooLow(key))

              return absLowest();

          TreeMap.Entry e = m.getCeilingEntry(key);

          return (e == null || tooHigh(e.key)) ? null : e;

      }

      final TreeMap.Entry absHigher(K key) {

          if (tooLow(key)) 

              return absLowest();

          TreeMap.Entry e = m.getHigherEntry(key);

          return (e == null || tooHigh(e.key)) ? null : e;

      }

      final TreeMap.Entry absFloor(K key) {

          if (tooHigh(key))

              return absHighest();

          TreeMap.Entry e = m.getFloorEntry(key);

          return (e == null || tooLow(e.key)) ? null : e;

      }

      final TreeMap.Entry absLower(K key) {

          if (tooHigh(key))

              return absHighest();

          TreeMap.Entry e = m.getLowerEntry(key);

          return (e == null || tooLow(e.key)) ? null : e;

      }

      /** 傳回升序遍歷的絕對上限 */

      final TreeMap.Entry absHighFence() {

          return (toEnd ? null : (hiInclusive ?

                                  m.getHigherEntry(hi) :

                                  m.getCeilingEntry(hi)));

      }

      /** 傳回降序遍歷的絕對下限 */

      final TreeMap.Entry absLowFence() {

          return (fromStart ? null : (loInclusive ?

                                      m.getLowerEntry(lo) :

                                      m.getFloorEntry(lo)));

      }

      // 剩下的就是實現NavigableMap的方法以及一些抽象方法

// 和NavigableSubMap中的集合視圖函式。

      // 大部分操作都是靠當前實體map的方法和上述用於判斷邊界的方法提供支持

      …..

  }

一個區域性視圖最重要的是要能夠判斷出傳入的key是否屬於該視圖的範圍內,在上面的代碼中可以發現NavigableSubMap提供了非常多的輔助函式用於判斷範圍,接下來我們看看NavigableSubMap的迭代器是如何實現的:

/**

 * Iterators for SubMaps

 */

abstract class SubMapIterator implements Iterator {

    TreeMap.Entry lastReturned;

    TreeMap.Entry next;

    final Object fenceKey;

    int expectedModCount;

    SubMapIterator(TreeMap.Entry first,

                   TreeMap.Entry fence) {

        expectedModCount = m.modCount; 

        lastReturned = null;

        next = first;

        // UNBOUNDED是一個虛擬值(一個Object物件),表示無邊界。

        fenceKey = fence == null ? UNBOUNDED : fence.key;

    }

    // 只要next不為null並且沒有超過邊界

    public final boolean hasNext() {

        return next != null && next.key != fenceKey;

    }

    final TreeMap.Entry nextEntry() {

        TreeMap.Entry e = next;

        // 已經遍歷到頭或者越界了

        if (e == null || e.key == fenceKey)

            throw new NoSuchElementException();

        // modCount是一個記錄運算元的計數器

        // 如果與expectedModCount不一致

        // 則代表當前map實體在遍歷過程中已被修改過了(從其他執行緒)

        if (m.modCount != expectedModCount)

            throw new ConcurrentModificationException();

        // 向後移動next指標

        // successor()傳回指定節點的繼任者

        // 它是節點e的右子樹的最左節點

        // 也就是比e大的最小的節點

        // 如果e沒有右子樹,則會試圖向上尋找

        next = successor(e);

        lastReturned = e; // 記錄最後傳回的節點

        return e;

    }

    final TreeMap.Entry prevEntry() {

        TreeMap.Entry e = next;

        if (e == null || e.key == fenceKey)

            throw new NoSuchElementException();

        if (m.modCount != expectedModCount)

            throw new ConcurrentModificationException();

        // 向前移動next指標

        // predecessor()傳回指定節點的前任

        // 它與successor()邏輯相反。

        next = predecessor(e);

        lastReturned = e;

        return e;

    }

    final void removeAscending() {

        if (lastReturned == null)

            throw new IllegalStateException();

        if (m.modCount != expectedModCount)

            throw new ConcurrentModificationException();

        // 被刪除的節點被它的繼任者取代

        // 執行完刪除後,lastReturned實際指向了它的繼任者

        if (lastReturned.left != null && lastReturned.right != null)

            next = lastReturned;

        m.deleteEntry(lastReturned);

        lastReturned = null;

        expectedModCount = m.modCount;

    }

    final void removeDescending() {

        if (lastReturned == null)

            throw new IllegalStateException();

        if (m.modCount != expectedModCount)

            throw new ConcurrentModificationException();

        m.deleteEntry(lastReturned);

        lastReturned = null;

        expectedModCount = m.modCount;

    }

}

final class SubMapEntryIterator extends SubMapIterator> {

    SubMapEntryIterator(TreeMap.Entry first,

                        TreeMap.Entry fence) {

        super(first, fence);

    }

    public Map.Entry next() {

        return nextEntry();

    }

    public void remove() {

        removeAscending();

    }

}

final class DescendingSubMapEntryIterator extends SubMapIterator> {

    DescendingSubMapEntryIterator(TreeMap.Entry last,

                                  TreeMap.Entry fence) {

        super(last, fence);

    }

    public Map.Entry next() {

        return prevEntry();

    }

    public void remove() {

        removeDescending();

    }

}

到目前為止,我們已經針對集合視圖討論了許多,想必大家也能夠理解集合視圖的概念了,由於SortedMap與NavigableMap的緣故,TreeMap中的集合視圖是非常多的,包括各種區域性視圖和不同排序的視圖,有興趣的讀者可以自己去看看原始碼,後面的內容不會再對集合視圖進行過多的解釋了。

系列

【關於投稿】


如果大家有原創好文投稿,請直接給公號發送留言。


① 留言格式:
【投稿】+《 文章標題》+ 文章鏈接

② 示例:
【投稿】《不要自稱是程式員,我十多年的 IT 職場總結》:http://blog.jobbole.com/94148/

③ 最後請附上您的個人簡介哈~


看完本文有收穫?請轉發分享給更多人

關註「ImportNew」,提升Java技能

赞(0)

分享創造快樂