TreeMap
TreeMap集合是基于紅黑樹（Red-Black tree）的 NavigableMap實現(xiàn)筛璧。該集合最重要的特點就是可排序惹恃，該映射根據(jù)其鍵的自然順序進行排序，或者根據(jù)創(chuàng)建映射時提供的 Comparator 進行排序，具體取決于使用的構(gòu)造方法曲秉。這句話是什么意思呢疲牵？就是說TreeMap可以對添加進來的元素進行排序，可以按照默認的排序方式纲爸，也可以自己指定排序方式
【知識點】
- TreeMap基于紅黑樹實現(xiàn)無容量限制；
- TreeMap是非線程安全的负蚊；
類名及類成員變量
public class TreeMap<K,V>
extends AbstractMap<K,V>
implements NavigableMap<K,V>, Cloneable, java.io.Serializable
{
// 比較器對象
private final Comparator<? super K> comparator;
// 根節(jié)點
private transient Entry<K,V> root;
// 集合大小
private transient int size = 0;
// 樹結(jié)構(gòu)被修改的次數(shù)
private transient int modCount = 0;
// 靜態(tài)內(nèi)部類用來表示節(jié)點類型
static final class Entry<K,V> implements Map.Entry<K,V> {
K key; // 鍵
V value; // 值
Entry<K,V> left; // 指向左子樹的引用（指針）
Entry<K,V> right; // 指向右子樹的引用（指針）
Entry<K,V> parent; // 指向父節(jié)點的引用（指針）
boolean color = BLACK; //
}
}
類構(gòu)造方法
public TreeMap() { // 1,無參構(gòu)造方法
comparator = null; // 默認比較機制
}
public TreeMap(Comparator<? super K> comparator) { // 2家妆，自定義比較器的構(gòu)造方法
this.comparator = comparator;
}
public TreeMap(Map<? extends K, ? extends V> m) { // 3，構(gòu)造已知Map對象為TreeMap
comparator = null; // 默認比較機制
putAll(m);
}
public TreeMap(SortedMap<K, ? extends V> m) { // 4伤极，構(gòu)造已知的SortedMap對象為TreeMap
comparator = m.comparator(); // 使用已知對象的構(gòu)造器
try {
buildFromSorted(m.size(), m.entrySet().iterator(), null, null);
} catch (java.io.IOException cannotHappen) {
} catch (ClassNotFoundException cannotHappen) {
}
}
- put(K key, V value)
public V put(K key, V value) {
Entry<K,V> t = root; // 獲取根節(jié)點
// 如果根節(jié)點為空哨坪，則該元素置為根節(jié)點
if (t == null) {
compare(key, key); // type (and possibly null) check
root = new Entry<>(key, value, null);
size = 1; // 集合大小為1
modCount++; // 結(jié)構(gòu)修改次數(shù)自增
return null;
}
int cmp;
Entry<K,V> parent;
Comparator<? super K> cpr = comparator; // 比較器對象
// 如果比較器對象不為空，也就是自定義了比較器
if (cpr != null) {
do { // 循環(huán)比較并確定元素應插入的位置(也就是找到該元素的父節(jié)點)
parent = t; // t就是root
// 調(diào)用比較器對象的compare()方法届慈，該方法返回一個整數(shù)
cmp = cpr.compare(key, t.key);
if (cmp < 0) // 待插入元素的key"小于"當前位置元素的key凌箕，則查詢左子樹
t = t.left;
else if (cmp > 0) // 待插入元素的key"大于"當前位置元素的key，則查詢右子樹
t = t.right;
else // "相等"則替換其value牵舱。
return t.setValue(value);
} while (t != null);
}
// 如果比較器對象為空芜壁，使用默認的比較機制
else {
if (key == null)
throw new NullPointerException();
@SuppressWarnings("unchecked")
Comparable<? super K> k = (Comparable<? super K>) key; // 取出比較器對象
do { // 同樣是循環(huán)比較并確定元素應插入的位置(也就是找到該元素的父節(jié)點)
parent = t;
cmp = k.compareTo(t.key); // 同樣調(diào)用比較方法并返回一個整數(shù)
if (cmp < 0) // 待插入元素的key"小于"當前位置元素的key，則查詢左子樹
t = t.left;
else if (cmp > 0) // 待插入元素的key"大于"當前位置元素的key慧妄，則查詢右子樹
t = t.right;
else // "相等"則替換其value塞淹。
return t.setValue(value);
} while (t != null);
}
Entry<K,V> e = new Entry<>(key, value, parent); // 根據(jù)key找到父節(jié)點后新建一個節(jié)點
if (cmp < 0) // 根據(jù)比較的結(jié)果來確定放在左子樹還是右子樹
parent.left = e;
else
parent.right = e;
fixAfterInsertion(e);
size++; // 集合大小+1
modCount++; // 集合結(jié)構(gòu)被修改次數(shù)+1
return null;
}
自定義比較器
- key為String類型，因為String實現(xiàn)了Comparable接口饱普，所以按照String類中的compareTo方法進行排序；
- TreeMap的key實現(xiàn)Comparable接口并實現(xiàn)compareTo方法谁帕；
public class User implements Comparable<User>{
private String username;
private int age;
public User(String username, int age) {
this.username = username;
this.age = age;
}
@Override
public String toString() {
return "User [username=" + username + ", age=" + age + "]";
}
@Override
public int compareTo(User user) {
int temp = this.age - user.age;
return temp == 0 ? this.username.compareTo(user.username) : temp;
}
}
- 使用TreeMap的構(gòu)造方法傳遞比較器
Map<User3, String> map = new TreeMap<>(new TreeMapComparator());
- 使用匿名內(nèi)部類的形式來寫比較器
Map<User3, String> map = new TreeMap<>(new Comparator<User3>() {
@Override
public int compare(User3 o1, User3 o2) {
int temp = o1.getAge() - o2.getAge();
return temp == 0 ? o1.getUsername().compareTo(o2.getUsername()) : temp;
}
});
參考資料
