一文帶你全面深入了解TreeMap-創新互聯

概述

TreeMap是Map家族中的一員，也是用來存放key-value鍵值對的。平時在工作中使用的可能并不多，它大的特點是遍歷時是有順序的，根據key的排序規則來，那么它具體是如何使用，又是怎么實現的呢？本文基于jdk8做一個講解。

創新互聯公司2013年至今，先為文成等服務建站，文成等地企業，進行企業商務咨詢服務。為文成企業網站制作PC+手機+微官網三網同步一站式服務解決您的所有建站問題。TreeMap介紹

TreeMap是一個基于key有序的key value散列表。

map根據其鍵的自然順序排序，或者根據map創建時提供的Comparator排序
不是線程安全的
key 不可以存入null
底層是基于紅黑樹實現的

以上是TreeMap的類結構圖：

實現了NavigableMap接口，NavigableMap又實現了Map接口，提供了導航相關的方法。
繼承了AbstractMap，該方法實現Map操作的骨干邏輯。
實現了Cloneable接口，標記該類支持clone方法復制
實現了Serializable接口，標記該類支持序列化

構造方法

TreeMap()

說明：使用鍵的自然排序構造一個新的空樹映射。

TreeMap(Comparatorcomparator)

說明：構造一個新的空樹映射，根據給定的比較器排序。

TreeMap(Mapm)

說明：構造一個新的樹映射，包含與給定映射相同的映射，按照鍵的自然順序排序。

TreeMap(SortedMapm)

說明：構造一個新的樹映射，包含相同的映射，并使用與指定排序映射相同的順序。

關鍵方法

這邊主要講解下NavigableMap和SortedMap提供的一些方法，Map相關的方法大家應該都很熟悉了。

SortedMap接口：

Comparatorcomparator()

返回用于排序此映射中的鍵的比較器，如果此映射使用其鍵的自然排序，則返回null。

Set>entrySet()

返回此映射中包含的映射的Set視圖。

K firstKey()

返回當前映射中的第一個(最低)鍵。

K lastKey()

返回當前映射中的最后(最高)鍵。

NavigableMap接口：

Map.EntryceilingEntry(K key)

返回與大于或等于給定鍵的最小鍵相關聯的鍵值映射，如果沒有這樣的鍵則返回null。

K ceilingKey(K key)

返回大于或等于給定鍵的最小鍵，如果沒有這樣的鍵，則返回null。

NavigableMapdescendingMap()

返回此映射中包含的映射的倒序視圖。

Map.EntryfirstEntry()

返回與該映射中最小的鍵關聯的鍵值映射，如果映射為空，則返回null。

Map.EntryfloorEntry(K key)

返回與小于或等于給定鍵的大鍵相關聯的鍵值映射，如果沒有這樣的鍵則返回null。

SortedMapheadMap(K toKey)

返回該映射中鍵嚴格小于toKey的部分的視圖。

Map.EntryhigherEntry(K key)

返回與嚴格大于給定鍵的最小鍵關聯的鍵值映射，如果沒有這樣的鍵，則返回null。

Map.EntrylastEntry()

返回與此映射中大鍵關聯的鍵值映射，如果映射為空，則返回null。

Map.EntrylowerEntry(K key)

返回與嚴格小于給定鍵的大鍵關聯的鍵值映射，如果沒有這樣的鍵，則返回null。

Map.EntrypollFirstEntry()

刪除并返回與該映射中最小的鍵關聯的鍵值映射，如果映射為空，則返回null。

Map.EntrypollLastEntry()

刪除并返回與此映射中大鍵關聯的鍵值映射，如果映射為空，則返回null。

SortedMapsubMap(K fromKey, K toKey)

返回該映射中鍵范圍從fromKey(包含)到toKey(獨占)的部分的視圖。

SortedMaptailMap(K fromKey)

返回該映射中鍵大于或等于fromKey的部分的視圖。

使用案例

驗證順序性

@Test
    public void test1() {
        MaptreeMap = new TreeMap<>();
        treeMap.put(16, "a");
        treeMap.put(1, "b");
        treeMap.put(4, "c");
        treeMap.put(3, "d");
        treeMap.put(8, "e");
        // 遍歷
        System.out.println("默認排序：");
        treeMap.forEach((key, value) ->{
            System.out.println("key: " + key + ", value: " + value);
        });

        // 構造方法傳入比較器
        Maptree2Map = new TreeMap<>((o1, o2) ->o2 - o1);
        tree2Map.put(16, "a");
        tree2Map.put(1, "b");
        tree2Map.put(4, "c");
        tree2Map.put(3, "d");
        tree2Map.put(8, "e");
        // 遍歷
        System.out.println("倒序排序：");
        tree2Map.forEach((key, value) ->{
            System.out.println("key: " + key + ", value: " + value);
        });
    }

運行結果：

驗證不能存儲null

@Test
    public void test2() {
        MaptreeMap = new TreeMap<>();
        treeMap.put(null, "a");
    }

運行結果：

驗證NavigableMap相關方法

@Test
    public void test3() {
        NavigableMaptreeMap = new TreeMap<>();
        treeMap.put(16, "a");
        treeMap.put(1, "b");
        treeMap.put(4, "c");
        treeMap.put(3, "d");
        treeMap.put(8, "e");

        // 獲取大于等于5的key
        Integer ceilingKey = treeMap.ceilingKey(5);
        System.out.println("ceilingKey 5 is " + ceilingKey);

        // 獲取大的key
        Integer lastKey = treeMap.lastKey();
        System.out.println("lastKey is " + lastKey);
    }

運行結果：

核心機制實現原理

大家有想過TreeMap的底層是怎么實現的嗎，是如何維護key的順序呢？答案就是基于紅黑樹實現的。

那什么是紅黑樹呢？我們在這里簡單的認識一下，了解一下紅黑樹的特點：紅黑樹是一顆自平衡的排序二叉樹。我們就先從二叉樹開始說起。

二叉樹

二叉樹很容易理解，就是一棵樹分倆叉。

上面這顆就是一顆最普通的二叉樹。但是你會發現看起來不那么美觀，因為你以H為根節點，發現左右兩邊高低不平衡，高度相差達到了2。于是出現了平衡二叉樹，使得左右兩邊高低差不多。

平衡二叉樹

這下子應該能看到，不管是從任何一個字母為根節點，左右兩邊的深度差不了2，最多是1。這就是平衡二叉樹。不過好景不長，有一天，突然要把字母變成數字，還要保持這種特性怎么辦呢？于是又出現了平衡二叉排序樹。

平衡二叉排序樹

不管是從長相（平衡），還是從規律（排序）感覺這棵樹超級完美。但是有一個問題，那就是在增加刪除節點的時候，你要時刻去讓這棵樹保持平衡，需要做太多的工作了，旋轉的次數超級多，于是乎出現了紅黑樹。

紅黑樹

這就是傳說中的紅黑樹，和平衡二叉排序樹的區別就是每個節點涂上了顏色，他有下列五條性質：

每個節點都只能是紅色或者黑色
根節點是黑色
每個葉節點（NIL節點，空節點）是黑色的。
如果一個結點是紅的，則它兩個子節點都是黑的。也就是說在一條路徑上不能出現相鄰的兩個紅色結點。
從任一節點到其每個葉子的所有路徑都包含相同數目的黑色節點。

這些性質有什么優點呢？就是插入效率超級高。因為在插入一個元素的時候，最多只需三次旋轉，O(1)的復雜度，但是有一點需要說明他的查詢效率略微遜色于平衡二叉樹，因為他比平衡二叉樹會稍微不平衡最多一層，也就是說紅黑樹的查詢性能只比相同內容的avl樹最多多一次比較。如何去旋轉呢？如下圖所示。

首先是左旋：

然后是右旋：

紅黑樹更詳細的內容可以參考這篇文章：segmentfault.com/a/119000001…

源碼解析成員變量

//這是一個比較器，方便插入查找元素等操作
private final Comparatorcomparator;
//紅黑樹的根節點：每個節點是一個Entry
private transient Entryroot;
//集合元素數量
private transient int size = 0;
//集合修改的記錄
private transient int modCount = 0;

comparator是一個排序器，作為key的排序規則
root是紅黑樹的根節點，說明的確底層用的紅黑樹作為數據結構。

static final class Entryimplements Map.Entry{
        K key;
        V value;
     	//左子樹
        Entryleft;
     	//右子樹
        Entryright;
     	//父節點
        Entryparent;
     	//每個節點的顏色：紅黑樹屬性。
        boolean color = BLACK;
        Entry(K key, V value, Entryparent) {
            this.key = key;
            this.value = value;
            this.parent = parent;
        }
        public K getKey() {
            return key;
        }
        public V getValue() {
            return value;
        }
        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.Entrye = (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;
        }
    }

查找get方法

TreeMap基于紅黑樹實現，而紅黑樹是一種自平衡二叉查找樹，所以 TreeMap 的查找操作流程和二叉查找樹一致。二叉樹的查找流程是這樣的，先將目標值和根節點的值進行比較，如果目標值小于根節點的值，則再和根節點的左孩子進行比較。如果目標值大于根節點的值，則繼續和根節點的右孩子比較。在查找過程中，如果目標值和二叉樹中的某個節點值相等，則返回 true，否則返回 false。TreeMap 查找和此類似，只不過在 TreeMap 中，節點（Entry）存儲的是鍵值對。在查找過程中，比較的是鍵的大小，返回的是值，如果沒找到，則返回null。TreeMap 中的查找方法是get。

public V get(Object key) {
        //調用 getEntry方法查找
        Entryp = getEntry(key);
        return (p==null ? null : p. value);
}

final EntrygetEntry(Object key) {
    / 如果比較器為空，只是用key作為比較器查詢
    if (comparator != null) 
        return getEntryUsingComparator(key);
    if (key == null)
        throw new NullPointerException();
    Comparablek = (Comparable) key;
    // 取得root節點
    Entryp = root;
   //核心來了：從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;
    }

插入put方法

我們來看下關鍵的插入方法，在插入時候是如何維護key的。

public V put(K key, V value) {
        Entryt = root;
       // 1.如果根節點為 null，將新節點設為根節點
        if (t == null) {
            compare(key, key); // type (and possibly null) check

            root = new Entry<>(key, value, null);
            size = 1;
            modCount++;
            return null;
        }
      //如果root不為null，說明已存在元素 
        int cmp;
        Entryparent;
        // split comparator and comparable paths
        Comparatorcpr = comparator;
    //如果比較器不為null 則使用比較器
        if (cpr != null) {
            //找到元素的插入位置
            do {
                parent = t;
                cmp = cpr.compare(key, t.key);
                 //當前key小于節點key 向左子樹查找
                if (cmp< 0)
                    t = t.left;
                    //當前key大于節點key 向右子樹查找
                else if (cmp >0)
                    t = t.right;
                else
                    //相等的情況下 直接更新節點值
                    return t.setValue(value);
            } while (t != null);
        }
            //如果比較器為null 則使用默認比較器
        else {
            //如果key為null  則拋出異常
            if (key == null)
                throw new NullPointerException();
            @SuppressWarnings("unchecked")
                Comparablek = (Comparable) 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);
        }
        Entrye = new Entry<>(key, value, parent);
      //根據比較結果決定插入到左子樹還是右子樹
        if (cmp< 0)
            parent.left = e;
        else
            parent.right = e;
    //保持紅黑樹性質，進行紅黑樹的旋轉等操作
        fixAfterInsertion(e);
        size++;
        modCount++;
        return null;
    }

比較關鍵的就是fixAfterInsertion方法，看懂這個方法需要你對紅黑樹的機制比較了解。

private void fixAfterInsertion(Entryx) {
    // 將新插入節點的顏色設置為紅色
    x. color = RED;
    // while循環，保證新插入節點x不是根節點或者新插入節點x的父節點不是紅色（這兩種情況不需要調整）
    while (x != null && x != root && x. parent.color == RED) {
        // 如果新插入節點x的父節點是祖父節點的左孩子
        if (parentOf(x) == leftOf(parentOf (parentOf(x)))) {
            // 取得新插入節點x的叔叔節點
            Entryy = rightOf(parentOf (parentOf(x)));
            // 如果新插入x的父節點是紅色
            if (colorOf(y) == RED) {
                // 將x的父節點設置為黑色
                setColor(parentOf (x), BLACK);
                // 將x的叔叔節點設置為黑色
                setColor(y, BLACK);
                // 將x的祖父節點設置為紅色
                setColor(parentOf (parentOf(x)), RED);
                // 將x指向祖父節點，如果x的祖父節點的父節點是紅色，按照上面的步奏繼續循環
                x = parentOf(parentOf (x));
            } else {
                // 如果新插入x的叔叔節點是黑色或缺少，且x的父節點是祖父節點的右孩子
                if (x == rightOf( parentOf(x))) {
                    // 左旋父節點
                    x = parentOf(x);
                    rotateLeft(x);
                }
                // 如果新插入x的叔叔節點是黑色或缺少，且x的父節點是祖父節點的左孩子
                // 將x的父節點設置為黑色
                setColor(parentOf (x), BLACK);
                // 將x的祖父節點設置為紅色
                setColor(parentOf (parentOf(x)), RED);
                // 右旋x的祖父節點
                rotateRight( parentOf(parentOf (x)));
            }
        } else { // 如果新插入節點x的父節點是祖父節點的右孩子和上面的相似
            Entryy = leftOf(parentOf (parentOf(x)));
            if (colorOf(y) == RED) {
                setColor(parentOf (x), BLACK);
                setColor(y, BLACK);
                setColor(parentOf (parentOf(x)), RED);
                x = parentOf(parentOf (x));
            } else {
                if (x == leftOf( parentOf(x))) {
                    x = parentOf(x);
                    rotateRight(x);
                }
                setColor(parentOf (x), BLACK);
                setColor(parentOf (parentOf(x)), RED);
                rotateLeft( parentOf(parentOf (x)));
            }
        }
    }
    // 最后將根節點設置為黑色
    root.color = BLACK;
}

刪除remove方法

刪除remove是最復雜的方法。

public V remove(Object key) {
        // 根據key查找到對應的節點對象
        Entryp = getEntry(key);
        if (p == null)
            return null;

        // 記錄key對應的value，供返回使用
        V oldValue = p. value;
        // 刪除節點
        deleteEntry(p);
        return oldValue;
}

private void deleteEntry(Entryp) {
        modCount++;
        //元素個數減一
        size--;
        // 如果被刪除的節點p的左孩子和右孩子都不為空，則查找其替代節
        if (p.left != null && p. right != null) {
            // 查找p的替代節點
            Entrys = successor (p);
            p. key = s.key ;
            p. value = s.value ;
            p = s;
        }
        Entryreplacement = (p. left != null ? p.left : p. right);
        if (replacement != null) { 
            // 將p的父節點拷貝給替代節點
            replacement. parent = p.parent ;
            // 如果替代節點p的父節點為空，也就是p為跟節點，則將replacement設置為根節點
            if (p.parent == null)
                root = replacement;
            // 如果替代節點p是其父節點的左孩子，則將replacement設置為其父節點的左孩子
            else if (p == p.parent. left)
                p. parent.left   = replacement;
            // 如果替代節點p是其父節點的左孩子，則將replacement設置為其父節點的右孩子
            else
                p. parent.right = replacement;
            // 將替代節點p的left、right、parent的指針都指向空
            p. left = p.right = p.parent = null;
            // 如果替代節點p的顏色是黑色，則需要調整紅黑樹以保持其平衡
            if (p.color == BLACK)
                fixAfterDeletion(replacement);
        } else if (p.parent == null) { // return if we are the only node.
            // 如果要替代節點p沒有父節點，代表p為根節點，直接刪除即可
            root = null;
        } else {
            // 如果p的顏色是黑色，則調整紅黑樹
            if (p.color == BLACK)
                fixAfterDeletion(p);
            // 下面刪除替代節點p
            if (p.parent != null) {
                // 解除p的父節點對p的引用
                if (p == p.parent .left)
                    p. parent.left = null;
                else if (p == p.parent. right)
                    p. parent.right = null;
                // 解除p對p父節點的引用
                p. parent = null;
            }
        }
    }

最終還是落到了對紅黑樹節點的刪除上，需要維持紅黑樹的特性，做一系列的工作。

你是否還在尋找穩定的海外服務器提供商？創新互聯www.cdcxhl.cn海外機房具備T級流量清洗系統配攻擊溯源，準確流量調度確保服務器高可用性，企業級服務器適合批量采購，新人活動首月15元起，快前往官網查看詳情吧

本文題目：一文帶你全面深入了解TreeMap-創新互聯
本文網址：http://m.jcarcd.cn/article/cdgesj.html

精品专区-精品自拍9-精品自拍三级乱伦-精品自拍视频-精品自拍视频曝光-精品自拍小视频

NEWS

網站建設資訊

一文帶你全面深入了解TreeMap-創新互聯

其他資訊