一文帶你深入了解Java?TreeMap

更新時(shí)間：2022年09月13日 09:21:36 作者：JAVA旭陽(yáng)

TreeMap是Map家族中的一員，也是用來(lái)存放key-value鍵值對(duì)的。平時(shí)在工作中使用的可能并不多。本文將基于jdk8對(duì)其做一個(gè)講解，感興趣的可以了解一下

概述

TreeMap是Map家族中的一員，也是用來(lái)存放key-value鍵值對(duì)的。平時(shí)在工作中使用的可能并不多，它最大的特點(diǎn)是遍歷時(shí)是有順序的，根據(jù)key的排序規(guī)則來(lái)，那么它具體是如何使用，又是怎么實(shí)現(xiàn)的呢？本文基于jdk8做一個(gè)講解。

TreeMap介紹

TreeMap是一個(gè)基于key有序的key value散列表。

map根據(jù)其鍵的自然順序排序，或者根據(jù)map創(chuàng)建時(shí)提供的Comparator排序
不是線程安全的
key 不可以存入null
底層是基于紅黑樹(shù)實(shí)現(xiàn)的

以上是TreeMap的類結(jié)構(gòu)圖：

實(shí)現(xiàn)了NavigableMap接口，NavigableMap又實(shí)現(xiàn)了Map接口，提供了導(dǎo)航相關(guān)的方法。
繼承了AbstractMap，該方法實(shí)現(xiàn)Map操作的骨干邏輯。
實(shí)現(xiàn)了Cloneable接口，標(biāo)記該類支持clone方法復(fù)制
實(shí)現(xiàn)了Serializable接口，標(biāo)記該類支持序列化

構(gòu)造方法

TreeMap()

說(shuō)明：使用鍵的自然排序構(gòu)造一個(gè)新的空樹(shù)映射。

TreeMap(Comparator<? super K> comparator)

說(shuō)明：構(gòu)造一個(gè)新的空樹(shù)映射，根據(jù)給定的比較器排序。

TreeMap(Map<? extends K,? extends V> m)

說(shuō)明：構(gòu)造一個(gè)新的樹(shù)映射，包含與給定映射相同的映射，按照鍵的自然順序排序。

TreeMap(SortedMap<K,? extends V> m)

說(shuō)明：構(gòu)造一個(gè)新的樹(shù)映射，包含相同的映射，并使用與指定排序映射相同的順序。

關(guān)鍵方法

這邊主要講解下NavigableMap和SortedMap提供的一些方法，Map相關(guān)的方法大家應(yīng)該都很熟悉了。

SortedMap接口：

Comparator<? super K> comparator()

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

Set<Map.Entry<K,V>> entrySet()

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

K firstKey()

返回當(dāng)前映射中的第一個(gè)(最低)鍵。

K lastKey()

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

NavigableMap接口：

Map.Entry<K,V> ceilingEntry(K key)

返回與大于或等于給定鍵的最小鍵相關(guān)聯(lián)的鍵值映射，如果沒(méi)有這樣的鍵則返回null。

K ceilingKey(K key)

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

NavigableMap<K,V> descendingMap()

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

Map.Entry<K,V> firstEntry()

返回與該映射中最小的鍵關(guān)聯(lián)的鍵值映射，如果映射為空，則返回null。

Map.Entry<K,V> floorEntry(K key)

返回與小于或等于給定鍵的最大鍵相關(guān)聯(lián)的鍵值映射，如果沒(méi)有這樣的鍵則返回null。

SortedMap<K,V> headMap(K toKey)

返回該映射中鍵嚴(yán)格小于toKey的部分的視圖。

Map.Entry<K,V> higherEntry(K key)

返回與嚴(yán)格大于給定鍵的最小鍵關(guān)聯(lián)的鍵值映射，如果沒(méi)有這樣的鍵，則返回null。

Map.Entry<K,V> lastEntry()

返回與此映射中最大鍵關(guān)聯(lián)的鍵值映射，如果映射為空，則返回null。

Map.Entry<K,V> lowerEntry(K key)

返回與嚴(yán)格小于給定鍵的最大鍵關(guān)聯(lián)的鍵值映射，如果沒(méi)有這樣的鍵，則返回null。

Map.Entry<K,V> pollFirstEntry()

刪除并返回與該映射中最小的鍵關(guān)聯(lián)的鍵值映射，如果映射為空，則返回null。

Map.Entry<K,V> pollLastEntry()

刪除并返回與此映射中最大鍵關(guān)聯(lián)的鍵值映射，如果映射為空，則返回null。

SortedMap<K,V> subMap(K fromKey, K toKey)

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

SortedMap<K,V> tailMap(K fromKey)

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

使用案例

驗(yàn)證順序性

@Test
    public void test1() {
        Map<Integer, String> treeMap = 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("默認(rèn)排序：");
        treeMap.forEach((key, value) -> {
            System.out.println("key: " + key + ", value: " + value);
        });

        // 構(gòu)造方法傳入比較器
        Map<Integer, String> tree2Map = 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);
        });
    }

運(yùn)行結(jié)果：

驗(yàn)證不能存儲(chǔ)null

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

運(yùn)行結(jié)果：

驗(yàn)證NavigableMap相關(guān)方法

@Test
    public void test3() {
        NavigableMap<Integer, String> treeMap = 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);
    }

運(yùn)行結(jié)果：

核心機(jī)制

實(shí)現(xiàn)原理

大家有想過(guò)TreeMap的底層是怎么實(shí)現(xiàn)的嗎，是如何維護(hù)key的順序呢？答案就是基于紅黑樹(shù)實(shí)現(xiàn)的。

那什么是紅黑樹(shù)呢？我們?cè)谶@里簡(jiǎn)單的認(rèn)識(shí)一下，了解一下紅黑樹(shù)的特點(diǎn)：紅黑樹(shù)是一顆自平衡的排序二叉樹(shù)。我們就先從二叉樹(shù)開(kāi)始說(shuō)起。

二叉樹(shù)

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

上面這顆就是一顆最普通的二叉樹(shù)。但是你會(huì)發(fā)現(xiàn)看起來(lái)不那么美觀，因?yàn)槟阋訦為根節(jié)點(diǎn)，發(fā)現(xiàn)左右兩邊高低不平衡，高度相差達(dá)到了2。于是出現(xiàn)了平衡二叉樹(shù)，使得左右兩邊高低差不多。

平衡二叉樹(shù)

這下子應(yīng)該能看到，不管是從任何一個(gè)字母為根節(jié)點(diǎn)，左右兩邊的深度差不了2，最多是1。這就是平衡二叉樹(shù)。不過(guò)好景不長(zhǎng)，有一天，突然要把字母變成數(shù)字，還要保持這種特性怎么辦呢？于是又出現(xiàn)了平衡二叉排序樹(shù)。

平衡二叉排序樹(shù)

不管是從長(zhǎng)相（平衡），還是從規(guī)律（排序）感覺(jué)這棵樹(shù)超級(jí)完美。但是有一個(gè)問(wèn)題，那就是在增加刪除節(jié)點(diǎn)的時(shí)候，你要時(shí)刻去讓這棵樹(shù)保持平衡，需要做太多的工作了，旋轉(zhuǎn)的次數(shù)超級(jí)多，于是乎出現(xiàn)了紅黑樹(shù)。

紅黑樹(shù)

這就是傳說(shuō)中的紅黑樹(shù)，和平衡二叉排序樹(shù)的區(qū)別就是每個(gè)節(jié)點(diǎn)涂上了顏色，他有下列五條性質(zhì)：

每個(gè)節(jié)點(diǎn)都只能是紅色或者黑色
根節(jié)點(diǎn)是黑色
每個(gè)葉節(jié)點(diǎn)（NIL節(jié)點(diǎn)，空節(jié)點(diǎn)）是黑色的。
如果一個(gè)結(jié)點(diǎn)是紅的，則它兩個(gè)子節(jié)點(diǎn)都是黑的。也就是說(shuō)在一條路徑上不能出現(xiàn)相鄰的兩個(gè)紅色結(jié)點(diǎn)。
從任一節(jié)點(diǎn)到其每個(gè)葉子的所有路徑都包含相同數(shù)目的黑色節(jié)點(diǎn)。

這些性質(zhì)有什么優(yōu)點(diǎn)呢？就是插入效率超級(jí)高。因?yàn)樵诓迦胍粋€(gè)元素的時(shí)候，最多只需三次旋轉(zhuǎn)，O(1)的復(fù)雜度，但是有一點(diǎn)需要說(shuō)明他的查詢效率略微遜色于平衡二叉樹(shù)，因?yàn)樗绕胶舛鏄?shù)會(huì)稍微不平衡最多一層，也就是說(shuō)紅黑樹(shù)的查詢性能只比相同內(nèi)容的avl樹(shù)最多多一次比較。如何去旋轉(zhuǎn)呢？如下圖所示。

首先是左旋：

然后是右旋：

紅黑樹(shù)更詳細(xì)的內(nèi)容可以參考文章：Java紅黑樹(shù)的數(shù)據(jù)結(jié)構(gòu)與算法解析

源碼解析

成員變量

//這是一個(gè)比較器，方便插入查找元素等操作
private final Comparator<? super K> comparator;
//紅黑樹(shù)的根節(jié)點(diǎn)：每個(gè)節(jié)點(diǎn)是一個(gè)Entry
private transient Entry<K,V> root;
//集合元素?cái)?shù)量
private transient int size = 0;
//集合修改的記錄
private transient int modCount = 0;

comparator是一個(gè)排序器，作為key的排序規(guī)則
root是紅黑樹(shù)的根節(jié)點(diǎn)，說(shuō)明的確底層用的紅黑樹(shù)作為數(shù)據(jù)結(jié)構(gòu)。

static final class Entry<K,V> implements Map.Entry<K,V> {
        K key;
        V value;
     	//左子樹(shù)
        Entry<K,V> left;
     	//右子樹(shù)
        Entry<K,V> right;
     	//父節(jié)點(diǎn)
        Entry<K,V> parent;
     	//每個(gè)節(jié)點(diǎn)的顏色：紅黑樹(shù)屬性。
        boolean color = BLACK;
        Entry(K key, V value, Entry<K,V> parent) {
            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.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;
        }
    }

查找get方法

TreeMap基于紅黑樹(shù)實(shí)現(xiàn)，而紅黑樹(shù)是一種自平衡二叉查找樹(shù)，所以 TreeMap 的查找操作流程和二叉查找樹(shù)一致。二叉樹(shù)的查找流程是這樣的，先將目標(biāo)值和根節(jié)點(diǎn)的值進(jìn)行比較，如果目標(biāo)值小于根節(jié)點(diǎn)的值，則再和根節(jié)點(diǎn)的左孩子進(jìn)行比較。如果目標(biāo)值大于根節(jié)點(diǎn)的值，則繼續(xù)和根節(jié)點(diǎn)的右孩子比較。在查找過(guò)程中，如果目標(biāo)值和二叉樹(shù)中的某個(gè)節(jié)點(diǎn)值相等，則返回 true，否則返回 false。TreeMap 查找和此類似，只不過(guò)在 TreeMap 中，節(jié)點(diǎn)（Entry）存儲(chǔ)的是鍵值對(duì)<k,v>。在查找過(guò)程中，比較的是鍵的大小，返回的是值，如果沒(méi)找到，則返回null。TreeMap 中的查找方法是get。

public V get(Object key) {
        //調(diào)用 getEntry方法查找
        Entry<K,V> p = getEntry(key);
        return (p==null ? null : p. value);
}

final Entry<K,V> getEntry(Object key) {
    / 如果比較器為空，只是用key作為比較器查詢
    if (comparator != null) 
        return getEntryUsingComparator(key);
    if (key == null)
        throw new NullPointerException();
    Comparable<? super K> k = (Comparable<? super K>) key;
    // 取得root節(jié)點(diǎn)
    Entry<K,V> p = root;
   //核心來(lái)了：從root節(jié)點(diǎn)開(kāi)始查找，根據(jù)比較器判斷是在左子樹(shù)還是右子樹(shù)
    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方法

我們來(lái)看下關(guān)鍵的插入方法，在插入時(shí)候是如何維護(hù)key的。

public V put(K key, V value) {
        Entry<K,V> t = root;
       // 1.如果根節(jié)點(diǎn)為 null，將新節(jié)點(diǎn)設(shè)為根節(jié)點(diǎn)
        if (t == null) {
            compare(key, key); // type (and possibly null) check

            root = new Entry<>(key, value, null);
            size = 1;
            modCount++;
            return null;
        }
      //如果root不為null，說(shuō)明已存在元素 
        int cmp;
        Entry<K,V> parent;
        // split comparator and comparable paths
        Comparator<? super K> cpr = comparator;
    //如果比較器不為null 則使用比較器
        if (cpr != null) {
            //找到元素的插入位置
            do {
                parent = t;
                cmp = cpr.compare(key, t.key);
                 //當(dāng)前key小于節(jié)點(diǎn)key 向左子樹(shù)查找
                if (cmp < 0)
                    t = t.left;
                    //當(dāng)前key大于節(jié)點(diǎn)key 向右子樹(shù)查找
                else if (cmp > 0)
                    t = t.right;
                else
                    //相等的情況下 直接更新節(jié)點(diǎn)值
                    return t.setValue(value);
            } while (t != null);
        }
            //如果比較器為null 則使用默認(rèn)比較器
        else {
            //如果key為null  則拋出異常
            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);
      //根據(jù)比較結(jié)果決定插入到左子樹(shù)還是右子樹(shù)
        if (cmp < 0)
            parent.left = e;
        else
            parent.right = e;
    //保持紅黑樹(shù)性質(zhì)，進(jìn)行紅黑樹(shù)的旋轉(zhuǎn)等操作
        fixAfterInsertion(e);
        size++;
        modCount++;
        return null;
    }

比較關(guān)鍵的就是fixAfterInsertion方法，看懂這個(gè)方法需要你對(duì)紅黑樹(shù)的機(jī)制比較了解。

private void fixAfterInsertion(Entry<K,V> x) {
    // 將新插入節(jié)點(diǎn)的顏色設(shè)置為紅色
    x. color = RED;
    // while循環(huán)，保證新插入節(jié)點(diǎn)x不是根節(jié)點(diǎn)或者新插入節(jié)點(diǎn)x的父節(jié)點(diǎn)不是紅色（這兩種情況不需要調(diào)整）
    while (x != null && x != root && x. parent.color == RED) {
        // 如果新插入節(jié)點(diǎn)x的父節(jié)點(diǎn)是祖父節(jié)點(diǎn)的左孩子
        if (parentOf(x) == leftOf(parentOf (parentOf(x)))) {
            // 取得新插入節(jié)點(diǎn)x的叔叔節(jié)點(diǎn)
            Entry<K,V> y = rightOf(parentOf (parentOf(x)));
            // 如果新插入x的父節(jié)點(diǎn)是紅色
            if (colorOf(y) == RED) {
                // 將x的父節(jié)點(diǎn)設(shè)置為黑色
                setColor(parentOf (x), BLACK);
                // 將x的叔叔節(jié)點(diǎn)設(shè)置為黑色
                setColor(y, BLACK);
                // 將x的祖父節(jié)點(diǎn)設(shè)置為紅色
                setColor(parentOf (parentOf(x)), RED);
                // 將x指向祖父節(jié)點(diǎn)，如果x的祖父節(jié)點(diǎn)的父節(jié)點(diǎn)是紅色，按照上面的步奏繼續(xù)循環(huán)
                x = parentOf(parentOf (x));
            } else {
                // 如果新插入x的叔叔節(jié)點(diǎn)是黑色或缺少，且x的父節(jié)點(diǎn)是祖父節(jié)點(diǎn)的右孩子
                if (x == rightOf( parentOf(x))) {
                    // 左旋父節(jié)點(diǎn)
                    x = parentOf(x);
                    rotateLeft(x);
                }
                // 如果新插入x的叔叔節(jié)點(diǎn)是黑色或缺少，且x的父節(jié)點(diǎn)是祖父節(jié)點(diǎn)的左孩子
                // 將x的父節(jié)點(diǎn)設(shè)置為黑色
                setColor(parentOf (x), BLACK);
                // 將x的祖父節(jié)點(diǎn)設(shè)置為紅色
                setColor(parentOf (parentOf(x)), RED);
                // 右旋x的祖父節(jié)點(diǎn)
                rotateRight( parentOf(parentOf (x)));
            }
        } else { // 如果新插入節(jié)點(diǎn)x的父節(jié)點(diǎn)是祖父節(jié)點(diǎn)的右孩子和上面的相似
            Entry<K,V> y = 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)));
            }
        }
    }
    // 最后將根節(jié)點(diǎn)設(shè)置為黑色
    root.color = BLACK;
}

刪除remove方法

刪除remove是最復(fù)雜的方法。

public V remove(Object key) {
        // 根據(jù)key查找到對(duì)應(yīng)的節(jié)點(diǎn)對(duì)象
        Entry<K,V> p = getEntry(key);
        if (p == null)
            return null;

        // 記錄key對(duì)應(yīng)的value，供返回使用
        V oldValue = p. value;
        // 刪除節(jié)點(diǎn)
        deleteEntry(p);
        return oldValue;
}

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

最終還是落到了對(duì)紅黑樹(shù)節(jié)點(diǎn)的刪除上，需要維持紅黑樹(shù)的特性，做一系列的工作。

到此這篇關(guān)于一文帶你深入了解Java TreeMap的文章就介紹到這了,更多相關(guān)Java TreeMap內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: