JDK的TreeMap怎么实现

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

创新互联专业提供成都主机托管四川主机托管成都服务器托管四川服务器托管，支持按月付款！我们的承诺：贵族品质、平民价格，机房位于中国电信/网通/移动机房，香港机房服务器托管服务有保障！

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

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

private transient Entry root = null;

这个Entry代码如下：

static final class Entry implements Map.Entry {
K key;
V value;
//指向小儿子
Entry left = null;
//指向大儿子
Entry right = null;
//指向父亲
Entry parent;
//颜色默认为黑色
boolean color = BLACK;
Entry(K key, V value, Entry 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 t = root;
//如果树是空树
if (t == null) {
//那么树根节点就是节点
root = new Entry(key, value, null);
size = 1;
modCount++;
return null;
}
int cmp;
Entry parent;
//否则利用提供的比较器进行比较
Comparator 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 k = (Comparable) 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 e = new Entry(key, value, parent);
//利用最后的判断，将这个节点变成该叶子节点的儿子；
if (cmp < 0)
parent.left = e;
else
parent.right = e;
//由于有可能破坏了红黑树的规则，现在进行调整；
fixAfterInsertion(e);
size++;
modCount++;
return null;
}

private void fixAfterInsertion(Entry x) {
//首先将该新增节点染红，叶子节点(null)是黑色的;
x.color = RED;
//如果他的父亲是红色的，那么冲突开始；
while (x != null && x != root && x.parent.color == RED) {
//如果是左子数；
if (parentOf(x) == leftOf(parentOf(parentOf(x)))) {
Entry 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 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 p = getEntry(key);
//不存在则结束
if (p == null)
return null;
V oldValue = p.value;
//删除
deleteEntry(p);
//返回原值
return oldValue;
}

查找该节点：

final Entry getEntry(Object key) {
if (comparator != null)
//利用外部比较器
return getEntryUsingComparator(key);
if (key == null)
throw new NullPointerException();
//内置比较器
Comparable k = (Comparable) key;
Entry 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 getEntryUsingComparator(Object key) {
K k = (K) key;
Comparator cpr = comparator;
if (cpr != null) {
Entry 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 p) {
modCount++;
size--;
//如果删除的节点有两个子节点；
if (p.left != null && p.right != null) {
Entry s = successor (p);
p.key = s.key;
p.value = s.value;
p = s;
}
//两个子节点的删除转化为了一个子节点的删除
//进行一个子节点的删除操作；
Entry 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 x) {
// 如果节点是黑色的；那么要经过调整，如果是红色的，可以直接修改成为黑色的，结束循环；
while (x != root && colorOf(x) == BLACK)
// 判断被删除节点是左子树；
if (x == leftOf(parentOf(x))) {
// 获得兄弟节点；
Entry 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 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 TreeMap.Entry successor(Entry t) {
//如果为null，则返回
if (t == null)
return null;
//如果大儿子存在，那么沿着这条路下去，找到其这个枝条中最小的节点
else if (t.right != null) {
Entry p = t.right;
while (p.left != null)
p = p.left;
return p;
} else {
//如果右边子树是空的，那么找到其长辈节点中间第一个大于他的
Entry p = t.parent;
Entry ch = t;
while (p != null && ch == p.right) {
ch = p;
p = p.parent;
}
return p;
}
}

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

static final class KeySet extends AbstractSet implements NavigableSet {
private final NavigableMap m;
KeySet(NavigableMap map) { m = map; }
public Iterator iterator() {
if (m instanceof TreeMap)
return ((TreeMap)m).keyIterator();
else
return (Iterator)(((TreeMap.NavigableSubMap)m).keyIterator());
}
public Iterator descendingIterator() {
if (m instanceof TreeMap)
return ((TreeMap)m).descendingKeyIterator();
else
return (Iterator)(((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 comparator() { return m.comparator(); }
public E pollFirst() {
Map.Entry e = m.pollFirstEntry();
return e == null? null : e.getKey();
}
public E pollLast() {
Map.Entry 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 subSet(E fromElement, boolean fromInclusive,
E toElement, boolean toInclusive) {
return new TreeSet(m.subMap(fromElement, fromInclusive,
toElement, toInclusive));
}
public NavigableSet headSet(E toElement, boolean inclusive) {
return new TreeSet(m.headMap(toElement, inclusive));
}
public NavigableSet tailSet(E fromElement, boolean inclusive) {
return new TreeSet(m.tailMap(fromElement, inclusive));
}
public SortedSet subSet(E fromElement, E toElement) {
return subSet(fromElement, true, toElement, false);
}
public SortedSet headSet(E toElement) {
return headSet(toElement, false);
}
public SortedSet tailSet(E fromElement) {
return tailSet(fromElement, true);
}
public NavigableSet descendingSet() {
return new TreeSet(m.descendingMap());
}
}

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

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

其中获取下一个nextEntry是：

final Entry nextEntry() {
Entry 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怎么实现
网站URL：http://scyanting.com/article/jdcgpj.html

JDK的TreeMap怎么实现

其他资讯