Java

JavaコレクションのTreeMapソースコードの分析



Analysis Treemap Source Code Java Collection



目次を読む

トップに戻る

1。概要

TreeMapは、赤黒木に基づいて実装されます。 TreeMapはjava.util.sortMapインターフェースを実装しているため、コレクション内のマッピング関係には特定の順序があります。マッピングは、使用される構築方法に応じて、キーの自然な順序、またはマッピングの作成時に提供されるコンパレータに従ってソートされます。 。さらに、TreeMapではキーオブジェクトをnullにすることはできません。



1.赤黒木とは何ですか？

赤黒木は特別な二分木であり、主に次の基本的なプロパティがあります。

  • 各ノードは赤または黒のみにすることができます
  • ルートノードは黒です
  • 各リーフノードは黒です
  • ノードが赤の場合、その2つの子ノードは黒です。
  • 任意のノードから各リーフノードへのすべてのパスには、同じ数の黒いノードが含まれています

赤黒木の特定の主成分分析とアルゴリズム設計は、ブログ投稿にあります。 赤黒木の主成分分析とアルゴリズム設計 。



2、2つの主要なソート方法

自然ソート：TreeMapのすべてのキーはComparableインターフェイスを実装する必要があり、すべてのキーは同じクラスのオブジェクトである必要があります。そうでない場合、ClassCastExceptionがスローされます。

指定された並べ替え：この並べ替えは、TreeMapを構築するときにComparatorオブジェクトを渡す必要があります。これは、TreeMapのキーの並べ替えを担当します。

3、TreeMapクラスの継承関係

lowerEntry

その中で、NavigableMapインターフェースは、特定の検索ターゲットに最も近い一致を返すナビゲーションメソッドを備えた拡張SortMapです。メソッドfloorEntry、ceilingEntry、higherEntry with Map.Entry指定されたキーnullオブジェクトよりも小さい、以下、または等しい、より大きい、またはより大きいに関連付けられたキーをそれぞれ返します。そのようなキーがない場合は、| _を返します。 + _ |。同様に、メソッドlowerKey、floorKey、ceilingKey higherKey関連するキーのみを返します。これらのメソッドはすべて、アイテムをトラバースするのではなく、アイテムを見つけるように設計されています。に



トップに戻る

2.TreeMapソースコード分析

1、ストレージ構造

TreeMapは赤黒木に基づいて実装され、ツリーノードは次のように定義されます。

画像 
public class TreeMap  
 
 extends AbstractMap 
 
 implements NavigableMap, Cloneable, Serializable
画像

2、コンストラクター

TreeMapには、さまざまなパラメーターに対応する4つのコンストラクターがあります。

画像 
 static final class Entry implements Map.Entry { //key  K key //value  V value //Left child Entry left //Right child Entry right //Parent node Entry parent //Node color boolean color = BLACK //Constructor Entry(K key, V value, Entry parent) { this.key = key this.value = value this.parent = parent } ...... }
画像

3、TreeMapの一般的なメソッド

V put（Kキー、V値）：キーと値のペア（キー、値）をTreeMapに追加します

画像 
 //1.Construct a new, empty tree map using the natural order of keys public TreeMap() { comparator = null } //2.Construct a new, empty tree map, which is sorted according to the given comparator public TreeMap(Comparatorsuper K> comparator) { this.comparator = comparator } /3.Construct a new tree map with the same mapping relationship as the given map, which is sorted according to the natural order of its keys public TreeMap(Mapextends K, ? extends V> m) { comparator = null putAll(m) } //4.Construct a new tree map with the same mapping relationship and the same sort order as the specified ordered map public TreeMap(SortedMapextends V> m) { comparator = m.comparator() try { buildFromSorted(m.size(), m.entrySet().iterator(), null, null) } catch (java.io.IOException cannotHappen) { } catch (ClassNotFoundException cannotHappen) { } }
画像

セットするentrySet（）：このマッピングに含まれるマッピング関係のセットビューを返します

public V put(K key, V value) { Entry t = root //If the root node is empty, create a new node with (key, value) as parameters 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 parent // split comparator and comparable paths Comparatorsuper K> cpr = comparator //Specified sorting algorithm if (cpr != null) { do { parent = t cmp = cpr.compare(key, t.key) if (cmp <0) //Indicates that the key of the new node is less than the key of the current node and the node, and the left child node of the current node is used as the new current node t = t.left else if (cmp > 0) //Indicates that the key of the new node is greater than the key of the current node and the node, and the right child node of the current node is used as the new current node t = t.right else return t.setValue(value) //Equal to overwrite the old value } while (t != null) } //If cpr is empty, the default sorting algorithm is used to create the TreeMap collection else { if (key == null) throw new NullPointerException() @SuppressWarnings('unchecked') Comparablesuper K> k = (Comparablesuper 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) } //Treat the new node as a child node of the parent Entry e = new Entry(key, value, parent) if (cmp <0) parent.left = e else parent.right = e //After inserting a new node, call fixAfterInsertion to adjust the red-black tree  fixAfterInsertion(e) size++ modCount++ return null }

boolean remove（Object o）：このTreeMapにキーマッピング関係が存在する場合は、削除します

画像 
 public Set entrySet() { EntrySet es = entrySet return (es != null) ? es : (entrySet = new EntrySet()) }
画像 トップに戻る

3、TreeMapアプリケーションのサンプルコード

画像 
 public boolean remove(Object o) { if (!(o instanceof Map.Entry)) return false Map.Entry entry = (Map.Entry) o K key = entry.getKey() if (!inRange(key)) return false TreeMap.Entry node = m.getEntry(key) if (node!=null && valEquals(node.getValue(), entry.getValue())) { m.deleteEntry(node) return true } return false } }
画像

まず、キーの自然な順序に従ってTreeMapを作成し、要素を追加してトラバースします。

次に、新しいコンパレータクラスを作成して、コンパレータインターフェイスを実装します。

画像 
public class TreeMapDemo { public static void main(String[] args) { //Construct a new, empty tree map using the natural order of keys TreeMap tm=new TreeMap() tm.put('001', 'China') tm.put('003', 'United States') tm.put('002', 'France') System.out.println('Call entrySet to get the key-value pair set:') Set result=tm.entrySet() for(Entry result2:result) { System.out.println(result2.getKey()+'---'+result2.getValue()) } System.out.println('Call keySet to get the key set:') Set result3=tm.keySet() for(String str:result3) { System.out.println(str) } System.out.println('Call values ​​to get the value set:') Collection result4=tm.values() for(Object str:result4) System.out.println(str) //Create a new TreeMap with a comparator TreeMap tm2=new TreeMap(new ComparatorDemo()) tm2.put('001', 'China') tm2.put('003', 'United States') tm2.put('002', 'France') Set result5=tm2.entrySet() for(Entry result2:result5) { System.out.println(result2.getKey()+'---'+result2.getValue()) } } }
画像

コンパレータ付きのtm2で、tm1と同じ順序で要素を追加してから、tm2を再度トラバースすると、結果は次のようになります。

ここでの順序は、コンパレータの比較方法に基づいています。 compareメソッドは常に1を返すため、つまりサイズは同じであるため、tm2のキーの順序が最初の加算順序になります。