TreeMap社内実装の概要

1、概要
TreeMapはJava内部実装が比較的複雑な集合クラスの1つである.HashMapとは異なり,TreeMapの下位層はハッシュテーブルで実現されるのではなく,赤と黒の木で実現される.また,HashMapアクセス要素の時間的複雑度はO(1)の定数レベルであり,TreeMap対要素の操作複雑度はO(log n)である.操作性能の面ではTreeMapが優位ではないが、赤黒ツリー(バランスツリー)を用いて実現されているため、内部の要素はすべて順序付けされている.検索する要素が順序付けされている場合、TreeMapの優位性が現れる.
2、赤と黒の木の紹介
まず、赤と黒の木の基本的な性質を紹介します.赤黒の木は厳密な意味でのバランスの木ではありません.高さの差が1より大きいからです.その性質を知るとすぐわかる.
赤黒樹は二叉木で、以下の5つの特性を満たしています.
<1>各ノードの色は赤または黒です.
<2>ルートノードは黒でなければなりません.
<3>各リーフノードは黒(リーフノードはツリーの末尾のNULLノード)です.
<4>ノードが赤い場合、サブノードは黒でなければなりません.すなわち、連続する赤色ノードを持つことができない.
<5>いずれかのノードについて、そのノードからリーフノードへの各パスは同じ数の黒いノードを含む.
上記の定義から分かるように、赤黒樹は相対的にバランスのとれた二叉検索樹である.赤黒樹は生まれながらにしてバランスが必要であるため,一般的な二叉ルックアップツリーが極端な状況(挿入されたデータが順番に並んでいる)でバランスを失うことを避けることができる.
3、TreeMapのEntryクラス
TreeMapにはtreeとMapの性質が含まれているため、Entryクラスには次の6つのメンバー変数が含まれます.
左サブノード参照、右サブノード参照、親ノード参照、key、value、color.
JDKにおいてEntryの具体的な定義は以下の通りである.

static final class Entry<K,V> implements Map.Entry<K,V> {  
    K key;  
    V value;  
    Entry<K,V> left = null;  
    Entry<K,V> right = null;  
    Entry<K,V> parent;  
    boolean color = BLACK;  
  
    /** 
     * Make a new cell with given key, value, and parent, and with 
     * {@code null} child links, and BLACK color. 
     */  
    Entry(K key, V value, Entry<K,V> parent) {  
        this.key = key;  
        this.value = value;  
        this.parent = parent;  
    } 
}

4、TreeMapのput(key,value)操作
挿入要素はput操作によって行われ、主に2つのプロセスを含み、最初のステップはkeyを計算することによって挿入要素の位置を見つけることであり、新しく追加されたkeyが直接挿入されていない場合.存在する場合は、元のノードの値を更新します.2つ目は、新しい要素を挿入すると赤黒ツリーのプロパティが破壊される可能性があるため、破壊された場合は左右に回転するなどして赤黒ツリーのプロパティを復元します.具体的なコードは以下の通りです.

public V put(K key, V value) {  
    Entry<K,V> t = root;  
    if (t == null) {  
        compare(key, key); // type (and possibly null) check  
  
        root = new Entry<>(key, value, null);  
        size = 1;  
        modCount++;  
        return null;  
    }  
    int cmp;  
    Entry<K,V> parent;  
    // split comparator and comparable paths  
    Comparator<? super K> cpr = comparator;  
    if (cpr != null) {  
        do {  
            parent = t;  
            cmp = cpr.compare(key, t.key);  
            if (cmp < 0)  
                t = t.left;  
            else if (cmp > 0)  
                t = t.right;  
            else  
                return t.setValue(value);  
        } while (t != null);  
    }  
    else {  
        if (key == null)  
            throw new NullPointerException();  
        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);  
    if (cmp < 0)  
        parent.left = e;  
    else  
        parent.right = e;  
    fixAfterInsertion(e);  
    size++;  
    modCount++;  
    return null;  
}