集合框架 Map篇（3）—-TreeMap及红黑树、EnumMap

来源：互联网

Map
------
1.HashMap
2.LinkedHashMap
3.IdentityHashMap
4.WeakHashMap
5.TreeMap
6.EnumMap
7.ConcurrentHashMap
8.ConcurrentSkipListMap
--------------------------------------

--------EnumMap----------------------------------------

public class EnumMap<K extends Enum<K>,V> extends AbstractMap<K,V> implements Serializable, Cloneable

与枚举类型键一起使用的专用 Map 实现。枚举映射中所有键都必须来自单个枚举类型，该枚举类型在创建映射时显式或隐式地指定。枚举映射在内部表示为数组。此表示形式非常紧凑且高效。

枚举映射根据其键的自然顺序来维护（该顺序是声明枚举常量的顺序）。在 collection 视图（keySet()、entrySet() 和 values()）所返回的迭代器中反映了这一点。

eg.:

import java.util.EnumMap;

enum WeekEnum {
Monday,Tuesday,Wednesday,Thursday,Friday,Saturday,Sunday
}

public class EnumMapTest {

private EnumMap<WeekEnum, String> enumMap = new EnumMap<WeekEnum, String>(WeekEnum.class);

public EnumMapTest() {
enumMap.put(WeekEnum.Monday, "星期一，一周开始");
enumMap.put(WeekEnum.Thursday, "星期二，一周第二天");
enumMap.put(WeekEnum.Wednesday, "星期三，好好工作……");
enumMap.put(WeekEnum.Thursday, "星期四，……");
enumMap.put(WeekEnum.Friday, "星期五，……");
enumMap.put(WeekEnum.Saturday, "星期六，……");
enumMap.put(WeekEnum.Sunday, "星期天，休息一下……");
}

public String getDayDescription(WeekEnum day) {
return this.enumMap.get(day);
}

public static void main(String[] args) {
String dayDesc=new EnumMapTest().enumMap.get(WeekEnum.Sunday);
System.err.println(dayDesc);
}

}

上面是一个简单的例子。由于EnumMap的具有枚举类型的特点，类型固定且枚举值的个数固定，所以EnumMap效率是比较高的，可以结合具体的应用（特别像例子中的那样，元素的个数较少且较固定时考虑使用EnumMap存储数据）

--------TreeMap------------------------------------------

TreeMap是一种支持排序的Map，其实现方式和HashMap有较大区别，是红黑树数据结构的实现。

/**
*TreeMap中节点的存储结构
*/
static final class Entry<K,V> implements Map.Entry<K,V> {
/**6个变量域：键、值对、左、右兄弟、父节点、颜色属性 */
K key;
V value;
Entry<K,V> left = null;//
Entry<K,V> right = null;
Entry<K,V> parent;
boolean color = BLACK;
......
}

put(Object key,Object value):

它是一个典型的基于红黑树的实现，因此要求一定要有key比较的方法，要么传入Comparator实现，要么key对像实现Comparator接口。
/**
*通过“键值对”初始化Entry并把该Entry放到红黑树结构中（如果该key对应的Entry存在，其value就替换为新的value）
*/
public V put(K key, V value) {
//临时变量t指向根节点
Entry<K,V> t = root;
//如果t为空，也就是root为空，TreeMap是空链的情况下，根据键值对创建Entry，并将其置为root根节点
if (t == null) {
root = new Entry<K,V>(key, value, null);//父节点为null
size = 1;//size表示节点的个数
modCount++;//modCount表示链表的变化次数
return null;
}
int cmp;
Entry<K,V> parent;
/**
*根据"比较器"comparator为null与否，采取定制比较或默认比较（key的Comparable）不同的方式
*然后，按照"二叉排序树"的方式从根节点开始查找。如果找到了就覆盖旧的value，并返回旧的value。
*/
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();
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);
}
/**
*如果上述遍历没有找到对应的key，则把key-value和最后的遍历得到的parent（也就是待插入位置的parent）
*构造成新的Entry，作为新的插入节点。
*/
Entry<K,V> e = new Entry<K,V>(key, value, parent);
//设置parent和该新节点的关系
if (cmp < 0)
parent.left = e;
else
parent.right = e;
fixAfterInsertion(e);//插入新节点后，可能会改变原有的红黑树结构，要进行修复
size++;
modCount++;
return null;
}

/** 红黑树插入后修复算法（该算法来源于CLR--算法3作者的姓氏第一个字母） */
private void fixAfterInsertion(Entry<K,V> x) {
//默认新插入的节点颜色为红色（这是为了尽量不改变红黑树黑节点的个数，具体可以查看"红黑树"的属性）
x.color = RED;
/** 直到 x 节点的父节点不是根，且 x 的父节点不是红色
(由于当x的父亲节点是黑色节点的时候，直接插入不会影响到红黑树的性质，所有就没有必要进行下面的操作了,
所以插入时，只考虑其父亲节点为红色的情况，只有这种情况下红黑树才需要修复操作)*/
while (x != null && x != root && x.parent.color == RED) {
/**
*新插入节点x的父节点为红色的时候又分为一下几种情况：
*1 x 的父节点P是其父节点G的左子节点：
*1.1 x的父亲节点p的兄弟节点为红色.解决办法：父设黑，父的兄设黑，父的父设红并以父的父为新节点往上遍历直到root涂黑。
*1.2 x的父亲节点p的兄弟节点为黑色.(此时，又分x是其父的左和右孩子两种情况)
* 1.2.1 x是其父右子。解决办法： x变黑，父的父变红，父左旋转，父的父右旋转。
* 1.2.2 x是其父左子。解决办法：父变黑，父的父变红，          父的父右旋转，
*
*2 x 的父节点P是其父节点G的右子节点（道理同上）
*/
// 1 如果 x 的父节点P是其父节点G的左子节点
if (parentOf(x) == leftOf(parentOf(parentOf(x)))) {
Entry<K,V> y = rightOf(parentOf(parentOf(x)));
//1.1 如果x的父亲节点p的兄弟节点为红色
if (colorOf(y) == RED) {
setColor(parentOf(x), BLACK);//将x的父亲节点设为黑色
setColor(y, BLACK);          //将x的父亲节点兄弟节点设为黑色
setColor(parentOf(parentOf(x)), RED);//将x的父亲节点的父亲节点设为红色
x = parentOf(parentOf(x));           //将x设为其父亲节点的父亲节点，以便继续往上遍历
} else {//1.2 如果x的父亲节点p的兄弟节点为黑色
if (x == rightOf(parentOf(x))) {//1.2.1 下面左转的目的是变成1.2.2的情况
x = parentOf(x);//x指向其父
rotateLeft(x); //当前的x指向左旋转
}
//1.2.2情况的处理
setColor(parentOf(x), BLACK); //父设黑
setColor(parentOf(parentOf(x)), RED);//父父设红
rotateRight(parentOf(parentOf(x)));//父父右旋转
}
} else {//2 道理同上，只是出现right的地方换成了left，出现left的地方换成了right
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根节点置黑，以满足“红黑树”黑头黑尾的性质。
root.color = BLACK;
}

---------------

TreeMap的删除操作的实现：

private void deleteEntry(Entry<K,V> p) {
modCount++; //修改次数加1
size--; //节点个数减1
// 如果被删除节点的左子树、右子树都不为空
if (p.left != null && p.right != null) {
// 用 p 节点的中序后继节点代替 p 节点
Entry<K,V> s = successor (p);
p.key = s.key;
p.value = s.value;
p = s;
}

/**

*经过上面的操作（用 p 节点的中序后继节点代替 p 节点），实际要执行的删除操作就

*变成了针对p的中序后继节点（如果存在的话）的操作：

*既然要删除的节点是后继节点，那么要删除的节点的左子树一定为空，所以：

* 1 当（删除的节点）p为黑色时就有两种情况：

* 1.1 p的左右均为null；

* 1.2 p的左为空，右子树为一单个红色节点（并且该红色节点的左右为null，如果不为空就不会满足红黑树的性质了）

* 2 当p为红色时：其左右子树比为null（也只有这样才能满足红黑树的性质）

*/
// 如果 p 节点的左节点存在，replacement 代表左节点；否则代表右节点。
Entry<K,V> replacement = (p.left != null ? p.left : p.right);
if (replacement != null) { //1.2的情况
replacement.parent = p.parent;
// 如果 p 没有父节点，则 replacemment 变成父节点
if (p.parent == null)
root = replacement;
// 如果 p 节点是其父节点的左子节点，则把其父左设为replacement
else if (p == p.parent.left)
p.parent.left = replacement;
// 如果 p 节点是其父节点的右子节点，则把其父右设为replacement
else
p.parent.right = replacement;
p.left = p.right = p.parent = null;
// 由于当p是红色节点时，直接删除后不会影响到红黑树的高度，所以就不用修复，当为黑节点时需修复红黑树
if (p.color == BLACK)
fixAfterDeletion(replacement);

} else if (p.parent == null) { // 如果 p 节点没有父节点，置为空链
root = null;
} else { 1.1或2的情况：即要删除的p节点的左右子树均为null
if (p.color == BLACK) //如果是p为黑色，就进行修复（红色时不必）
// 修复红黑树
fixAfterDeletion(p);

if (p.parent != null) { //在p父不为空的情况下，对其父的左（或右）节点进行删除后的置空处理
// 如果 p 是其父节点的左子节点
if (p == p.parent.left)
p.parent.left = null;
// 如果 p 是其父节点的右子节点
else if (p == p.parent.right)
p.parent.right = null;
p.parent = null;
}
}
------

// 删除节点后修复红黑树
private void fixAfterDeletion(Entry<K,V> x)
{

/**

*由于x为红的情况不存在修复的情况，所以

*当x为黑色是修复存在如下情况：

*1 x 是其父节点的左子节点

* 1.1 当删除的节点有一个红孩子时。解决办法：红孩子目前属于删除节点父的一个孩子，把该孩子变成黑色。

* 1.2 当删除的节点左右子为null的情况下：

* 1.2.1 删除节点的兄弟节点为红色。解决办法：父变红，兄变黑，父左旋转。

* 1.2.2 删除节点的兄弟节点为黑色。（又有多种情况）

* 1.2.2.1 兄有两个黑子节点。解决办法：兄变红，子变黑，红父时变黑（黑父时，从黑父往上遍历）

* 1.2.2.2 兄的子节点左黑右红。解决办法：兄变父色，父变黑，兄红子变黑，父左旋转。

* 1.2.2.3 兄的子节点左红右黑。解决办法：兄红子变父色，父变黑，兄右旋转，父左旋转。

*2 x 是其父节点的右子节点（道理同上）

*/
// 直到 x 不是根节点，且 x 的颜色是黑色
while (x != root && colorOf(x) == BLACK) {
// 如果 x 是其父节点的左子节点
if (x == leftOf(parentOf(x))) { //1 情况
// 获取 x 节点的兄弟节点
Entry<K,V> sib = rightOf(parentOf(x));
// 如果 sib 节点是红色
if (colorOf(sib) == RED) { //1.2.1 情况
// 将 sib 节点设为黑色
setColor(sib, BLACK);
// 将 x 的父节点设为红色
setColor(parentOf(x), RED);
rotateLeft(parentOf(x));
// 再次将 sib 设为 x 的父节点的右子节点
sib = rightOf(parentOf(x));
}
// 如果 sib 的两个子节点都是黑色
if (colorOf(leftOf(sib)) == BLACK && colorOf(rightOf(sib)) == BLACK) { // 1.2.2.1 情况
// 将 sib 设为红色
setColor(sib, RED);
// 让 x 等于 x 的父节点，继续遍历
x = parentOf(x);
} else {
// 如果 sib 的只有右子节点是黑色
if (colorOf(rightOf(sib)) == BLACK) { // 1.2.2.3 情况，下面几行操作是先将其转换成1.2.2.2的情况
// 将 sib 的左子节点也设为黑色
setColor(leftOf(sib), BLACK);
// 将 sib 设为红色
setColor(sib, RED);
rotateRight(sib);
sib = rightOf(parentOf(x));
}

// 1.2.2.2 情况
// 设置 sib 的颜色与 x 的父节点的颜色相同
setColor(sib, colorOf(parentOf(x)));
// 将 x 的父节点设为黑色
setColor(parentOf(x), BLACK);
// 将 sib 的右子节点设为黑色
setColor(rightOf(sib), BLACK);
rotateLeft(parentOf(x));
x = root;
}
} else { // 2情况（道理同上）

// 获取 x 节点的兄弟节点
Entry<K,V> sib = leftOf(parentOf(x));
// 如果 sib 的颜色是红色
if (colorOf(sib) == RED) {
// 将 sib 的颜色设为黑色
setColor(sib, BLACK);
// 将 sib 的父节点设为红色
setColor(parentOf(x), RED);
rotateRight(parentOf(x));
sib = leftOf(parentOf(x));
}
// 如果 sib 的两个子节点都是黑色
if (colorOf(rightOf(sib)) == BLACK && colorOf(leftOf(sib)) == BLACK) {
// 将 sib 设为红色
setColor(sib, RED);
// 让 x 等于 x 的父节点
x = parentOf(x);
} else {
// 如果 sib 只有左子节点是黑色
if (colorOf(leftOf(sib)) == BLACK) {
// 将 sib 的右子节点也设为黑色
setColor(rightOf(sib), BLACK);
// 将 sib 设为红色
setColor(sib, RED);
rotateLeft(sib);
sib = leftOf(parentOf(x));
}
// 将 sib 的颜色设为与 x 的父节点颜色相同
setColor(sib, colorOf(parentOf(x)));
// 将 x 的父节点设为黑色
setColor(parentOf(x), BLACK);
// 将 sib 的左子节点设为黑色
setColor(leftOf(sib), BLACK);
rotateRight(parentOf(x));
x = root;
}
}
}