/**
* Map接口的實(shí)現(xiàn)類TreeMap ? ? 使用紅黑樹存儲數(shù)據(jù) ? 通過Comparable或Comparator對key進(jìn)行排序且key不可重復(fù)
*/
public class TestTreeMap1 {
? ?public static void main(String[] args) {
? ? ? ?Map<Integer,String> comment = new TreeMap<>();
? ? ? ?comment.put(9865481,"good");
? ? ? ?comment.put(6848453,"bad");
? ? ? ?for (Integer id :
? ? ? ? ? ? ? ?comment.keySet()) {
? ? ? ? ? ?//通過.keySet()遍歷
? ? ? ? ? ?System.out.println(id+":"+comment.get(id));
? ? ? ?}
? ? ? ?comment.put(8764582,"excellent");
? ? ? ?for (Map.Entry<Integer, String> comm :
? ? ? ? ? ? ? ?comment.entrySet()) {
? ? ? ? ? ?//通過.entrySet()遍歷
? ? ? ? ? ?System.out.println(comm.getKey()+":"+comm.getValue());
? ? ? ?}
? ? ? ?System.out.println(comment);
? ? ? ?//結(jié)果為{6848453=bad, 8764582=excellent, 9865481=good} TreeSet對key=Integer排序，從小到大
? ? ? ?//comment.remove();comment.clear();comment.containsValue();comment.isEmpty();comment.size();方法的使用和HashMap相同
? ? ? ?Map<Integer,String> comment2 = new TreeMap<>(new Comparator<Integer>() {
? ? ? ? ? ?//通過比較器comparator指定規(guī)則排序
? ? ? ? ? ?@Override
? ? ? ? ? ?public int compare(Integer o1, Integer o2) {
? ? ? ? ? ? ? ?if (o1>o2) return -1;
? ? ? ? ? ? ? ?if (o1<o2)return 1;
? ? ? ? ? ? ? ?return 0;
? ? ? ? ? ?}
? ? ? ?});
? ?}
}
/* 分析TreeMap集合put()源碼
public class TreeMap<K,V> extends AbstractMap<K,V> implements NavigableMap<K,V>, Cloneable, java.io.Serializable {
//TreeMap實(shí)現(xiàn)NavigableMap<K,V>，而NavigableMap<K,V> extends SortedMap<K,V> extends Map<K,V>
? ?public V put(K key, V value) {
? ? ? ?Entry<K,V> t = root; ? ? ? ?//root根結(jié)點(diǎn) ? 紅黑樹中不使用Node存儲結(jié)點(diǎn)，直接使用內(nèi)部定義的Entry類存儲結(jié)點(diǎn) ? ? 每個(gè)結(jié)點(diǎn)有key、value、left左子樹結(jié)點(diǎn)/左孩子、right右子樹結(jié)點(diǎn)/右孩子、parent父結(jié)點(diǎn)和boolean color表示紅色或黑色，紅色用常量RED = false，黑色用常量BLACK = true
? ? ? ?if (t == null) {
? ? ? ? ? ?compare(key, key); // type (and possibly null) check ? ? ? ?//當(dāng)根結(jié)點(diǎn)為空即紅黑樹集合中沒有存放結(jié)點(diǎn)，通過調(diào)用compare方法檢查key是否指定了排序規(guī)則，當(dāng)既沒有實(shí)現(xiàn)Comparable也沒有指定Comparator比較器時(shí)會拋出類型轉(zhuǎn)換異常
? ? ? ? ? ?root = new Entry<>(key, value, null);
? ? ? ? ? ?size = 1; ? ? ? //將根結(jié)點(diǎn)設(shè)為新結(jié)點(diǎn)，size即結(jié)點(diǎn)數(shù)變?yōu)?，結(jié)束方法
? ? ? ? ? ?modCount++;
? ? ? ? ? ?return null;
? ? ? ?} ? ? ? //當(dāng)已經(jīng)存在根結(jié)點(diǎn)時(shí)往下執(zhí)行
? ? ? ?int cmp;
? ? ? ?Entry<K,V> parent;
? ? ? ?// split comparator and comparable paths分成使用Comparable排序或使用Comparator排序兩條路
? ? ? ?Comparator<? super K> cpr = comparator; ? ? ? ? //cmp即Comparable，cpr即Comparator，parent用來緩存父結(jié)點(diǎn)
? ? ? ?if (cpr != null) { ? ? ? ? ?//當(dāng)存在比較器時(shí)無論是否自身存在比較規(guī)則都優(yōu)先使用比較器
? ? ? ? ? ?do {
? ? ? ? ? ? ? ?parent = t;
? ? ? ? ? ? ? ?cmp = cpr.compare(key, t.key);
? ? ? ? ? ? ? ?if (cmp < 0)
? ? ? ? ? ? ? ? ? ?t = t.left;
? ? ? ? ? ? ? ?else if (cmp > 0)
? ? ? ? ? ? ? ? ? ?t = t.right; ? ? ? ?//近似二分法，當(dāng)比較結(jié)果為負(fù)走左子樹這條路，當(dāng)比較結(jié)果為正走右子樹這條路，這樣在put階段直接完成了排序
? ? ? ? ? ? ? ?else
? ? ? ? ? ? ? ? ? ?return t.setValue(value); ? ? ? ? ? //返回0即兩個(gè)key相同，變更value并將原value返回
? ? ? ? ? ?} while (t != null); ? ? ? ? ? ?//直到遇到null即這條路走到頭了到達(dá)了葉結(jié)點(diǎn)的子結(jié)點(diǎn)null，這時(shí)parent為葉結(jié)點(diǎn)即樹的末端結(jié)點(diǎn)，如果沒有key沖突則往下執(zhí)行新結(jié)點(diǎn)的添加
? ? ? ?}
? ? ? ?else { ? ? ? ? ?//當(dāng)不存在比較器的時(shí)候使用自身實(shí)現(xiàn)的compareTo方法，過程和上面類似
? ? ? ? ? ?if (key == null)
? ? ? ? ? ? ? ?throw new NullPointerException();
? ? ? ? ? ?@SuppressWarnings("unchecked")
? ? ? ? ? ? ? ?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); ? ? //將新結(jié)點(diǎn)的父結(jié)點(diǎn)設(shè)為葉結(jié)點(diǎn)
? ? ? ?if (cmp < 0) ? ? ? ?//根據(jù)比較結(jié)果判斷應(yīng)該將新結(jié)點(diǎn)放在葉結(jié)點(diǎn)的左孩子還是右孩子位
? ? ? ? ? ?parent.left = e;
? ? ? ?else
? ? ? ? ? ?parent.right = e;
? ? ? ?fixAfterInsertion(e); ? ? ? //為了維持紅黑樹的性質(zhì)，這里要針對新增的結(jié)點(diǎn)進(jìn)行修復(fù)
? ? ? ?size++;
? ? ? ?modCount++;
? ? ? ?return null; ? ? ? ?//添加完成返回null
? ?}
*/