【集合】TreeMap(轉(zhuǎn))

轉(zhuǎn)自作者：leesf 出處：http://www.cnblogs.com/leesf456/
一、前言
　　當(dāng)我們需要把插入的元素進(jìn)行排序的時(shí)候，就是時(shí)候考慮TreeMap了，從名字上來看，TreeMap肯定是和樹是脫不了干系的，它是一個(gè)排序了的Map,下面我們來著重分析其源碼，理解其底層如何實(shí)現(xiàn)排序功能。下面，開始分析。
二、TreeMap示例

import java.util.TreeMap;
import java.util.Map;

public class TreeMapTest {
    public static void main(String[] args) {
        Map<String, String> maps = new TreeMap<String, String>();
        maps.put("aa", "aa");
        maps.put("cc", "cc");
        maps.put("bb", "bb");
        
        for (Map.Entry<String, String> entry : maps.entrySet()) {
            System.out.println(entry.getKey() + " : " + entry.getValue());
        }
    }
}```
運(yùn)行結(jié)果：

　　aa : aa
　　bb : bb
　　cc : cc

說明：從輸出結(jié)果可以看到TreeMap對插入的元素進(jìn)行了排序。

**三、TreeMap數(shù)據(jù)結(jié)構(gòu)**
　　TreeMap底層使用的數(shù)據(jù)結(jié)構(gòu)是紅黑樹，有印象的的讀者，應(yīng)該知道我們在分析HashMap的時(shí)候就已經(jīng)接觸到了紅黑樹結(jié)構(gòu)，只是沒有對紅黑樹進(jìn)行詳細(xì)的分析，現(xiàn)在，筆者也并不打算對紅黑樹做太過仔細(xì)的分析，因?yàn)楣P者之后會(huì)出數(shù)據(jù)結(jié)構(gòu)的專題（先挖個(gè)坑），到時(shí)候再來一睹各種數(shù)據(jù)結(jié)構(gòu)的風(fēng)采。
　　![](http://upload-images.jianshu.io/upload_images/1986284-2bfe1ef057332c31.png?imageMogr2/auto-orient/strip%7CimageView2/2/w/1240)
　　說明：上圖為典型的紅黑樹結(jié)構(gòu)，效率很高，具體的細(xì)節(jié)問題，我們以后詳談。
**四、TreeMap源碼分析**
4.1 類的繼承關(guān)系　　

public class TreeMap<K,V> extends AbstractMap<K,V> implements NavigableMap<K,V>, Cloneable, java.io.Serializable

　說明：繼承了抽象類AbstractMap，AbstractMap實(shí)現(xiàn)了Map接口，實(shí)現(xiàn)了部分方法。不能進(jìn)行實(shí)例化，實(shí)現(xiàn)了NavigableMap,Cloneable,Serializable接口，其中NavigableMap是繼承自SortedMap的接口，定義了一系列規(guī)范。
4.2 類的屬性　

public class TreeMap<K,V>
extends AbstractMap<K,V>
implements NavigableMap<K,V>, Cloneable, java.io.Serializable
{
// 比較器，用于控制Map中的元素順序
private final Comparator<? super K> comparator;
// 根節(jié)點(diǎn)
private transient Entry<K,V> root;
// 樹中結(jié)點(diǎn)個(gè)數(shù)
private transient int size = 0;
// 對樹進(jìn)行結(jié)構(gòu)性修改的次數(shù)
private transient int modCount = 0;
}```
說明：重點(diǎn)是比較器Comparator，此接口實(shí)現(xiàn)了對插入元素進(jìn)行排序。
4.3 類的構(gòu)造函數(shù)

  1. TreeMap()型構(gòu)造函數(shù)
public TreeMap() {
   // 無用戶自定義比較器 
      comparator = null;
 }
  1. TreeMap(Comparator<? super K>)型構(gòu)造函數(shù)
// 自定義了比較器
 public TreeMap(Comparator<? super K> comparator) { 
       this.comparator = comparator; 
}```
說明：用戶自定義了比較器，可以按照用戶的邏輯進(jìn)行比較，確定元素的訪問順序。
3. TreeMap(Map<? extends K, ? extends V>)型構(gòu)造函數(shù)　　

// 從已有map中構(gòu)造
TreeMap public TreeMap(Map<? extends K, ? extends V> m) {
comparator = null; putAll(m);
}

說明：根據(jù)已有的Map構(gòu)造TreeMap。
4. TreeMap(SortedMap<K, ? extends V>)型構(gòu)造函數(shù)　

// 從SortedMap中構(gòu)造TreeMap,有比較器
public TreeMap(SortedMap<K, ? extends V> m) {
comparator = m.comparator();
try {
buildFromSorted(m.size(), m.entrySet().iterator(), null, null);
} catch (java.io.IOException cannotHappen) {
} catch (ClassNotFoundException cannotHappen) {
}
}

說明：傳入SortedMap型參數(shù)，實(shí)現(xiàn)SortedMap接口的類都會(huì)實(shí)現(xiàn)comparator方法，用于返回比較器。
　　4.4 核心函數(shù)分析
　　1. put函數(shù)

public V put(K key, V value) {
// 記錄根節(jié)點(diǎn)
Entry<K,V> t = root;
// 根節(jié)點(diǎn)為空
if (t == null) {
// 比較key
compare(key, key); // type (and possibly null) check
// 新生根節(jié)點(diǎn)
root = new Entry<>(key, value, null);
// 大小加1
size = 1;
// 修改次數(shù)加1
modCount++;
return null;
}
int cmp;
Entry<K,V> parent;
// 獲取比較器
Comparator<? super K> cpr = comparator;
// 比較器不為空
if (cpr != null) {
// 找到元素合適的插入位置
do {
// parent賦值
parent = t;
// 比較key與元素的key值，在Comparator類的compare方法中可以實(shí)現(xiàn)我們自己的比較邏輯
cmp = cpr.compare(key, t.key);
// 小于結(jié)點(diǎn)key值，向左子樹查找
if (cmp < 0)
t = t.left;
// 大于結(jié)點(diǎn)key值，向右子樹查找
else if (cmp > 0)
t = t.right;
// 表示相等，直接更新結(jié)點(diǎn)的值
else
return t.setValue(value);
} while (t != null);
}
// 比較器為空
else {
// key為空，拋出異常
if (key == null)
throw new NullPointerException();
@SuppressWarnings("unchecked")
// 取得K實(shí)現(xiàn)的比較器
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);
}
// 新生一個(gè)結(jié)點(diǎn)
Entry<K,V> e = new Entry<>(key, value, parent);
// 根據(jù)比較結(jié)果決定存為左結(jié)點(diǎn)或右結(jié)點(diǎn)
if (cmp < 0)
parent.left = e;
else
parent.right = e;
// 插入后進(jìn)行修正
fixAfterInsertion(e);
// 大小加1
size++;
// 進(jìn)行了結(jié)構(gòu)性修改
modCount++;
return null;
}```
　說明：插入一個(gè)元素時(shí)，若用戶自定義比較器，則會(huì)按照用戶自定義的邏輯確定元素的插入位置，否則，將會(huì)使用K自身實(shí)現(xiàn)的比較器確定插入位置。
2. getEntry函數(shù)

final Entry<K,V> getEntry(Object key) {
        // 判斷比較器是否為空
        if (comparator != null)
            // 根據(jù)自定義的比較器來返回結(jié)果
            return getEntryUsingComparator(key);
        // 比較器為空
        // key為空，拋出異常
        if (key == null)
            throw new NullPointerException();
        @SuppressWarnings("unchecked")
            // 取得K自身實(shí)現(xiàn)了比較接口
            Comparable<? super K> k = (Comparable<? super K>) key;
        Entry<K,V> p = root;
        // 根據(jù)Comparable接口的compareTo函數(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;
        }
        return null;
    }```
說明：當(dāng)我們調(diào)用get函數(shù)時(shí)，實(shí)際上是委托g(shù)etEntry函數(shù)獲取元素，對于用戶自定義實(shí)現(xiàn)的Comparator比較器而言，是使用getEntryUsingComparator函數(shù)來完成獲取邏輯。

　　具體代碼如下

final Entry<K,V> getEntryUsingComparator(Object key) {
@SuppressWarnings("unchecked")
// 向下轉(zhuǎn)型
K k = (K) key;
// 取得比較器
Comparator<? super K> cpr = comparator;
// 比較器不為空
if (cpr != null) {
Entry<K,V> p = root;
// 開始遍歷樹節(jié)點(diǎn)找到對應(yīng)的結(jié)點(diǎn)
while (p != null) {
int cmp = cpr.compare(k, p.key);
// 小于結(jié)點(diǎn)key值，向左子樹查找
if (cmp < 0)
p = p.left;
// 大于結(jié)點(diǎn)key值，向右子樹查找
else if (cmp > 0)
p = p.right;
// 相等，找到，直接返回
else
return p;
}
}
return null;
}```
　說明：會(huì)根據(jù)用戶定義在compare函數(shù)里面的邏輯進(jìn)行元素的查找。
　　3. deleteEntry函數(shù)

private void deleteEntry(Entry<K,V> p) {
        // 結(jié)構(gòu)性修改
        modCount++;
        // 大小減1
        size--;
        // p的左右子結(jié)點(diǎn)均不為空
        if (p.left != null && p.right != null) {
            // 找到p結(jié)點(diǎn)的后繼
            Entry<K,V> s = successor(p);
            // 將p的值用其后繼結(jié)點(diǎn)的key-value替換，并且用s指向其后繼
            p.key = s.key;
            p.value = s.value;
            p = s;
        } 

        // 開始進(jìn)行修正，具體的修正過程我們會(huì)在之后的數(shù)據(jù)結(jié)構(gòu)專區(qū)進(jìn)行講解
        // 現(xiàn)在可以看成是為了保持紅黑樹的特性，提高性能
        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;
            }
        }
    }```
　說明：deleteEntry函數(shù)會(huì)在remove函數(shù)中被調(diào)用，它完成了移除元素的主要工作，刪除該結(jié)點(diǎn)后會(huì)對紅黑樹進(jìn)行修正，此部分內(nèi)容以后會(huì)詳細(xì)講解，同時(shí)，在此函數(shù)中需要調(diào)用successor函數(shù)，即找到該結(jié)點(diǎn)的后繼結(jié)點(diǎn)。具體函數(shù)代碼如下　

// 找到后繼
static <K,V> TreeMap.Entry<K,V> successor(Entry<K,V> t) {
// t為null，直接返回null
if (t == null)
return null;
// 右孩子不為空
else if (t.right != null) {
// 找到右孩子的最底層的左孩子，返回
Entry<K,V> p = t.right;
while (p.left != null)
p = p.left;
return p;
} else { // 右孩子為空
// 保存t的父節(jié)點(diǎn)
Entry<K,V> p = t.parent;
// 保存t結(jié)點(diǎn)
Entry<K,V> ch = t;
// 進(jìn)行回溯，找到后繼，直到p == null || ch != p.right
while (p != null && ch == p.right) {
ch = p;
p = p.parent;
}
return p;
}
}```
說明：當(dāng)結(jié)點(diǎn)的右子樹為空的時(shí)候，進(jìn)行回溯可以找到該結(jié)點(diǎn)的后繼結(jié)點(diǎn)。
五、問題擴(kuò)展
　　1. 如何找到小于指定結(jié)點(diǎn)的最大結(jié)點(diǎn)？參考getLowerEntry函數(shù)源碼
　　2. 如何找到大于指定結(jié)點(diǎn)的最小結(jié)點(diǎn)？參考getHigherEntry函數(shù)源碼　
　　對getLowerEntry源碼分析如下

final Entry<K,V> getLowerEntry(K key) {
        // 保存根節(jié)點(diǎn)
        Entry<K,V> p = root;
        // 根節(jié)點(diǎn)不為空
        while (p != null) {
            // 比較該key與節(jié)點(diǎn)的key
            int cmp = compare(key, p.key);
            if (cmp > 0) { // 如果該key大于結(jié)點(diǎn)的key
                // 如果結(jié)點(diǎn)的右子樹不為空，與該結(jié)點(diǎn)右結(jié)點(diǎn)進(jìn)行比較
                if (p.right != null)
                    p = p.right;
                else // 右子樹為空，則直接返回結(jié)點(diǎn)；因?yàn)榇藭r(shí)已經(jīng)沒有比該結(jié)點(diǎn)key更大的結(jié)點(diǎn)了(右子樹為空)
                    return p;
            } else { // 如果該key小于等于結(jié)點(diǎn)的key
                // 結(jié)點(diǎn)的左子樹不為空，與該結(jié)點(diǎn)的左結(jié)點(diǎn)進(jìn)行比較
                if (p.left != null) { 
                    p = p.left;
                } else { // 結(jié)點(diǎn)的左子樹不為空，則開始進(jìn)行回溯
                    Entry<K,V> parent = p.parent;
                    Entry<K,V> ch = p;
                    while (parent != null && ch == parent.left) {
                        ch = parent;
                        parent = parent.parent;
                    }
                    return parent;
                }
            }
        }
        return null;
    }```
流程圖如下：
　　![](http://upload-images.jianshu.io/upload_images/1986284-0c527df411ea4a10.png?imageMogr2/auto-orient/strip%7CimageView2/2/w/1240)　　
　　getHigherEntry則可以以此類推。
**六、總結(jié)**
　　由TreeMap我們可以知道其底層的數(shù)據(jù)結(jié)構(gòu)為紅黑樹，并且可以使用用戶自定義的比較器來實(shí)現(xiàn)比較邏輯。對于其核心函數(shù)的分析就到此為止了，謝謝各位園友的觀看~
最后編輯于 ：
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時(shí)請結(jié)合常識與多方信息審慎甄別。
平臺聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點(diǎn)，簡書系信息發(fā)布平臺，僅提供信息存儲(chǔ)服務(wù)。

相關(guān)閱讀更多精彩內(nèi)容

  • 一、基本數(shù)據(jù)類型 注釋 單行注釋：// 區(qū)域注釋：/* */ 文檔注釋：/** */ 數(shù)值 對于byte類型而言...
    龍貓小爺閱讀 4,457評論 0贊 16
  • 1. Java基礎(chǔ)部分 基礎(chǔ)部分的順序：基本語法，類相關(guān)的語法，內(nèi)部類的語法，繼承相關(guān)的語法，異常的語法，線程的語...
    子非魚_t_閱讀 34,767評論 18贊 399
  • 從三月份找實(shí)習(xí)到現(xiàn)在，面了一些公司，掛了不少，但最終還是拿到小米、百度、阿里、京東、新浪、CVTE、樂視家的研發(fā)崗...
    時(shí)芥藍(lán)閱讀 42,821評論 11贊 349
  • 上篇文章我們介紹了HashMap集合，這是一個(gè)鍵值對集合，可以高效的按照鍵查找數(shù)值。但是它有一個(gè)缺陷：數(shù)據(jù)如果是無...
    Single_YAM閱讀 259評論 0贊 3
  • B樹的定義 一棵m階的B樹滿足下列條件： 樹中每個(gè)結(jié)點(diǎn)至多有m個(gè)孩子。 除根結(jié)點(diǎn)和葉子結(jié)點(diǎn)外，其它每個(gè)結(jié)點(diǎn)至少有m...
    文檔隨手記閱讀 13,685評論 0贊 25

友情鏈接更多精彩內(nèi)容