Javaコレクション(六)--TreeMapの概要
9351 ワード
本編ではTreeMapを分析する.
TreeMapの定義と説明
次のように定義します.
1、AbstractMapを継承し、NavigableMapインタフェースを実現した.NavigableMapはSortedMapインタフェースを拡張したインタフェースであることを集合フレームワークの記事から知った.一方、SortedMapインタフェースは、主に秩序化されたMap実装を提供します.だからTreeMapは秩序あるMapです.
2、Cloneableを実現し、cloneをサポートする.
3、javaを実現した.io.Serializableは、シーケンス化と逆シーケンス化をサポートします.
TreeMapは赤と黒の木に基づいて実現された.使用するコンストラクション関数に応じて、キーの比較可能な自然な順序、または作成時に提供されるComparatorに基づいてソートします.
次に、構造方法を見てみましょう.
コンストラクション関数から,コンパレータを指定しない場合,キーの自然な順序ソートを用いることが分かった.
TreeMapソースコードの概要
慣例に従って、TreeMapに付与されたput()メソッドを見に行きます.
以上の解析から,TreeMapは実際にTreeMapEntryタイプのroot属性を操作することによって,データの挿入を実現していることが分かった.つまり、TreeMapに対する操作は、実は赤と黒の木に対する操作によって行われています.
次に、他の方法を分析します.
TreeMapEntryの操作
TreeMapの操作方法としては、firstEntry()、lastEntry()、pollFirstEntry()、pollLastEntry()、lowerEntry()、floorEntry()、ceilingEntry()、higherEntry()がある.これらは、指定したノードをツリーのループで見つけて操作します.例えばfirstEntry():
上の分析では、見知らぬクラス、AbstractMapを発見しました.SimpleImmutableEntry.このクラスは、setValue()メソッドをサポートしないキーと値を可変にするためです.これは私たちが戻ってきたEntryを修正しないようにするためです.
key操作に関する方法
キーの操作方法はfirstKey()、lastKey()、lowerKey()、floorKey()、ceilingKey()、higherKey()があります.firstKey()の方法を見てみましょう.
すなわち,ノードのTreeMapEntryオブジェクトを取得することにより,対応するkeyを取得する.
value操作に関する方法
valueの操作方法はcontainsValue()、get()、values()などがありますが、get()の方法を見てみましょう.
実際には、指定したノードをツリーのループで取得し、指定した値を取得していることがわかります.
ツリーに関連するアクション
操作木に関する方法としては,左回り(rotateLeft()),右回り(rotateRight()),挿入補正(fixAfterInsertion()),削除補正(fixAfterDeletion()などがある.左回りを見てみましょう.
では、この文章はここまで分析して、後期に補充があるかどうかを見てみましょう.
TreeMapの定義と説明
次のように定義します.
public class TreeMap
extends AbstractMap
implements NavigableMap, Cloneable, java.io.Serializable{}p
1、AbstractMapを継承し、NavigableMapインタフェースを実現した.NavigableMapはSortedMapインタフェースを拡張したインタフェースであることを集合フレームワークの記事から知った.一方、SortedMapインタフェースは、主に秩序化されたMap実装を提供します.だからTreeMapは秩序あるMapです.
2、Cloneableを実現し、cloneをサポートする.
3、javaを実現した.io.Serializableは、シーケンス化と逆シーケンス化をサポートします.
TreeMapは赤と黒の木に基づいて実現された.使用するコンストラクション関数に応じて、キーの比較可能な自然な順序、または作成時に提供されるComparatorに基づいてソートします.
次に、構造方法を見てみましょう.
// ， TreeMap ， ， null。
private final Comparator super K> comparator;
// TreeMap
public TreeMap() {
// null
comparator = null;
}
// ， TreeMap
public TreeMap(Comparator super K> comparator) {
//
this.comparator = comparator;
}
// TreeMap，
public TreeMap(Map extends K, ? extends V> m) {
comparator = null;
// TreeMap。 TreeMap
putAll(m);
}
// m TreeMap
public TreeMap(SortedMap m) {
// m
comparator = m.comparator();
try {
//
buildFromSorted(m.size(),m.entrySet().iterator(), null, null);
} catch (java.io.IOException cannotHappen) {
} catch (ClassNotFoundException cannotHappen) {
}
}
コンストラクション関数から,コンパレータを指定しない場合,キーの自然な順序ソートを用いることが分かった.
TreeMapソースコードの概要
慣例に従って、TreeMapに付与されたput()メソッドを見に行きます.
//
private final Comparator super K> comparator;
//
private transient TreeMapEntry root;
//TreeMap
private transient int size = 0;
//TreeMap
private transient int modCount = 0;
public V put(K key, V value) {
// t
TreeMapEntry t = root;
// null
if (t == null) {
// null， null
if (comparator != null) {
// null， key null
if (key == null) {
// null
comparator.compare(key, key);
}
} else {
// null， key null
if (key == null) {
//key null，
throw new NullPointerException("key == null");
} else if (!(key instanceof Comparable)) {
//comparator null，key null， key Comparable ，
throw new ClassCastException(
"Cannot cast" + key.getClass().getName() + " to Comparable.");
}
}
//
root = new TreeMapEntry<>(key, value, null);
size = 1;
modCount++;
return null;
}
// ，
//key key
int cmp;
// key
TreeMapEntry parent;
// cpr
Comparator super K> cpr = comparator;
// null
if (cpr != null) {
// null，
do {
// t parent( root)
parent = t;
// key key
cmp = cpr.compare(key, t.key);
// key t
if (cmp < 0)
t = t.left;
// key t
else if (cmp > 0)
t = t.right;
else
// key ，
return t.setValue(value);
} while (t != null);
}
else {
// null， key null
if (key == null)
//key null，
throw new NullPointerException();
@SuppressWarnings("unchecked")
// ，key Comparable ， ClassCastException。
Comparable super K> k = (Comparable super K>) key;
//
do {
// t parent( root)
parent = t;
// key key
cmp = k.compareTo(t.key);
if (cmp < 0)
// key t
t = t.left;
else if (cmp > 0)
// key t
t = t.right;
else
// key ，
return t.setValue(value);
} while (t != null);
}
//
TreeMapEntry e = new TreeMapEntry<>(key, value, parent);
// key key
if (cmp < 0)
//
parent.left = e;
else
// ，
parent.right = e;
// ，
fixAfterInsertion(e);
size++;
modCount++;
return null;
}
private static final boolean RED = false;
private static final boolean BLACK = true;
//
static final class TreeMapEntry implements Map.Entry {
//key
K key;
//value
V value;
//
TreeMapEntry left;
//
TreeMapEntry right;
//
TreeMapEntry parent;
//
boolean color = BLACK;
//
TreeMapEntry(K key, V value, TreeMapEntry parent) {
this.key = key;
this.value = value;
this.parent = parent;
}
//
..........
}
以上の解析から,TreeMapは実際にTreeMapEntryタイプのroot属性を操作することによって,データの挿入を実現していることが分かった.つまり、TreeMapに対する操作は、実は赤と黒の木に対する操作によって行われています.
次に、他の方法を分析します.
TreeMapEntryの操作
TreeMapの操作方法としては、firstEntry()、lastEntry()、pollFirstEntry()、pollLastEntry()、lowerEntry()、floorEntry()、ceilingEntry()、higherEntry()がある.これらは、指定したノードをツリーのループで見つけて操作します.例えばfirstEntry():
//
public Map.Entry firstEntry() {
return exportEntry(getFirstEntry());
}
//
final TreeMapEntry getFirstEntry() {
// ，
TreeMapEntry p = root;
if (p != null)
while (p.left != null)
p = p.left;
return p;
}
// AbstractMap.SimpleImmutableEntry
static Map.Entry exportEntry(TreeMapEntry e) {
return (e == null) ? null :
new AbstractMap.SimpleImmutableEntry<>(e);
}
// key value
public SimpleImmutableEntry(Entry extends K, ? extends V> entry) {
this.key = entry.getKey();
this.value = entry.getValue();
}
上の分析では、見知らぬクラス、AbstractMapを発見しました.SimpleImmutableEntry.このクラスは、setValue()メソッドをサポートしないキーと値を可変にするためです.これは私たちが戻ってきたEntryを修正しないようにするためです.
key操作に関する方法
キーの操作方法はfirstKey()、lastKey()、lowerKey()、floorKey()、ceilingKey()、higherKey()があります.firstKey()の方法を見てみましょう.
public K firstKey() {
return key(getFirstEntry());
}
static K key(TreeMapEntry e) {
if (e==null)
throw new NoSuchElementException();
return e.key;
}
すなわち,ノードのTreeMapEntryオブジェクトを取得することにより,対応するkeyを取得する.
value操作に関する方法
valueの操作方法はcontainsValue()、get()、values()などがありますが、get()の方法を見てみましょう.
public V get(Object key) {
// key
TreeMapEntry p = getEntry(key);
//
return (p==null ? null : p.value);
}
final TreeMapEntry getEntry(Object key) {
//
if (comparator != null)
return getEntryUsingComparator(key);
// key null
if (key == null)
throw new NullPointerException();
@SuppressWarnings("unchecked")
// key
Comparable super K> k = (Comparable super K>) key;
// root t
TreeMapEntry p = root;
// key ， null
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;
}
実際には、指定したノードをツリーのループで取得し、指定した値を取得していることがわかります.
ツリーに関連するアクション
操作木に関する方法としては,左回り(rotateLeft()),右回り(rotateRight()),挿入補正(fixAfterInsertion()),削除補正(fixAfterDeletion()などがある.左回りを見てみましょう.
private void rotateLeft(TreeMapEntry p) {
if (p != null) {
TreeMapEntry r = p.right;
p.right = r.left;
if (r.left != null)
r.left.parent = p;
r.parent = p.parent;
if (p.parent == null)
root = r;
else if (p.parent.left == p)
p.parent.left = r;
else
p.parent.right = r;
r.left = p;
p.parent = r;
}
}
では、この文章はここまで分析して、後期に補充があるかどうかを見てみましょう.