JDK的TreeMap怎么實(shí)現(xiàn)

發(fā)布時(shí)間：2021-12-31 16:00:30 來(lái)源：億速云閱讀：138 作者：iii 欄目：編程語(yǔ)言

這篇文章主要講解了“JDK的TreeMap怎么實(shí)現(xiàn)”，文中的講解內(nèi)容簡(jiǎn)單清晰，易于學(xué)習(xí)與理解，下面請(qǐng)大家跟著小編的思路慢慢深入，一起來(lái)研究和學(xué)習(xí)“JDK的TreeMap怎么實(shí)現(xiàn)”吧！

TreeMap的實(shí)現(xiàn)也是利用的紅黑樹(shù)，我們來(lái)看代碼：

在TreeMap中包含著一個(gè)根結(jié)點(diǎn)：

private transient Entry<K,V> root = null;

這個(gè)Entry代碼如下：

static final class Entry<K,V> implements Map.Entry<K,V> {
K key;
V value;
//指向小兒子
Entry<K,V> left = null;
//指向大兒子
Entry<K,V> right = null;
//指向父親
Entry<K,V> parent;
//顏色默認(rèn)為黑色
boolean color = BLACK;
Entry(K key, V value, Entry<K,V> parent) {
this.key = key;
this.value = value;
this.parent = parent;
}
public K getKey() {
return key;
}
public V getValue() {
return value;
}
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;
}
}

廢話不多說(shuō)，我們來(lái)看一下他的插入實(shí)現(xiàn)：

public V put(K key, V value) {
Entry<K,V> t = root;
//如果樹(shù)是空樹(shù)
if (t == null) {
//那么樹(shù)根節(jié)點(diǎn)就是節(jié)點(diǎn)
root = new Entry<K,V>(key, value, null);
size = 1;
modCount++;
return null;
}
int cmp;
Entry<K,V> parent;
//否則利用提供的比較器進(jìn)行比較
Comparator<? super K> cpr = comparator;
if (cpr != null) {
do {
parent = t;
cmp = cpr.compare(key, t.key);
//如果比當(dāng)前節(jié)點(diǎn)小，
if (cmp < 0)
//往小兒子遞歸
t = t.left;
else if (cmp > 0)
//往大兒子遞歸
t = t.right;
else
//如果已經(jīng)有這個(gè)key，那么修改key，并且什么都可以不修改了
return t.setValue(value);
} while (t != null); //知道找到葉子節(jié)點(diǎn)；
}
else {
if (key == null)
throw new NullPointerException();
//如果沒(méi)有提供外部的比較器，那么就利用內(nèi)置的比較器
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);
}
//生成一個(gè)葉子節(jié)點(diǎn)，準(zhǔn)備進(jìn)行加入
Entry<K,V> e = new Entry<K,V>(key, value, parent);
//利用最后的判斷，將這個(gè)節(jié)點(diǎn)變成該葉子節(jié)點(diǎn)的兒子；
if (cmp < 0)
parent.left = e;
else
parent.right = e;
//由于有可能破壞了紅黑樹(shù)的規(guī)則，現(xiàn)在進(jìn)行調(diào)整；
fixAfterInsertion(e);
size++;
modCount++;
return null;
}

private void fixAfterInsertion(Entry<K,V> x) {
//首先將該新增節(jié)點(diǎn)染紅，葉子節(jié)點(diǎn)(null)是黑色的;
x.color = RED;
//如果他的父親是紅色的，那么沖突開(kāi)始；
while (x != null && x != root && x.parent.color == RED) {
//如果是左子數(shù)；
if (parentOf(x) == leftOf(parentOf(parentOf(x)))) {
Entry<K,V> y = rightOf(parentOf(parentOf(x)));
//如果其兄弟是紅色的，那么根據(jù)上一節(jié)的分析，將兩兄弟都變成黑色，其父節(jié)點(diǎn)變紅，這樣黑色節(jié)點(diǎn)的數(shù)目沒(méi)有發(fā)生變化，而我們距離跟更近一步；
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)));
}
//如果是右子數(shù)，正好與上面相反；
} 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)));
}
}
}
//沖突會(huì)一直追溯到跟，把跟染黑，不違背根節(jié)點(diǎn)是黑色的特性，并且使得所有的樹(shù)枝的黑色節(jié)點(diǎn)因此加1，沖突解決；
root.color = BLACK;
}

看完了增加，我們?cè)賮?lái)看看刪除

public V remove(Object key) {
//查找到該節(jié)點(diǎn)
Entry<K,V> p = getEntry(key);
//不存在則結(jié)束
if (p == null)
return null;
V oldValue = p.value;
//刪除
deleteEntry(p);
//返回原值
return oldValue;
}

查找該節(jié)點(diǎn)：

final Entry<K,V> getEntry(Object key) {
if (comparator != null)
//利用外部比較器
return getEntryUsingComparator(key);
if (key == null)
throw new NullPointerException();
//內(nèi)置比較器
Comparable<? super K> k = (Comparable<? super K>) key;
Entry<K,V> p = root;
while (p != null) {
int cmp = k.compareTo(p.key);
if (cmp < 0)
p = p.left;
else if (cmp > 0)
p = p.right;
else
return p;
}
return null;
}

外部比較器查找節(jié)點(diǎn)：

final Entry<K,V> getEntryUsingComparator(Object key) {
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;
}

刪除操作：

private void deleteEntry(Entry<K,V> p) {
modCount++;
size--;
//如果刪除的節(jié)點(diǎn)有兩個(gè)子節(jié)點(diǎn)；
if (p.left != null && p.right != null) {
Entry<K,V> s = successor (p);
p.key = s.key;
p.value = s.value;
p = s;
}
//兩個(gè)子節(jié)點(diǎn)的刪除轉(zhuǎn)化為了一個(gè)子節(jié)點(diǎn)的刪除
//進(jìn)行一個(gè)子節(jié)點(diǎn)的刪除操作；
Entry<K,V> replacement = (p.left != null ? p.left : p.right);
//如果有一個(gè)以上的節(jié)點(diǎn)；重新接上樹(shù)枝；
if (replacement != null) {
replacement.parent = p.parent;
if (p.parent == null)
root = replacement;
else if (p == p.parent.left)
p.parent.left = replacement;
else
p.parent.right = replacement;
p.left = p.right = p.parent = null;
//如果刪除位置的新節(jié)點(diǎn)是黑色的，那么會(huì)少一個(gè)黑節(jié)點(diǎn)，調(diào)整
if (p.color == BLACK)
//調(diào)整新的節(jié)點(diǎn)，即刪除節(jié)點(diǎn)的子節(jié)點(diǎn)；
fixAfterDeletion(replacement);
} else if (p.parent == null) { // return if we are the only node.
root = null;
} else {
//如果沒(méi)有子節(jié)點(diǎn)
//紅色的節(jié)點(diǎn)要可以直接刪除，黑色的話，必須要經(jīng)過(guò)調(diào)整；
if (p.color == BLACK)
fixAfterDeletion(p);
//刪除操作；
if (p.parent != null) {
if (p == p.parent.left)
p.parent.left = null;
else if (p == p.parent.right)
p.parent.right = null;
p.parent = null;
}
}
}

刪除后的調(diào)整：

private void fixAfterDeletion(Entry<K,V> x) {
// 如果節(jié)點(diǎn)是黑色的；那么要經(jīng)過(guò)調(diào)整，如果是紅色的，可以直接修改成為黑色的，結(jié)束循環(huán)；
while (x != root && colorOf(x) == BLACK)
// 判斷被刪除節(jié)點(diǎn)是左子樹(shù)；
if (x == leftOf(parentOf(x))) {
// 獲得兄弟節(jié)點(diǎn)；
Entry<K,V> sib = rightOf(parentOf(x));
//兄弟節(jié)點(diǎn)是紅色的
if (colorOf(sib) == RED) {
setColor(sib, BLACK);
setColor(parentOf(x), RED);
//開(kāi)始旋轉(zhuǎn)
rotateLeft(parentOf(x));
// 得到旋轉(zhuǎn)后的新的兄弟節(jié)點(diǎn)；這個(gè)時(shí)候是黑色的
sib = rightOf(parentOf(x));
}
//判斷侄子的顏色；如果兩個(gè)都是黑色的
if (colorOf(leftOf(sib)) == BLACK &&
colorOf(rightOf(sib)) == BLACK) {
setColor(sib, RED);
x = parentOf(x);
} else {
// 只有一個(gè)是黑色的
// 如果是黑色的那個(gè)侄子位置不對(duì)，那么經(jīng)過(guò)一次轉(zhuǎn)換；
if (colorOf(rightOf(sib)) == BLACK) {
setColor(leftOf(sib), BLACK);
setColor(sib, RED);
rotateRight(sib);
sib = rightOf(parentOf(x));
}
setColor(sib, colorOf(parentOf(x)));
setColor(parentOf(x), BLACK);
setColor(rightOf(sib), BLACK);
rotateLeft(parentOf(x));
x = root;
}
} else {
Entry<K,V> sib = leftOf(parentOf(x));
if (colorOf(sib) == RED) {
setColor(sib, BLACK);
setColor(parentOf(x), RED);
rotateRight(parentOf(x));
sib = leftOf(parentOf(x));
}
if (colorOf(rightOf(sib)) == BLACK &&
colorOf(leftOf(sib)) == BLACK) {
setColor(sib, RED);
x = parentOf(x);
} else {
if (colorOf(leftOf(sib)) == BLACK) {
setColor(rightOf(sib), BLACK);
setColor(sib, RED);
rotateLeft(sib);
sib = leftOf(parentOf(x));
}
setColor(sib, colorOf(parentOf(x)));
setColor(parentOf(x), BLACK);
setColor(leftOf(sib), BLACK);
rotateRight(parentOf(x));
x = root;
}
}
}
//如果該節(jié)點(diǎn)不是黑色的，或者是根節(jié)點(diǎn)，那么把他染黑；
setColor(x, BLACK);
}

static <K,V> TreeMap.Entry<K,V> successor(Entry<K,V> t) {
//如果為null，則返回
if (t == null)
return null;
//如果大兒子存在，那么沿著這條路下去，找到其這個(gè)枝條中最小的節(jié)點(diǎn)
else if (t.right != null) {
Entry<K,V> p = t.right;
while (p.left != null)
p = p.left;
return p;
} else {
//如果右邊子樹(shù)是空的，那么找到其長(zhǎng)輩節(jié)點(diǎn)中間第一個(gè)大于他的
Entry<K,V> p = t.parent;
Entry<K,V> ch = t;
while (p != null && ch == p.right) {
ch = p;
p = p.parent;
}
return p;
}
}

我們?cè)賮?lái)看一下我們?cè)讷@取其集合的時(shí)候的順序：

static final class KeySet<E> extends AbstractSet<E> implements NavigableSet<E> {
private final NavigableMap<E, Object> m;
KeySet(NavigableMap<E,Object> map) { m = map; }
public Iterator<E> iterator() {
if (m instanceof TreeMap)
return ((TreeMap<E,Object>)m).keyIterator();
else
return (Iterator<E>)(((TreeMap.NavigableSubMap)m).keyIterator());
}
public Iterator<E> descendingIterator() {
if (m instanceof TreeMap)
return ((TreeMap<E,Object>)m).descendingKeyIterator();
else
return (Iterator<E>)(((TreeMap.NavigableSubMap)m).descendingKeyIterator());
}
public int size() { return m.size(); }
public boolean isEmpty() { return m.isEmpty(); }
public boolean contains(Object o) { return m.containsKey(o); }
public void clear() { m.clear(); }
public E lower(E e) { return m.lowerKey(e); }
public E floor(E e) { return m.floorKey(e); }
public E ceiling(E e) { return m.ceilingKey(e); }
public E higher(E e) { return m.higherKey(e); }
public E first() { return m.firstKey(); }
public E last() { return m.lastKey(); }
public Comparator<? super E> comparator() { return m.comparator(); }
public E pollFirst() {
Map.Entry<E,Object> e = m.pollFirstEntry();
return e == null? null : e.getKey();
}
public E pollLast() {
Map.Entry<E,Object> e = m.pollLastEntry();
return e == null? null : e.getKey();
}
public boolean remove(Object o) {
int oldSize = size();
m.remove(o);
return size() != oldSize;
}
public NavigableSet<E> subSet(E fromElement, boolean fromInclusive,
E toElement, boolean toInclusive) {
return new TreeSet<E>(m.subMap(fromElement, fromInclusive,
toElement, toInclusive));
}
public NavigableSet<E> headSet(E toElement, boolean inclusive) {
return new TreeSet<E>(m.headMap(toElement, inclusive));
}
public NavigableSet<E> tailSet(E fromElement, boolean inclusive) {
return new TreeSet<E>(m.tailMap(fromElement, inclusive));
}
public SortedSet<E> subSet(E fromElement, E toElement) {
return subSet(fromElement, true, toElement, false);
}
public SortedSet<E> headSet(E toElement) {
return headSet(toElement, false);
}
public SortedSet<E> tailSet(E fromElement) {
return tailSet(fromElement, true);
}
public NavigableSet<E> descendingSet() {
return new TreeSet(m.descendingMap());
}
}

這個(gè)是返回的set，他的查找排序是利用的迭代模式委托給了迭代器，我們看看他的迭代器實(shí)現(xiàn)：

final class KeyIterator extends PrivateEntryIterator<K> {
KeyIterator(Entry<K,V> first) {
super(first);
}
public K next() {
return nextEntry().key;
}
}

其中獲取下一個(gè)nextEntry是：

final Entry<K,V> nextEntry() {
Entry<K,V> e = next;
if (e == null)
throw new NoSuchElementException();
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
next = successor(e);
lastReturned = e;
return e;
}

利用的successvor（），在開(kāi)始的分析中我們知道，successor的查找，是通過(guò)了樹(shù)的中序遍歷的

感謝各位的閱讀，以上就是“JDK的TreeMap怎么實(shí)現(xiàn)”的內(nèi)容了，經(jīng)過(guò)本文的學(xué)習(xí)后，相信大家對(duì)JDK的TreeMap怎么實(shí)現(xiàn)這一問(wèn)題有了更深刻的體會(huì)，具體使用情況還需要大家實(shí)踐驗(yàn)證。這里是億速云，小編將為大家推送更多相關(guān)知識(shí)點(diǎn)的文章，歡迎關(guān)注！

向AI問(wèn)一下細(xì)節(jié)

JDK的TreeMap怎么實(shí)現(xiàn)

猜你喜歡

最新資訊

相關(guān)推薦

相關(guān)標(biāo)簽