1、本文主要内容
- TreeMap及Set介绍
- TreeMap源码解析
- Set源码解析
2、TreeMap及Set介绍
首先我们查看Set接口，Set接口定义了add方法，remove方法，唯独没有定义get方法，用户是无法单独获取set的某元素，只能通过遍历获取。
Set是接口，本期主要讲述其中两个实现，HashSet以及TreeSet。顾名思义，HashSet使用哈希表存储元素，而TreeSet使用树结构存储元素。接下来的源码分析可以知道，HashSet利用了成员变量HashMap存储元素，而TreeSet使用成员变量TreeMap来存储元素，这也是本文要介绍TreeMap的原因。
TreeMap使用红黑树来存储元素，不过它实现的接口是Map，它存储的是键值对。
3、TreeMap源码解析
红黑树 前期已有介绍，本文不再重复红黑树添加修复以及删除修复内容的介绍了，不过先回忆下红黑树的5大特性：
- 节点非黑即红
- 根节点为黑
- 叶结点（NIL结点，空结点）为黑
- 红色结点的子结点一定是黑色的，也就是说没有两个相连的红色结点
- 从根结点开始到每一个叶结点（NIL结点，空结点）之间的黑色结点数量相等
以上是红黑树的5大特性，依靠着上述特性，红黑树成为了相对平衡的二叉搜索树。
//put方法，存储元素
public V put(K key, V value) {
Entry<K,V> t = root;
if (t == null) {
//如果根结点为空，则这是插入的第一个元素，将它设置成根结点
compare(key, key); // type (and possibly null) check
root = new Entry<>(key, value, null);
size = 1;
modCount++;
return null;
}
int cmp;
Entry<K,V> parent;
// split comparator and comparable paths
//如果比较器不为null，则使用比较器来比较key之间的大小
Comparator<? super K> cpr = comparator;
if (cpr != null) {
do {
parent = t;
cmp = cpr.compare(key, t.key);
//如果key小于当前节点key，则将当前节点置为它的左子节点，反之则右子节点
//这是二叉搜索树的性质，左子节点小于父节点，父节点小于右子节点
if (cmp < 0)
t = t.left;
else if (cmp > 0)
t = t.right;
else
return t.setValue(value);
} while (t != null);
}
else {
//如果比较器为null，则将key转化为Comparable比较，逻辑同上一样
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);
}
//此时找到的parent即是新节点的parent节点
Entry<K,V> e = new Entry<>(key, value, parent);
//最后根据cmp的结果，确认新节点是左还是右子结点
if (cmp < 0)
parent.left = e;
else
parent.right = e;
//修复红黑树
fixAfterInsertion(e);
size++;
modCount++;
return null;
}
put方法比较简单，结合二叉搜索树的性质，找到正确的位置，插入新节点即可。在红黑树中，为了尽量少违背那5条特性，一律将新插入的节点颜色置为红色，最后修复红黑树，使之仍然是一颗正常的红黑树，如何修复新增节点的红黑树，请参考以前写的红黑树一文。
private void deleteEntry(Entry<K,V> p) {
modCount++;
//删除节点，所以size减一
size--;
// If strictly internal, copy successor's element to p and then make p
// point to successor.
//如果删除的节点左右子树都不为空，则需要找出中序遍历中的后续节代替当前节点
//后继节点可以是左子树中的最大结点，也可以是右子树中的最小节点
//最后删除后继节点
if (p.left != null && p.right != null) {
Entry<K,V> s = successor(p);
p.key = s.key;
p.value = s.value;
p = s;
} // p has 2 children
// Start fixup at replacement node, if it exists.
//经过上面的判断，此时p不可能左右子树都存在，将存在的其中一个或者空指针，替换要被删除的节点
Entry<K,V> replacement = (p.left != null ? p.left : p.right);
if (replacement != null) {
//如果替换的节点不为空，则将替换节点代替p结点
// Link replacement to parent
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;
// Null out links so they are OK to use by fixAfterDeletion.
//将p结点的关系斩断
p.left = p.right = p.parent = null;
// Fix replacement
if (p.color == BLACK)
//如果p结点是黑色的，现在删除p，性质5会违背，所以需要修复红黑树
fixAfterDeletion(replacement);
} else if (p.parent == null) { // return if we are the only node.
//如果p没有父节点，则说明p结点为根结点，将root置空
root = null;
} else { // No children. Use self as phantom replacement and unlink.
if (p.color == BLACK)
//同理，p颜色为黑色，那么修复红黑树
fixAfterDeletion(p);
if (p.parent != null) {
//p的替代节点为null，但父节点不为null的情况下，处理p父节点相关信息
if (p == p.parent.left)
p.parent.left = null;
else if (p == p.parent.right)
p.parent.right = null;
p.parent = null;
}
}
}
删除节点比添加节点稍复杂一些，尤其需要理解后继节点的含义，在删除节点p时，并不是直接删除节点p，如果p的两个子节点都存在的情况下，需要找出中序遍历下的p的后继节点，用后继节点代替p节点，最后删除的其实是后续节点。因为后继节点肯定最多只有一个子节点，位于树的底层，更加好删除一些。但删除后红黑树的修复更加复杂了，情况更多了。
4、Set源码解析
Set是接口，本期主要讲两个实现类，HashSet和TreeSet，但阅读源码后才知道，这两个实现类超级简单，因为它们所有的逻辑都是基于自身的成员变量HashMap和TreeMap，存、删除等都是调用成员变量的实现。
另外Set存储的不是键值对，但它们的成员变量存储的都是键值对，这是因为Set只用到了key值，value是一个默认值。
下面看看HashSet的存储和删除：
private transient HashMap<E,Object> map;
private static final Object PRESENT = new Object();
public boolean add(E e) {
return map.put(e, PRESENT)==null;
}
public boolean remove(Object o) {
return map.remove(o)==PRESENT;
}
public boolean contains(Object o) {
return map.containsKey(o);
}
代码实在太简单了，就不再介绍了。现在来看看TreeSet的方法：
private transient NavigableMap<E,Object> m;
TreeSet(NavigableMap<E,Object> m) {
this.m = m;
}
public TreeSet() {
this(new TreeMap<E,Object>());
}
由上述方法可知，TreeSet中的成员变量其实是TreeMap。
public boolean add(E e) {
return m.put(e, PRESENT)==null;
}
public boolean remove(Object o) {
return m.remove(o)==PRESENT;
}
添加和删除同HashSet一样。
那么HashSet和TreeSet之间有什么不同呢？TreeSet它是基于红黑树的，红黑树是二叉搜索树，如果采用中序遍历的话，它的key会从大到小按顺序排列，所以TreeSet它是有序的。
