TreeMap

簡介

TreeMap是一個直接由紅黑樹實現的結構，對於Key值得比較來排序，顯然得到：

1.key的class必須實現comparable方法，不能拋出ClassCastException異常，否則必須指定一個comprartor

2.由於TreeMap實現了Serializable接口，所以默認的或者自定義的comparator也應該實現該接口

最重要的是，實現了NavigableMap，我理解為導航map,提供了各種操作map視圖的操作

public class TreeMap<K,V>
    extends AbstractMap<K,V>
    implements NavigableMap<K,V>, Cloneable, java.io.Serializable{}
複製代碼

構造方法

四個構造方法，其實就是是否使用默認的compatator

對於無序Map，直接調用putAll,有序的SortedMap話遞歸調用buildFromSorted，提高效率

public TreeMap() {
    comparator = null;
}

public TreeMap(Comparator<? super K> comparator) {
        this.comparator = comparator;
    }

public TreeMap(Map<? extends K, ? extends V> m) {
    comparator = null;
    putAll(m);
}

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) {
    }
}
複製代碼

但是putAll依然判斷了map instanceof SortedMap

具體的紅黑樹的操作在此不作贅述

remove(),put()最根本的操作是紅黑樹的操作，get()也是二叉搜索樹比較直觀的實現

方法詳解

有關樹的操作的方法，其實就是代碼分支比較多，需要考慮各種情況然後轉換為代碼就好了
比較的話看如果有comparator就用，沒有就用key默認的comparable

successor() 查找下個節點

在containsValue()從第一個節點開始successor遍歷
在forEach()從第一個節點開始successor遍歷
replaceAll()從第一個節點開始successor遍歷賦值新的value
remove()遍歷找出Object刪除

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;
    }
}
複製代碼

getCeilingEntry()/getFloorEntry 獲取[low,key]/[key,high]的最大/小值，沒有返回null

// 這個跟successor是相似的，其實如果根據搜索樹沒找到，就是找的下一個節點
final Entry<K,V> getCeilingEntry(K key) {
    Entry<K,V> p = root;
    while (p != null) {
        int cmp = compare(key, p.key);
        //比當前節點小，再跟左子節點比較
        if (cmp < 0) {
            if (p.left != null)
                p = p.left;
            else
                return p;
        } else if (cmp > 0) {
            //比當前節點大，再跟右子節點比較
            if (p.right != null) {
                p = p.right;
            } else {
                //這裡跟successor相同，比最右葉子大，下一個為當前子樹的父節點
                Entry<K,V> parent = p.parent;
                Entry<K,V> ch = p;
                while (parent != null && ch == parent.right) {
                    ch = parent;
                    parent = parent.parent;
                }
                return parent;
            }
        } else
            //相等的話返回當前節點
            return p;
    }
    return null;
}
//跟上面是鏡像的過程
final Entry<K,V> getFloorEntry(K key) {
    Entry<K,V> p = root;
    while (p != null) {
        int cmp = compare(key, p.key);
        //比當前節點大，跟右子節點比較
        if (cmp > 0) {
            if (p.right != null)
                p = p.right;
            else
                return p;
        } else if (cmp < 0) {
            //比當前節點小，再跟左子節點比較
            if (p.left != null) {
                p = p.left;
            } else {
                Entry<K,V> parent = p.parent;
                Entry<K,V> ch = p;
                //比最左葉子小，下一個為當前子樹的父節點
                while (parent != null && ch == parent.left) {
                    ch = parent;
                    parent = parent.parent;
                }
                return parent;
            }
        } else
             //相等的話返回當前節點
            return p;

    }
    return null;
}
複製代碼

getHigherEntry()/getLowerEntry獲取[low,key)/(key,high]的最大/小值，沒有返回null

跟getCeilingEntry一樣的只不過對於相等的情況，不考慮相等的情況

final Entry<K,V> getHigherEntry(K key) {
    Entry<K,V> p = root;
    while (p != null) {
        int cmp = compare(key, p.key);
        if (cmp < 0) {
            if (p.left != null)
                p = p.left;
            else
                return p;
        } else {
            if (p.right != null) {
                p = p.right;
            } else {
                Entry<K,V> parent = p.parent;
                Entry<K,V> ch = p;
                while (parent != null && ch == parent.right) {
                    ch = parent;
                    parent = parent.parent;
                }
                return parent;
            }
        }
    }
    return null;
}
複製代碼

DescendingMap()翻轉map

底層由DescendingSubMap()實現，其實還是這個map，只不過對於所有的操作，比如getfist()，會將其轉換為getLast()來執行,所以對於DescendingMap()的操作依然會影響原Map

同樣的，subMap()的操作也會影響原Map

static final class DescendingSubMap<K,V>  extends NavigableSubMap<K,V> {
    private static final long serialVersionUID = 912986545866120460L;
    // m是當前Map,fromStart是否從頭開始為ture則lo為null，lo開始位置，loInclusive是否包含開始位置
    DescendingSubMap(TreeMap<K,V> m,
                    boolean fromStart, K lo, boolean loInclusive,
                    boolean toEnd,     K hi, boolean hiInclusive) {
        super(m, fromStart, lo, loInclusive, toEnd, hi, hiInclusive);
    }
複製代碼

//DescendingSubMap一些方法的實現
TreeMap.Entry<K,V> subLowest()       { return absHighest(); }
TreeMap.Entry<K,V> subHighest()      { return absLowest(); }
TreeMap.Entry<K,V> subCeiling(K key) { return absFloor(key); }
TreeMap.Entry<K,V> subHigher(K key)  { return absLower(key); }
TreeMap.Entry<K,V> subFloor(K key)   { return absCeiling(key); }
TreeMap.Entry<K,V> subLower(K key)   { return absHigher(key); }
複製代碼