Java基礎(chǔ)之TreeMap詳解
一、寫在前面
TreeMap的底層數(shù)據(jù)結(jié)構(gòu)是紅黑樹,且TreeMap可以實現(xiàn)集合元素的排序。
所以TreeMap的源碼需要實現(xiàn):
1.紅黑樹的數(shù)據(jù)結(jié)構(gòu),以及紅黑樹的節(jié)點插入,刪除,以及紅黑樹的自平衡操作,如左旋,右旋,以及節(jié)點變色
2.紅黑樹需要支持按照指定的比較器進(jìn)行排序,或者進(jìn)行自然排序。
二、定義
public class TreeMap<K,V> extends AbstractMap<K,V> implements NavigableMap<K,V>, Cloneable, java.io.Serializable
public interface NavigableMap<K,V> extends SortedMap<K,V> {
TreeMap
繼承了AbstractMap
實現(xiàn)了NavigableMap,而NavigableMap接口繼承了SortedMap接口,SortedMap接口表示其實現(xiàn)類是一個有序集合
實現(xiàn)了Cloneable,所以支持對象克隆
實現(xiàn)了Serializable,所以支持對象序列化
三、成員變量
comparator
/** * The comparator used to maintain order in this tree map, or * null if it uses the natural ordering of its keys. * * @serial */ private final Comparator<? super K> comparator;
外部指定的比較器。在創(chuàng)建TreeMap對象時可以指定。如果指定了比較器,則TreeMap插入鍵值對時,按照comparator比較排序。
root
private transient Entry<K,V> root;
root指代TreeMap底層紅黑樹的根節(jié)點。 root的類型Entry<K,V>就是紅黑樹節(jié)點的類型。
紅黑樹數(shù)據(jù)結(jié)構(gòu)的實現(xiàn)就依賴于Entry<K,V>
size
/** * The number of entries in the tree */ private transient int size = 0;
表示TreeMap集合中鍵值對個數(shù)。
modCount
/** * The number of structural modifications to the tree. */ private transient int modCount = 0;
表示TreeMap集合被結(jié)構(gòu)化修改的次數(shù)。用于迭代器迭代過程中檢測集合是否被結(jié)構(gòu)化修改,若是,則fail-fast。
四、內(nèi)部類
Entry<K,V>
Entry<K,V>是紅黑樹節(jié)點的代碼實現(xiàn),是實現(xiàn)紅黑樹數(shù)據(jù)結(jié)構(gòu)的基礎(chǔ)。
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; boolean color = BLACK; /** * Make a new cell with given key, value, and parent, and with * {@code null} child links, and BLACK color. */ Entry(K key, V value, Entry<K,V> parent) { this.key = key; this.value = value; this.parent = parent; } /** * Returns the key. * * @return the key */ public K getKey() { return key; } /** * Returns the value associated with the key. * * @return the value associated with the key */ public V getValue() { return value; } /** * Replaces the value currently associated with the key with the given * value. * * @return the value associated with the key before this method was * called */ public V setValue(V value) { V oldValue = this.value; this.value = value; return oldValue; } public boolean equals(Object o) { if (!(o instanceof Map.Entry)) return false; Map.Entry<?,?> e = (Map.Entry<?,?>)o; return valEquals(key,e.getKey()) && valEquals(value,e.getValue()); } public int hashCode() { int keyHash = (key==null ? 0 : key.hashCode()); int valueHash = (value==null ? 0 : value.hashCode()); return keyHash ^ valueHash; } public String toString() { return key + "=" + value; } }
成員變量
K key,V value分別是TreeMap集合中存儲的鍵值對的鍵和值
Entry<K,V> left 代表當(dāng)前節(jié)點的左子節(jié)點
Entry<K,V> right 代表當(dāng)前節(jié)點的右子節(jié)點
Entry<K,V> parent 代表當(dāng)前節(jié)點的父節(jié)點
boolean color 代表當(dāng)前節(jié)點的顏色,默認(rèn)是黑色,為true
構(gòu)造器
Entry<K,V>只提供了一個構(gòu)造器 Entry(K key, V value, Entry<K,V> parent)
即:創(chuàng)建一個紅黑樹節(jié)點,只需要指定其存儲的鍵值信息,以及其父節(jié)點引用。不需要指定左孩子和右孩子,以及顏色。
成員方法
提供了getKey()方法返回當(dāng)前節(jié)點的key值。
提供了getValue(),setValue(V v)分別用于獲取Value,以及覆蓋Value后返回oldValue
重寫了equals()方法用于判斷兩個紅黑樹節(jié)點是否相同。邏輯是:兩個紅黑樹節(jié)點的key要么都為null,要么equals結(jié)果true,且,value要么都為null,要么equals結(jié)果為true。
重寫了hashCode()方法。
重寫了toString()方法。
五、構(gòu)造器
public TreeMap()
public TreeMap() { comparator = null; }
無參構(gòu)造器,即不指定比較器的構(gòu)造器。
注意,此時插入集合的鍵值對的key的類型必須實現(xiàn)Comparable接口,即提供自然排序能力,否則會報錯類型轉(zhuǎn)換異常。
public TreeMap(Comparator<? super K> comparator)
public TreeMap(Comparator<? super K> comparator) { this.comparator = comparator; }
指定比較器的構(gòu)造器。
指定的比較器用于比較key,且comparator指定了泛型,即比較器比較的元素的類型必須是K或者K的父類類型。
public TreeMap(Map<? extends K, ? extends V> m)
public TreeMap(Map<? extends K, ? extends V> m) { comparator = null; putAll(m); }
將非TreeMap集合轉(zhuǎn)為TreeMap集合構(gòu)造器
public TreeMap(SortedMap<K, ? extends V> m)
public TreeMap(SortedMap<K, ? extends V> m) { comparator = m.comparator(); try { buildFromSorted(m.size(), m.entrySet().iterator(), null, null); } catch (java.io.IOException cannotHappen) { } catch (ClassNotFoundException cannotHappen) { } }
將有序Map集合轉(zhuǎn)為TreeMap集合
六、成員方法
public V get(Object key)
public V get(Object key) { Entry<K,V> p = getEntry(key); return (p==null ? null : p.value); }
TreeMap的get方法用于獲取指定key的value。如果指定key沒有對應(yīng)的紅黑樹節(jié)點,則返回null,否則返回對應(yīng)紅黑樹節(jié)點的value。
可以看到get方法實現(xiàn)依賴于getEntry(Object key)方法。
getEntry(Object key)方法是根據(jù)指定key找對應(yīng)的紅黑樹節(jié)點并返回該節(jié)點。
final Entry<K,V> getEntry(Object key)
final Entry<K,V> getEntry(Object key) { // Offload comparator-based version for sake of performance if (comparator != null)//如果外部指定了比較器 return getEntryUsingComparator(key);//則使用指定比較器來查找 if (key == null)//如果外部沒有指定比較器,且要查找的key為null,則拋出空指針異常 throw new NullPointerException(); @SuppressWarnings("unchecked")//此時外部沒有指定構(gòu)造器,且要查的Key不為null Comparable<? super K> k = (Comparable<? super K>) key;//檢查Key的類型是否實現(xiàn)了Comparable接口,即是否實現(xiàn)了自然排序,如果實現(xiàn)了,則此處可以強轉(zhuǎn)成功,否則會報錯類型轉(zhuǎn)換異常 Entry<K,V> p = root; while (p != null) {//從紅黑樹根節(jié)點開始使用key本身的自然排序進(jìn)行比較 int cmp = k.compareTo(p.key); if (cmp < 0)//如果要查找的key小于樹節(jié)點的key,則說明要找的key在當(dāng)前節(jié)點的左子樹上,則下次遍歷從左子樹的根節(jié)點開始 p = p.left; else if (cmp > 0)//如果要查找的key大于樹節(jié)點的key,則說明要找的key在當(dāng)前節(jié)點的右子樹上,則下次遍歷從右子樹的根節(jié)點開始 p = p.right; else//如果要查找的key等于樹節(jié)點的key,則該節(jié)點就是要找的,直接返回該節(jié)點 return p; } return null;//如果上面遍歷沒有找到對應(yīng)Key的節(jié)點,則返回null } final Entry<K,V> getEntryUsingComparator(Object key) {//使用指定比較器來查找,邏輯基本和自然排序查找一樣,只是這里使用了比較器排序查找 @SuppressWarnings("unchecked") K k = (K) key; Comparator<? super K> cpr = comparator; if (cpr != null) { Entry<K,V> p = root; while (p != null) { int cmp = cpr.compare(k, p.key); if (cmp < 0) p = p.left; else if (cmp > 0) p = p.right; else return p; } } return null; }
public V put(K key, V value)
public V put(K key, V value) { Entry<K,V> t = root; 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<K,V> parent; // split comparator and comparable paths Comparator<? super K> cpr = comparator; 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<? 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); if (cmp < 0) parent.left = e; else parent.right = e; fixAfterInsertion(e); size++; modCount++; return null; }
final int compare(Object k1, Object k2) { return comparator==null ? ((Comparable<? super K>)k1).compareTo((K)k2) : comparator.compare((K)k1, (K)k2); }
public V setValue(V value) { V oldValue = this.value; this.value = value; return oldValue; }
TreeMap的put方法用于插入一個鍵值對,
當(dāng)插入的key在集合中不存在時,則put表示新增鍵值對,并返回null;
當(dāng)插入的key在集合中存在時,則put表示覆蓋已存在key對應(yīng)的value,并返回老value。
private void fixAfterInsertion(Entry<K,V> x)
private void fixAfterInsertion(Entry<K,V> x) {//x是被插入的紅黑樹節(jié)點 x.color = RED;//默認(rèn)被插入的節(jié)點都是紅色 while (x != null && x != root && x.parent.color == RED) {//如果被插入節(jié)點不是根節(jié)點 if (parentOf(x) == leftOf(parentOf(parentOf(x)))) { Entry<K,V> y = rightOf(parentOf(parentOf(x))); if (colorOf(y) == RED) { setColor(parentOf(x), BLACK); setColor(y, BLACK); setColor(parentOf(parentOf(x)), RED); x = parentOf(parentOf(x)); } else { if (x == rightOf(parentOf(x))) { x = parentOf(x); rotateLeft(x); } setColor(parentOf(x), BLACK); setColor(parentOf(parentOf(x)), RED); rotateRight(parentOf(parentOf(x))); } } else { Entry<K,V> y = leftOf(parentOf(parentOf(x))); if (colorOf(y) == RED) { setColor(parentOf(x), BLACK); setColor(y, BLACK); setColor(parentOf(parentOf(x)), RED); x = parentOf(parentOf(x)); } else { if (x == leftOf(parentOf(x))) { x = parentOf(x); rotateRight(x); } setColor(parentOf(x), BLACK); setColor(parentOf(parentOf(x)), RED); rotateLeft(parentOf(parentOf(x))); } } } root.color = BLACK;//如果被插入的節(jié)點是根節(jié)點,則節(jié)點顏色改為黑色 }
fixAfterInsertion方法用于:當(dāng)TreeMap插入紅黑樹節(jié)點后,導(dǎo)致紅黑樹不平衡時,TreeMap保持自平衡的自旋和變色操作。
該方法的入?yún)⒕褪遣迦氲募t黑樹節(jié)點。
到此這篇關(guān)于Java基礎(chǔ)之TreeMap詳解的文章就介紹到這了,更多相關(guān)Java TreeMap詳解內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!
- Java TreeMap升序|降序排列和按照value進(jìn)行排序的案例
- JAVA使用TreeMap對字符串進(jìn)行排序
- 在Java中如何決定使用 HashMap 還是 TreeMap
- Java源碼解析TreeMap簡介
- 通過java.util.TreeMap源碼加強紅黑樹的理解
- java中TreeMap排序的示例代碼
- java中treemap和treeset實現(xiàn)紅黑樹
- Java TreeMap排序算法實例
- java TreeMap源碼解析詳解
- java 中HashMap、HashSet、TreeMap、TreeSet判斷元素相同的幾種方法比較
- 淺談java中的TreeMap 排序與TreeSet 排序
- java HashMap,TreeMap與LinkedHashMap的詳解
- Java中HashMap和TreeMap的區(qū)別深入理解
相關(guān)文章
NoHttpResponseException問題排查解決記錄分析
這篇文章主要為大家介紹了NoHttpResponseException問題排查解決記錄分析,有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進(jìn)步,早日升職加薪2023-08-08JAVA中使用JSON進(jìn)行數(shù)據(jù)傳遞示例
本篇文章主要介紹了JAVA中使用JSON進(jìn)行數(shù)據(jù)傳遞示例,小編覺得挺不錯的,現(xiàn)在分享給大家,也給大家做個參考。一起跟隨小編過來看看吧2017-01-01SpringBoot項目打jar包與war包的詳細(xì)步驟
SpringBoot和我們之前學(xué)習(xí)的web應(yīng)用程序不一樣,其本質(zhì)上是一個 Java應(yīng)用程序,那么又如何部署呢?這篇文章主要給大家介紹了關(guān)于SpringBoot項目打jar包與war包的詳細(xì)步驟,需要的朋友可以參考下2023-02-02Java兩個變量的互換(不借助第3個變量)具體實現(xiàn)方法
這篇文章主要介紹了Java兩個變量的互換(不借助第3個變量)具體實現(xiàn)方法,需要的朋友可以參考下2014-02-02