JDK的TreeMap怎么实现

发布时间：2021-12-31 16:00:30 作者：iii
来源：亿速云阅读：139

这篇文章主要讲解了“JDK的TreeMap怎么实现”，文中的讲解内容简单清晰，易于学习与理解，下面请大家跟着小编的思路慢慢深入，一起来研究和学习“JDK的TreeMap怎么实现”吧！

TreeMap的实现也是利用的红黑树，我们来看代码：

在TreeMap中包含着一个根结点：

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

这个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;
//颜色默认为黑色
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;
}
}

废话不多说，我们来看一下他的插入实现：

public V put(K key, V value) {
Entry<K,V> t = root;
//如果树是空树
if (t == null) {
//那么树根节点就是节点
root = new Entry<K,V>(key, value, null);
size = 1;
modCount++;
return null;
}
int cmp;
Entry<K,V> parent;
//否则利用提供的比较器进行比较
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
//如果已经有这个key，那么修改key，并且什么都可以不修改了
return t.setValue(value);
} while (t != null); //知道找到叶子节点；
}
else {
if (key == null)
throw new NullPointerException();
//如果没有提供外部的比较器，那么就利用内置的比较器
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<K,V>(key, value, parent);
//利用最后的判断，将这个节点变成该叶子节点的儿子；
if (cmp < 0)
parent.left = e;
else
parent.right = e;
//由于有可能破坏了红黑树的规则，现在进行调整；
fixAfterInsertion(e);
size++;
modCount++;
return null;
}

private void fixAfterInsertion(Entry<K,V> x) {
//首先将该新增节点染红，叶子节点(null)是黑色的;
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)));
}
}
}
//冲突会一直追溯到跟，把跟染黑，不违背根节点是黑色的特性，并且使得所有的树枝的黑色节点因此加1，冲突解决；
root.color = BLACK;
}

看完了增加，我们再来看看删除

public V remove(Object key) {
//查找到该节点
Entry<K,V> p = getEntry(key);
//不存在则结束
if (p == null)
return null;
V oldValue = p.value;
//删除
deleteEntry(p);
//返回原值
return oldValue;
}

查找该节点：

final Entry<K,V> getEntry(Object key) {
if (comparator != null)
//利用外部比较器
return getEntryUsingComparator(key);
if (key == null)
throw new NullPointerException();
//内置比较器
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;
}

外部比较器查找节点：

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--;
//如果删除的节点有两个子节点；
if (p.left != null && p.right != null) {
Entry<K,V> s = successor (p);
p.key = s.key;
p.value = s.value;
p = s;
}
//两个子节点的删除转化为了一个子节点的删除
//进行一个子节点的删除操作；
Entry<K,V> replacement = (p.left != null ? p.left : p.right);
//如果有一个以上的节点；重新接上树枝；
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;
//如果删除位置的新节点是黑色的，那么会少一个黑节点，调整
if (p.color == BLACK)
//调整新的节点，即删除节点的子节点；
fixAfterDeletion(replacement);
} else if (p.parent == null) { // return if we are the only node.
root = null;
} else {
//如果没有子节点
//红色的节点要可以直接删除，黑色的话，必须要经过调整；
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;
}
}
}

删除后的调整：

private void fixAfterDeletion(Entry<K,V> x) {
// 如果节点是黑色的；那么要经过调整，如果是红色的，可以直接修改成为黑色的，结束循环；
while (x != root && colorOf(x) == BLACK)
// 判断被删除节点是左子树；
if (x == leftOf(parentOf(x))) {
// 获得兄弟节点；
Entry<K,V> sib = rightOf(parentOf(x));
//兄弟节点是红色的
if (colorOf(sib) == RED) {
setColor(sib, BLACK);
setColor(parentOf(x), RED);
//开始旋转
rotateLeft(parentOf(x));
// 得到旋转后的新的兄弟节点；这个时候是黑色的
sib = rightOf(parentOf(x));
}
//判断侄子的颜色；如果两个都是黑色的
if (colorOf(leftOf(sib)) == BLACK &&
colorOf(rightOf(sib)) == BLACK) {
setColor(sib, RED);
x = parentOf(x);
} else {
// 只有一个是黑色的
// 如果是黑色的那个侄子位置不对，那么经过一次转换；
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;
}
}
}
//如果该节点不是黑色的，或者是根节点，那么把他染黑；
setColor(x, BLACK);
}

static <K,V> TreeMap.Entry<K,V> successor(Entry<K,V> t) {
//如果为null，则返回
if (t == null)
return null;
//如果大儿子存在，那么沿着这条路下去，找到其这个枝条中最小的节点
else if (t.right != null) {
Entry<K,V> p = t.right;
while (p.left != null)
p = p.left;
return p;
} else {
//如果右边子树是空的，那么找到其长辈节点中间第一个大于他的
Entry<K,V> p = t.parent;
Entry<K,V> ch = t;
while (p != null && ch == p.right) {
ch = p;
p = p.parent;
}
return p;
}
}

我们再来看一下我们在获取其集合的时候的顺序：

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());
}
}

这个是返回的set，他的查找排序是利用的迭代模式委托给了迭代器，我们看看他的迭代器实现：

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

其中获取下一个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（），在开始的分析中我们知道，successor的查找，是通过了树的中序遍历的

感谢各位的阅读，以上就是“JDK的TreeMap怎么实现”的内容了，经过本文的学习后，相信大家对JDK的TreeMap怎么实现这一问题有了更深刻的体会，具体使用情况还需要大家实践验证。这里是亿速云，小编将为大家推送更多相关知识点的文章，欢迎关注！

JDK的TreeMap怎么实现

相关阅读