TreeMap

/ Java / 没有评论 / 365浏览

在前几篇中我们主要介绍了底层是通过数组、链表、哈希表等方式实现的集合,今天我们来学习一种新的集合叫做TreeMap。TreeMap底层并不是通过哈希表的方式实现的,而是采用了一种全新的数据结构,红黑树结构存储的。下面我们简单介绍一下红黑树的相关知识。

红黑树也叫红黑二叉树,所以它也是二叉树的一种,除了具有二叉树的基本特性外,还有自己独特的一些特性。二叉树也就是说在每个树节点最多有两个子节点的树结构。并且二叉树的子节点有左右之分,且左节点的值都要小于右节点的。所以,通过二叉树结构存储的数据在检索元素时速度会很快,因为从树根节点检索时,就会过滤掉将近一半的数据(理想情况下)。并且红黑树是一种平衡二叉树,这也是红黑树的一种特性。下面我们来看一下什么是平衡二叉树。

平衡二叉树主要具有以下特性:它是一棵空树或它的左右两个子树的高度差的绝对值不超过1,并且左右两个子树也都是一棵平衡二叉树。说白了红黑树就是平衡二叉树的一种实现算法,除此算法外还有AVL、Treap、伸展树、SBT等算法。(主要来源为百度百科)

QQ截图20170508155027.jpg

下面我们继续介绍红黑树的其它特性,红黑树顾名思义就是通过设置红色或黑色等状态来保证树的平衡的。所以红黑树的主要特性如下:

上面是红黑树的相关特性,也就是说无论任何时候红黑树都必须保证具有上面的全部特性。但是在我们日常开发时,常常需要向集合中添加或者删除元素,那么在执行上述操作时,难免会破坏红黑树的相关特性,那么这时应该怎么处理呢?事实上,每当我们执行添加或者删除操作时,如果破坏了红黑树的特性,那么这时就会进行树的旋转,以保证红黑树的相关特性。红黑树的旋转主要分为左旋和右旋。下面我们分别看看具体的实现。

QQ截图20170508162144.jpg

红黑树进行左旋的逻辑是,将要左旋的节点的父节点设置为自己的左节点,然后将原左节点设置为新左节点的右节点。

QQ截图20170508162432.jpg

红黑树进行右旋的逻辑是,将要右旋的节点的父节点设置为自己的右节点,然后将原右节点设置为新右节点的左节点。

现在我们已经知道了有关红黑树的所有知识,下面我们分析一下TreeMap的底层源码,看TreeMap底层是怎么实现红黑树的逻辑的。我们还是和其它集合一样还是先看TreeMap的初始化。

public TreeMap() {
comparator = null;
}
private final Comparator<? super K> comparator;

上面是TreeMap的无参构造函数,我们发现当我们通过参构造函数创建TreeMap对象时,并不会执行底层树结构的初始化,而只是将comparator设置为空。那么通过我们以往分析其它集合时总结的规律,TreeMap的初始化一定是在第一次调用put方法时执行的。下面我们将重点看一下TreeMap中的put方法。

private transient Entry<K,V> root; // 创建一个实例变量 用transient关键字修饰变量不能被序列化 
static final class Entry<K,V> implements Map.Entry<K,V> { // 定义一个Entry对象用来保存底层数据
K key;  // 保存key信息
V value;   // 保存value信息
Entry<K,V> left; // 保存当前节点的左节点
Entry<K,V> right; // 保存当前节点的右节点
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; // 将实例变量root赋值给t
if (t == null) { // 判断t是否为空 如果为空 说明TreeMap第一次调用put方法
compare(key, key); 调用Comparable接口比较两个key 如果两个key相等则返回0 如果前面key比后面的大则返回大于0 否则返回小于0

root = new Entry<>(key, value, null); // 创建新节点保存数据并将此节点赋值给root变量
size = 1;
modCount++;
return null;
}
int cmp;
Entry<K,V> parent; // 创建一个保存当前节点父节点的局部变量
Comparator<? super K> cpr = comparator; // 将实例变量中的排序接口赋值给cpr 因为保存到TreeMap中的元素必须可以进行比较 所以TreeMap为我们提供了一个可以指定排序接口的构造方法来方便我们自由的按照我们的要求排序TreeMap中的元素,如果没有指定则执行默认排序规则
if (cpr != null) { // cpr不为空,说明TreeMap实例化时调用了有参的Comparator接口的构造方法
do {
parent = t; // 因为TreeMap第二次调用put方法是t一定不为空,所以此代码的目的是将TreeMap中已经保存的元素设置为当前要添加的元素的父节点
cmp = cpr.compare(key, t.key); // 比较当前节点与父节点的key值的大小,以此来判断当前节点是父节点的左节点还是右节点
if (cmp < 0)
t = t.left; // 小于0说明当前节点的key比父节点小 所以将保存为父节点的左节点
else if (cmp > 0)
t = t.right; // 大于0说说明当前节点的key比父节点大 所以将保存为父节点的右节点
else
return t.setValue(value); // 等于为说明当前节点的key与父节点的key相同 于是将当前节点的value覆盖父节点中的value
} while (t != null);
}
else {
if (key == null) // 如果当前元素的key等于null则直接抛出异常,这说明在TreeMap中不能将null做为key存储TreeMap中
throw new NullPointerException();
@SuppressWarnings("unchecked")
Comparable<? super K> k = (Comparable<? super K>) key; // 采用默认的比较
do {
parent = t; // 第一次时将根节点赋值给parent 然后循环更改t的值 直到确认当前节点要保存的位置
cmp = k.compareTo(t.key); // 比较当前key的值
if (cmp < 0)
t = t.left; // 将当前节点的左节点赋值给t
else if (cmp > 0)
t = t.right; // 将当前节点的右节点赋值给t
else
return t.setValue(value); // 覆盖相同的key的节点的value值
} while (t != null);
}
Entry<K,V> e = new Entry<>(key, value, parent); // 创建一个新节点保存key和value并设置当前节点的父节点 父节点就是上述循环中确定的节点
if (cmp < 0)
parent.left = e; // 设置父节点为当前元素的左节点
else
parent.right = e;// 设置父节点为当前元素的右节点
fixAfterInsertion(e); // 执行树的旋转功能 包括左旋和右旋
size++;
modCount++;
return null;
}

下面我们看一下上述方法中提到的fixAfterInsertion方法的具体逻辑也就是左旋和右旋的具体实现。

private void fixAfterInsertion(Entry<K,V> 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;
}
private void rotateRight(Entry<K,V> p) {
if (p != null) {
Entry<K,V> l = p.left;
p.left = l.right;
if (l.right != null) l.right.parent = p;
l.parent = p.parent;
if (p.parent == null)
root = l;
else if (p.parent.right == p)
p.parent.right = l;
else p.parent.left = l;
l.right = p;
p.parent = l;
}
}
private void rotateLeft(Entry<K,V> p) {
if (p != null) {
Entry<K,V> r = p.right;
p.right = r.left;
if (r.left != null)
r.left.parent = p;
r.parent = p.parent;
if (p.parent == null)
root = r;
else if (p.parent.left == p)
p.parent.left = r;
else
p.parent.right = r;
r.left = p;
p.parent = r;
}
}

左旋和右旋的具体逻辑这里就不在详细分析了,主要的实现逻辑就是上面所说的,左旋就是讲要左旋的节点的父节点设置为自己的左节点,然后将原左节点设置为新左节点的右节点。右旋就是讲右旋的的父节点设置为自己的右节点,然后将原右节点设置为新右节点的左节点。

public class Test {
  public static void main(String [] args) {
    TreeMap treeMap = new TreeMap();
    treeMap.put(new Object(), null);
    System.out.println(treeMap);
  }
}
Exception in thread "main" java.lang.ClassCastException: java.lang.Object cannot be cast to java.lang.Comparable
	at java.util.TreeMap.compare(TreeMap.java:1294)
	at java.util.TreeMap.put(TreeMap.java:538)
	at com.jilinwula.service.Test.main(Test.java:75)