【Java原理探索】「TreeMap」原理和基礎(chǔ)源碼的介紹
基本概念：
TreeMap是基于紅黑樹(shù)（Red-Black tree）的NavigableMap實(shí)現(xiàn)。
該集合最重要的特點(diǎn)就是可排序，該映射根據(jù)其鍵的自然順序進(jìn)行排序，或者根據(jù)創(chuàng)建映射時(shí)提供的Comparator進(jìn)行排序，具體取決于使用的構(gòu)造方法。
TreeMap可以對(duì)添加進(jìn)來(lái)的元素進(jìn)行排序，可以按照默認(rèn)的排序方式，也可以自己指定排序方式。
TreeMap存儲(chǔ)并排序我們自定義的類(lèi)，那么必須自己定義比較機(jī)制：一種方式是User類(lèi)去實(shí)現(xiàn)java.lang.Comparable接口，并實(shí)現(xiàn)其compareTo()方法。
寫(xiě)一個(gè)類(lèi)（如MyComparator）去實(shí)現(xiàn)java.util.Comparator接口，并實(shí)現(xiàn)compare()方法，然后將MyComparator類(lèi)實(shí)例對(duì)象作為T(mén)reeMap的構(gòu)造方法參數(shù)進(jìn)行傳參（當(dāng)然也可以使用匿名內(nèi)部類(lèi)），這些比較方法是怎么被調(diào)用的將在源碼中講解。
源碼分析
類(lèi)名及類(lèi)成員變量
public class TreeMap<K,V>
extends AbstractMap<K,V>
implements NavigableMap<K,V>, Cloneable, java.io.Serializable{
// 比較器對(duì)象
private final Comparator<? super K> comparator;
// 根節(jié)點(diǎn)
private transient Entry<K,V> root;
// 集合大小
private transient int size = 0;
// 樹(shù)結(jié)構(gòu)被修改的次數(shù)
private transient int modCount = 0;
// 靜態(tài)內(nèi)部類(lèi)用來(lái)表示節(jié)點(diǎn)類(lèi)型
static final class Entry<K,V> implements Map.Entry<K,V> {
K key; // 鍵
V value; // 值
Entry<K,V> left; // 指向左子樹(shù)的引用（指針）
Entry<K,V> right; // 指向右子樹(shù)的引用（指針）
Entry<K,V> parent; // 指向父節(jié)點(diǎn)的引用（指針）
boolean color = BLACK; //
}
}
復(fù)制代碼類(lèi)構(gòu)造方法
public TreeMap() {
// 1,無(wú)參構(gòu)造方法
comparator = null; //默認(rèn)比較機(jī)制
}
public TreeMap(Comparator<? super K> comparator) {
// 2，自定義比較器的構(gòu)造方法
this.comparator = comparator;
}
public TreeMap(Map<? extends K, ? extends V> m) {
// 3，構(gòu)造已知Map對(duì)象為T(mén)reeMap
comparator = null; // 默認(rèn)比較機(jī)制
putAll(m);
}
public TreeMap(SortedMap<K, ? extends V> m) {
// 4，構(gòu)造已知的SortedMap對(duì)象為T(mén)reeMap
comparator = m.comparator();
// 使用已知對(duì)象的構(gòu)造器
try {
buildFromSorted(m.size(),
m.entrySet().iterator(), null, null);
} catch (java.io.IOException cannotHappen) {
} catch (ClassNotFoundException cannotHappen) {
}
}
復(fù)制代碼put()方法詳解
public V put(K key, V value) {
Entry<K,V> t = root; // 獲取根節(jié)點(diǎn)
// 如果根節(jié)點(diǎn)為空，則該元素置為根節(jié)點(diǎn)
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;
// 比較器對(duì)象
// 如果比較器對(duì)象不為空，也就是自定義了比較器
if (cpr != null) {
do {
// 循環(huán)比較并確定元素應(yīng)插入的位置(也就是找到該元素的父節(jié)點(diǎn))
parent = t; // t就是root
// 調(diào)用比較器對(duì)象的compare()方法，該方法返回一個(gè)整數(shù)
cmp = cpr.compare(key, t.key);
if (cmp < 0)
// 待插入元素的key"小于"當(dāng)前位置元素的key，則查詢(xún)左子樹(shù)
t = t.left;
else if (cmp > 0)
// 待插入元素的key"大于"當(dāng)前位置元素的key，則查詢(xún)右子樹(shù)
t = t.right;
else
// "相等"則替換其value。
return t.setValue(value);
} while (t != null);
}
// 如果比較器對(duì)象為空，使用默認(rèn)的比較機(jī)制
else {
if (key == null)
throw new NullPointerException();
@SuppressWarnings("unchecked")
Comparable<? super K> k =
(Comparable<? super K>) key;
// 取出比較器對(duì)象
do {
// 同樣是循環(huán)比較并確定元素應(yīng)插入的位置(也就是
找到該元素的父節(jié)點(diǎn))
parent = t;
cmp = k.compareTo(t.key);
// 同樣調(diào)用比較方法并返回一個(gè)整數(shù)
if (cmp < 0)
// 待插入元素的key"小于"當(dāng)前位置元素的key，則查詢(xún)左子樹(shù)
t = t.left;
else if (cmp > 0)
// 待插入元素的key"大于"當(dāng)前位置元素的key，則查詢(xún)右子樹(shù)
t = t.right;
else
// "相等"則替換其value。
return t.setValue(value);
} while (t != null);
}
Entry<K,V> e = new Entry<>(key, value, parent);
// 根據(jù)key找到父節(jié)點(diǎn)后新建一個(gè)節(jié)點(diǎn)
if (cmp < 0)
// 根據(jù)比較的結(jié)果來(lái)確定放在左子樹(shù)還是右子樹(shù)
parent.left = e;
else
parent.right = e;
fixAfterInsertion(e);
size++; // 集合大小+1
modCount++; // 集合結(jié)構(gòu)被修改次數(shù)+1
return null;
}
復(fù)制代碼自定義比較器的使用，說(shuō)了這么多關(guān)于比較器的內(nèi)容？
先來(lái)看下面這段代碼
public class LiboExample {
public static void main(String[] args) {
Map<String, String> map = new TreeMap<>();
map.put("ddd", "444");
map.put("ccc", "333");
map.put("bbb", "222");
map.put("aaa", "111");
Set<Entry<String, String>> entrySet = map.entrySet();
for (Entry<String, String> each : entrySet) { System.out.println(each.getKey()+"::"+each.getValue());
}
}
}
復(fù)制代碼輸出結(jié)果如下，結(jié)果是排序過(guò)的，那是因?yàn)镾tring類(lèi)實(shí)現(xiàn)了Comparable接口并實(shí)現(xiàn)了compareTo()方法，該方法按字典順序比較兩個(gè)字符串。
aaa::111
bbb::222
ccc::333
ddd::444
復(fù)制代碼下面我們寫(xiě)個(gè)自定義User類(lèi)，使用2種方式將類(lèi)對(duì)象按照age字段從小到大排序。
方式1，User實(shí)現(xiàn)Comparable接口并實(shí)現(xiàn)了compareTo()方法
User類(lèi)
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;
}
}
復(fù)制代碼測(cè)試代碼
public class TreeMapDemo1 {
public static void main(String[] args) {
Map<User, String> map = new TreeMap<>();
map.put(new User("jimmy1", 30), "hello");
map.put(new User("jimmy2", 30), "hello");
map.put(new User("jimmy", 22), "hello");
map.put(new User("jimmy", 20), "hello");
Set<Entry<User, String>> entrySet = map.entrySet();
for (Entry<User, String> each : entrySet) {
System.out.println(each.getKey()+"::"+each.getValue());
}
}
}
復(fù)制代碼輸出結(jié)果如下，首先按age排序，若年齡相等則再按username的字母表順序排序。
User [username=jimmy, age=20]::hello
User [username=jimmy, age=22]::hello
User [username=jimmy1, age=30]::hello
User [username=jimmy2, age=30]::hello
復(fù)制代碼方式2，寫(xiě)一個(gè)類(lèi)實(shí)現(xiàn)java.util.Comparator接口，并將該類(lèi)對(duì)象傳遞給TreeMap的構(gòu)造方法。
這種方式將實(shí)體類(lèi)和比較機(jī)制解耦合，可以寫(xiě)很多個(gè)不同的比較器對(duì)象。
實(shí)體類(lèi)
public class User3 {
// User對(duì)象不再實(shí)現(xiàn)任何接口
private String username;
private int age;
public User3(String username, int age) {
super();
this.username = username;
this.age = age;
}
public String getUsername() {
return username;
}
public void setUsername(String username) {
this.username = username;
}
public int getAge() {
return age;
}
public void setAge(int age) {
this.age = age;
}
@Override
public String toString() {
return "User3 [username=" + username +
", age=" + age + "]";
}
}
復(fù)制代碼比較器類(lèi)
public class TreeMapComparator implements Comparator<User3>{
// 比較器類(lèi)
@Override
public int compare(User3 o1, User3 o2) {
int temp = o1.getAge() - o2.getAge();
return temp == 0 ?
o1.getUsername().compareTo(o2.getUsername())
: temp;
}
}
復(fù)制代碼測(cè)試代碼
public class TreeMapDemo3 {
public static void main(String[] args) {
Map<User3, String> map = new TreeMap<>(new TreeMapComparator());
map.put(new User3("jimmy1", 30), "hello");
map.put(new User3("jimmy2", 30), "hello");
map.put(new User3("jimmy", 22), "hello");
map.put(new User3("jimmy", 20), "hello");
Set<Entry<User3, String>> entrySet = map.entrySet();
for (Entry<User3, String> each : entrySet) {
System.out.println(each.getKey()+"::"+each.getValue());
}
}
}
復(fù)制代碼輸出結(jié)果如下，跟上面的相同。
User3 [username=jimmy, age=20]::hello
User3 [username=jimmy, age=22]::hello
User3 [username=jimmy1, age=30]::hello
User3 [username=jimmy2, age=30]::hello
復(fù)制代碼當(dāng)然，我們還可以不寫(xiě)比較器類(lèi)，而是使用匿名內(nèi)部類(lèi)的形式來(lái)寫(xiě)比較器。
public class TreeMapDemo4 {
public static void main(String[] args) {
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;
}
});
map.put(new User3("jimmy1", 30), "hello");
map.put(new User3("jimmy2", 30), "hello");
map.put(new User3("jimmy", 22), "hello");
map.put(new User3("jimmy", 20), "hello");
Set<Entry<User3, String>> entrySet = map.entrySet();
for (Entry<User3, String> each : entrySet) {
System.out.println(each.getKey()+"::"+each.getValue());
}
}
}
復(fù)制代碼一幫以getEntry()方法為基礎(chǔ)的獲取元素的方法，其中包括containsKey()，get()，remove()等。
final Entry<K,V> getEntry(Object key) {
// 如果有自定義比較器對(duì)象，就按照自定義規(guī)則遍歷二叉樹(shù)
if (comparator != null)
return getEntryUsingComparator(key);
if (key == null)
throw new NullPointerException();
@SuppressWarnings("unchecked")
Comparable<? super K> k = (Comparable<? super
K>) key;
Entry<K,V> p = root;
while (p != null) {
//按照默認(rèn)比較規(guī)則遍歷二叉樹(shù)
int cmp = k.compareTo(p.key);
if (cmp < 0)
p = p.left;
else if (cmp > 0)
p = p.right;
else
return p;
}
return null;
}
復(fù)制代碼一幫以getFirstEntry()，getLastEntry()為基礎(chǔ)的獲取頭和尾元素的方法，其中包括：firstKey()，lastKey()；firstEntry()，lastEntry()；pollFirstEntry()，pollLastEntry()；
final Entry<K,V> getFirstEntry() {
// 獲取第一個(gè)元素也就是最小的元素，一直遍歷左子樹(shù)
Entry<K,V> p = root;
if (p != null)
while (p.left != null)
p = p.left;
return p;
}
final Entry<K,V> getLastEntry() {
// 獲取最后個(gè)元素也就是最大的元素，一直遍歷右子樹(shù)
Entry<K,V> p = root;
if (p != null)
while (p.right != null)
p = p.right;
return p;
}
復(fù)制代碼keySet()和entrySet()方法，在將HashMap的時(shí)候已經(jīng)講過(guò)了，Map沒(méi)有迭代器，要將Map轉(zhuǎn)化為Set，用Set的迭代器才能進(jìn)行元素迭代。
總結(jié)
TreeMap繼承了Map的性質(zhì)，同時(shí)其樹(shù)結(jié)構(gòu)又可以進(jìn)行元素排序，用處很大。
作者：李浩宇A(yù)lex
鏈接：https://juejin.cn/post/6979571483588689956
來(lái)源：掘金
著作權(quán)歸作者所有。商業(yè)轉(zhuǎn)載請(qǐng)聯(lián)系作者獲得授權(quán)，非商業(yè)轉(zhuǎn)載請(qǐng)注明出處。
評(píng)論
圖片
表情