一.TreeMap的特性
TreeMap是有序的泛鸟，可以自定義排序規(guī)則乳讥，如果不指定則按照默認(rèn)的規(guī)則排序
二.TreeMap的底層結(jié)構(gòu)
采用了紅黑樹作為底層的數(shù)據(jù)結(jié)構(gòu)
三.源碼分析
public V put(K key, V value) {
//頭結(jié)點(diǎn)
Entry t =root;
//頭結(jié)點(diǎn)為空的情況下
? ? 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
? ? Comparator cpr =comparator;
? ?//循環(huán)比較笋颤，插入節(jié)點(diǎn)
? ? 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();
? ? ? ? @SuppressWarnings("unchecked")
Comparable k = (Comparable) 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 e =new Entry<>(key, value, parent);
? ? if (cmp <0)
? ? ? ? parent.left = e;
else
? ? ? ? parent.right = e;
? ? ?//插入節(jié)點(diǎn)后钓简，調(diào)整紅黑樹
? ? ? fixAfterInsertion(e);
? ? size++;
? ? modCount++;
? ? return null;
}
