溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
這期內容當中小編將會給大家帶來有關TreeMap怎么在Java中使用，文章內容豐富且以專業的角度為大家分析和敘述，閱讀完這篇文章希望大家可以有所收獲。
Java主要應用于：1. web開發；2. Android開發；3. 客戶端開發；4. 網頁開發；5. 企業級應用開發；6. Java大數據開發；7.游戲開發等。
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
實現了NavigableMap，而NavigableMap接口繼承了SortedMap接口,SortedMap接口表示其實現類是一個有序集合
實現了Cloneable，所以支持對象克隆
實現了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;
外部指定的比較器。在創建TreeMap對象時可以指定。如果指定了比較器，則TreeMap插入鍵值對時，按照comparator比較排序。
root
private transient Entry<K,V> root;
root指代TreeMap底層紅黑樹的根節點。 root的類型Entry<K,V>就是紅黑樹節點的類型。
紅黑樹數據結構的實現就依賴于Entry<K,V>
size
/** * The number of entries in the tree */ private transient int size = 0;
表示TreeMap集合中鍵值對個數。
modCount
/** * The number of structural modifications to the tree. */ private transient int modCount = 0;
表示TreeMap集合被結構化修改的次數。用于迭代器迭代過程中檢測集合是否被結構化修改，若是，則fail-fast。
Entry<K,V>
Entry<K,V>是紅黑樹節點的代碼實現，是實現紅黑樹數據結構的基礎。
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 代表當前節點的左子節點
Entry<K,V> right 代表當前節點的右子節點
Entry<K,V> parent 代表當前節點的父節點
boolean color 代表當前節點的顏色，默認是黑色，為true
構造器
Entry<K,V>只提供了一個構造器 Entry(K key, V value, Entry<K,V> parent)
即：創建一個紅黑樹節點，只需要指定其存儲的鍵值信息，以及其父節點引用。不需要指定左孩子和右孩子，以及顏色。
成員方法
提供了getKey()方法返回當前節點的key值。
提供了getValue()，setValue(V v)分別用于獲取Value，以及覆蓋Value后返回oldValue
重寫了equals()方法用于判斷兩個紅黑樹節點是否相同。邏輯是：兩個紅黑樹節點的key要么都為null，要么equals結果true，且，value要么都為null,要么equals結果為true。
重寫了hashCode()方法。
重寫了toString()方法。
public TreeMap()
public TreeMap() {
comparator = null;
}無參構造器，即不指定比較器的構造器。
注意，此時插入集合的鍵值對的key的類型必須實現Comparable接口，即提供自然排序能力，否則會報錯類型轉換異常。
public TreeMap(Comparator<? super K> comparator)
public TreeMap(Comparator<? super K> comparator) {
this.comparator = comparator;
}指定比較器的構造器。
指定的比較器用于比較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集合轉為TreeMap集合構造器
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集合轉為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沒有對應的紅黑樹節點，則返回null，否則返回對應紅黑樹節點的value。
可以看到get方法實現依賴于getEntry(Object key)方法。
getEntry(Object key)方法是根據指定key找對應的紅黑樹節點并返回該節點。
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")//此時外部沒有指定構造器，且要查的Key不為null
Comparable<? super K> k = (Comparable<? super K>) key;//檢查Key的類型是否實現了Comparable接口，即是否實現了自然排序，如果實現了，則此處可以強轉成功，否則會報錯類型轉換異常
Entry<K,V> p = root;
while (p != null) {//從紅黑樹根節點開始使用key本身的自然排序進行比較
int cmp = k.compareTo(p.key);
if (cmp < 0)//如果要查找的key小于樹節點的key，則說明要找的key在當前節點的左子樹上，則下次遍歷從左子樹的根節點開始
p = p.left;
else if (cmp > 0)//如果要查找的key大于樹節點的key，則說明要找的key在當前節點的右子樹上，則下次遍歷從右子樹的根節點開始
p = p.right;
else//如果要查找的key等于樹節點的key，則該節點就是要找的，直接返回該節點
return p;
}
return null;//如果上面遍歷沒有找到對應Key的節點，則返回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方法用于插入一個鍵值對，
當插入的key在集合中不存在時，則put表示新增鍵值對，并返回null；
當插入的key在集合中存在時，則put表示覆蓋已存在key對應的value，并返回老value。
private void fixAfterInsertion(Entry<K,V> x)
private void fixAfterInsertion(Entry<K,V> x) {//x是被插入的紅黑樹節點
x.color = RED;//默認被插入的節點都是紅色
while (x != null && x != root && x.parent.color == RED) {//如果被插入節點不是根節點
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;//如果被插入的節點是根節點，則節點顏色改為黑色
}上述就是小編為大家分享的TreeMap怎么在Java中使用了，如果剛好有類似的疑惑，不妨參照上述分析進行理解。如果想知道更多相關知識，歡迎關注億速云行業資訊頻道。
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
