[TOC]

一、頂部注釋分析

1.1 首句分析

• A Red-Black tree based NavigableMap implementation. The map is sorted according to the Comparable natural ordering of its keys, or by a Comparator provided at map creation time, depending on which constructor is used.
• TreeMap是基于紅黑樹的 NavigableMap 實現(xiàn)
• TreeMap根據(jù)鍵的自然順序進行排序，或者根據(jù)創(chuàng)建map時提供的Comparator進行排序，使用哪種取決于使用哪個構(gòu)造方法

1.2 從注釋中得到的結(jié)論

• 底層是紅黑樹，通過實現(xiàn) NavigableMap 接口，使得可以根據(jù) key 本身進行排序，或是根據(jù)構(gòu)造時提供的 Comparator 進行排序 ，即 TreeMap 是有序的
• TreeMap 的 key 不能為null
• TreeMap提供時間復(fù)雜度為 log(n) 的 containsKey、get、put 、remove操作
• TreeMap同樣是非線程安全，其迭代器也是 fail-fast 的

二、源碼分析

2.1 定義

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

• TreeMap<K,V>：TreeMap是以 key-value 形式存儲數(shù)據(jù)的
• extends AbstractMap<K,V>：繼承自AbstractMap
• implements NavigableMap：實現(xiàn)了NavigableMap，可以返回特定條件的最近匹配
• implements Cloneable：可以調(diào)用 clone() 方法來返回實例的 field-for-field 拷貝
• implements Serializable：可以序列化

2.2 字段

// TreeMap的排序規(guī)則，如果為null，則根據(jù)鍵的自然順序進行排序
private final Comparator<? super K> comparator;

// 紅黑樹根節(jié)點
private transient Entry<K,V> root;

// 紅黑樹大小
private transient int size = 0;

// 樹節(jié)點構(gòu)造，除了左右指針還包括指向父節(jié)點的指針，且為紅黑樹結(jié)構(gòu)
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;
}

2.3 構(gòu)造方法

1. public TreeMap()：使用 key 的自然排序構(gòu)造一個空的 TreeMap
2. public TreeMap(Comparator<? super K> comparator)：使用給定的比較器構(gòu)造一個空的 TreeMap
3. public TreeMap(Map<? extends K, ? extends V> m)：根據(jù)給定 Map 來構(gòu)造 TreeMap，排序方式為key 的自然排序
4. public TreeMap(SortedMap<K, ? extends V> m)：根據(jù)給定 SortedMap (可排序的Map) 來構(gòu)造 TreeMap，且排序方式與 SortedMap 相同

2.4 put 操作

• put 方法共分為以下幾個步驟：
  1. 若紅黑樹為空，且 key 不為空，則新建一棵紅黑樹；
  2. 根據(jù)是否有自定義的 Comparator 方式采用不同的方法遍歷紅黑樹查找 key 所在位置；
  3. 第2步中若沒有自定義 Comparator 方式，即根據(jù) key 進行自然排序，則 key 必須實現(xiàn) Comparable 接口，確保是可比較的；
  4. 如果找到 key 所在位置，則用新值替換原值，并返回原值；
  5. 否則創(chuàng)建新節(jié)點插入紅黑樹，并對樹進行調(diào)整以保持平衡，最終返回 null

2.5 get 操作

• get 方法共分為以下幾個步驟：
  1. 調(diào)用 getEntry 查找對應(yīng)的鍵值對，若找到則返回 value ，找不到返回 null
  2. 在 getEntry 內(nèi)部根據(jù)是否有自定義 comparator 采用不同方式查找，總體邏輯相似，只是 key 之間的比較方式不同

public V get(Object key) 
{
    Entry<K,V> p = getEntry(key);
    return (p==null ? null : p.value);
}

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;
}

2.6 remove 操作

• remove 方法共分為以下幾個步驟：
  1. 先和 get 方法類似嘗試獲取對應(yīng)鍵值對
  2. 若找不到則直接返回 null
  3. 若找到了則先保存對應(yīng)的值，然后調(diào)用 deleteEntry(p) 刪除該節(jié)點并調(diào)整紅黑樹
  4. 最后返回保存的值

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

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

2.7 entrySet

• TreeMap 遍歷是使用的是 EntryIterator 這個內(nèi)部類
• EntryIterator 大多數(shù)的實現(xiàn)均在其父類 PrivateEntryIterator 中
• PrivateEntryIterator 中的 lastReturned 用于存放返回的節(jié)點，在調(diào)用 nextEntry 方法獲取下一個節(jié)點的過程中，使用了 successor 方法
• 該方法是從樹結(jié)構(gòu)中按順序獲取下一個節(jié)點。由于紅黑樹是有序的二叉樹，因此可以采取類似中序遍歷的方式，劍指Offer上有類似的題目
• 大致思路為：
  1. 若當前節(jié)點的右子樹不為空，則返回右子樹中最小節(jié)點，即右子樹的最左節(jié)點；
  2. 如果右子樹為空，則不斷向上回溯，直至當前節(jié)點是其父節(jié)點的左孩子

class EntrySet extends AbstractSet<Map.Entry<K,V>> 
{
    public Iterator<Map.Entry<K,V>> iterator() 
    {
        return new EntryIterator(getFirstEntry());
    }
}

final class EntryIterator extends PrivateEntryIterator<Map.Entry<K,V>> 


abstract class PrivateEntryIterator<T> implements Iterator<T>
{
    Entry<K,V> lastReturned;
    
    final Entry<K,V> nextEntry() 
    {
        Entry<K,V> e = next;
        if (e == null)
            throw new NoSuchElementException();
        if (modCount != expectedModCount)
            throw new ConcurrentModificationException();
        next = successor(e);
        lastReturned = e;
        return e;
    }
}

// 按順序獲取樹結(jié)構(gòu)中的下一個節(jié)點，順序類似于中序遍歷
static <K,V> TreeMap.Entry<K,V> successor(Entry<K,V> t) 
{
    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 
    {
        Entry<K,V> p = t.parent;
        Entry<K,V> ch = t;
        while (p != null && ch == p.right) 
        {
            ch = p;
            p = p.parent;
        }
        return p;
    }
}

三、與HashMap對比