目录
1 TreeMap基本介绍
- Java TreeMap实现了SortedMap接口，也就是说会按照key的大小顺序对Map中的元素进行排序
- key大小的评判可以通过其本身的自然顺序(natural ordering)，也可以通过构造时传入的比较器(Comparator)。
- TreeMap底层通过红黑树实现
- TreeMap是非同步的。可以通过如下方式将TreeMap包装成同步的：SortedMap m = Collections.synchronizedSortedMap(new TreeMap(...));
- TreeMap 跟 HashMap是两种不同的结构，TreeMap没有使用hash相关概念
2 红黑树数据结构回顾
- 每个节点颜色不是黑色，就是红色
- 根节点是黑色的
- 红色节点不能连续
- 对于每个节点，从该节点到其树尾端的简单路径上，均包含相同数目的黑色节点
3 成员变量
private final Comparator<? super K> comparator; //排序器，如果空，按照key的字典顺序来排序（升序）；comparator为空时用Comparable的排序接口
private transient Entry<K,V> root; //根节点
private transient int size = 0; //树中entry个数 ，即红黑树大小
private transient int modCount = 0; //数结构被修改的次数的
/**
* Fields initialized to contain an instance of the entry set view
* the first time this view is requested. Views are stateless, so
* there's no reason to create more than one.
*/
private transient EntrySet entrySet;
private transient KeySet<K> navigableKeySet;
private transient NavigableMap<K,V> descendingMap;
/**
* Dummy value serving as unmatchable fence key for unbounded
* SubMapIterators
*/
private static final Object UNBOUNDED = new Object();
private static final boolean RED = false; //红节点 默认false
private static final boolean BLACK = true; // 黑节点 默认true
4 内部类Entry
它是组成树的节点的类型
static final class Entry<K,V> implements Map.Entry<K,V> {
K key; // key
V value; //value
Entry<K,V> left; //左孩子
Entry<K,V> right; //右孩子
Entry<K,V> parent; //父节点
boolean color = BLACK; //默认黑色
//根据 key value 父节点创建新节点
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;
}
//替换value，返回旧value
public V setValue(V value) {
V oldValue = this.value;
this.value = value;
return oldValue;
}
// 重写equals方法：key 和 value的引用都相等
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());
}
//重写hashCode方法，返回 key 和 value的hashCode 的异或运算结构
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;
}
}
5 构造函数
// 构造函数一：不指定排序器。按照key的字典顺序来排序（升序）
public TreeMap() {
comparator = null;
}
// 构造函数二：指定排序器
public TreeMap(Comparator<? super K> comparator) {
this.comparator = comparator;
}
//构造函数三：构造并返回跟参数m有相同键值映射结构的treeMap（m变为红黑树）
public TreeMap(Map<? extends K, ? extends V> m) {
comparator = null;
putAll(m);
}
//构造函数四：构造并返回跟参数m（有序的）有相同键值映射结构的treeMap
public TreeMap(SortedMap<K, ? extends V> m) {
comparator = m.comparator();
try {
buildFromSorted(m.size(), m.entrySet().iterator(), null, null);
} catch (java.io.IOException cannotHappen) {
} catch (ClassNotFoundException cannotHappen) {
}
}
Comparator Integer类型倒序排序
public static void main(String[] args) {
TreeMap treeMap = new TreeMap<