构造方法
// 默认构造函数。使用该构造函数，TreeMap中的元素按照自然排序进行排列。
TreeMap()
// 创建的TreeMap包含Map
TreeMap(Map<? extends K, ? extends V> copyFrom)
// 指定Tree的比较器
TreeMap(Comparator<? super K> comparator)
// 创建的TreeSet包含copyFrom
TreeMap(SortedMap<K, ? extends V> copyFrom)
常见用法
比较器。用来给TreeMap排序
private final Comparator<? super K> comparator;
TreeMap是红黑树实现的，root是红黑树的根节点
private transient Entry<K,V> root = null;
红黑树的节点总数
private transient int size = 0;
记录红黑树的修改次数
private transient int modCount = 0;
返回TreeMap中是否保护“键(key)”
public boolean containsKey(Object key) {
return getEntry(key) != null;
}
返回TreeMap中是否保护"值(value)"
public boolean containsValue(Object value) {
// getFirstEntry() 是返回红黑树的第一个节点
// successor(e) 是获取节点e的后继节点
for (Entry<K,V> e = getFirstEntry(); e != null; e = successor(e))
if (valEquals(value, e.value))
return true;
return false;
}
获取“键(key)”对应的“值(value)”
public V get(Object key) {
// 获取“键”为key的节点(p)
Entry<K,V> p = getEntry(key);
// 若节点(p)为null，返回null；否则，返回节点对应的值
return (p==null ? null : p.value);
}
public Comparator<? super K> comparator() {
return comparator;
}
获取第一个节点对应的key
public K firstKey() {
return key(getFirstEntry());
}
获取最后一个节点对应的key
public K lastKey() {
return key(getLastEntry());
}
将map中的全部节点添加到TreeMap中
public void putAll(Map<? extends K, ? extends V> map) {
// 获取map的大小
int mapSize = map.size();
// 如果TreeMap的大小是0,且map的大小不是0,且map是已排序的“key-value对”
if (size==0 && mapSize!=0 && map instanceof SortedMap) {
Comparator c = ((SortedMap)map).comparator();
// 如果TreeMap和map的比较器相等；
// 则将map的元素全部拷贝到TreeMap中，然后返回！
if (c == comparator || (c != null && c.equals(comparator))) {
++modCount;
try {
buildFromSorted(mapSize, map.entrySet().iterator(),
null, null);
} catch (java.io.IOException cannotHappen) {
} catch (ClassNotFoundException cannotHappen) {
}
return;
}
}
// 调用AbstractMap中的putAll();
// AbstractMap中的putAll()又会调用到TreeMap的put()
super.putAll(map);
}
获取TreeMap中“键”为key的节点
final Entry<K,V> getEntry(Object key) {
// 若“比较器”为null，则通过getEntryUsingComparator()获取“键”为key的节点
if (comparator != null)
return getEntryUsingComparator(key);
if (key == null)
throw new NullPointerException();
Comparable<? super K> k = (Comparable<? super K>) key;
// 将p设为根节点
Entry<K,V> p = root;
while (p != null) {
int cmp = k.compareTo(p.key);
// 若“p的key” < key，则p=“p的左孩子”
if (cmp < 0)
p = p.left;
// 若“p的key” > key，则p=“p的左孩子”
else if (cmp > 0)
p = p.right;
// 若“p的key” = key，则返回节点p
else
return p;
}
return null;
}
获取TreeMap中“键”为key的节点(对应TreeMap的比较器不是null的情况)
final Entry<K,V> getEntryUsingComparator(Object key) {
K k = (K) key;
Comparator<? super K> cpr = comparator;
if (cpr != null) {
// 将p设为根节点
Entry<K,V> p = root;
while (p != null) {
int cmp = cpr.compare(k, p.key);
// 若“p的key” < key，则p=“p的左孩子”
if (cmp < 0)
p = p.left;
// 若“p的key” > key，则p=“p的左孩子”
else if (cmp > 0)
p = p.right;
// 若“p的key” = key，则返回节点p
else
return p;
}
}
return null;
}
获取TreeMap中不小于key的最小的节点；
若不存在(即TreeMap中所有节点的键都比key大)，就返回null
final Entry<K,V> getCeilingEntry(K key) {
Entry<K,V> p = root;
while (p != null) {
int cmp = compare(key, p.key);
// 情况一：若“p的key” > key。
// 若 p 存在左孩子，则设 p=“p的左孩子”；
// 否则，返回p
if (cmp < 0) {
if (p.left != null)
p = p.left;
else
return p;
// 情况二：若“p的key” < key。
} else if (cmp > 0) {
// 若 p 存在右孩子，则设 p=“p的右孩子”
if (p.right != null) {
p = p.right;
} else {
// 若 p 不存在右孩子，则找出 p 的后继节点，并返回
// 注意：这里返回的 “p的后继节点”有2种可能性：第一，null；第二，TreeMap中大于key的最小的节点。
// 理解这一点的核心是，getCeilingEntry是从root开始遍历的。
// 若getCeilingEntry能走到这一步，那么，它之前“已经遍历过的节点的key”都 > key。
// 能理解上面所说的，那么就很容易明白，为什么“p的后继节点”又2种可能性了。
Entry<K,V> parent = p.parent;
Entry<K,V> ch = p;
while (parent != null && ch == parent.right) {
ch = parent;
parent = parent.parent;
}
return parent;
}
// 情况三：若“p的key” = key。
} else
return p;
}
return null;
}
获取TreeMap中大于key的最小的节点。
// 若不存在，就返回null。
final Entry<K,V> getHigherEntry(K key) {
Entry<K,V> p = root;
while (p != null) {
int cmp = compare(key, p.key);
if (cmp < 0) {
if (p.left != null)
p = p.left;
else
return p;
} else {
if (p.right != null) {
p = p.right;
} else {
Entry<K,V> parent = p.parent;
Entry<K,V> ch = p;
while (parent != null && ch == parent.right) {
ch = parent;
parent = parent.parent;
}
return parent;
}
}
}
return null;
}
删除TreeMap中的键为key的节点，并返回节点的值
public V remove(Object key) {
// 找到键为key的节点
Entry<K,V> p = getEntry(key);
if (p == null)
return null;
// 保存节点的值
V oldValue = p.value;
// 删除节点
deleteEntry(p);
return oldValue;
}
清空红黑树
public void clear() {
modCount++;
size = 0;
root = null;
}
获取最后一个节点(对外接口)。
public Map.Entry<K,V> lastEntry() {
return exportEntry(getLastEntry());
}
// 获取第一个节点，并将改节点从TreeMap中删除。
public Map.Entry<K,V> pollFirstEntry() {
// 获取第一个节点
Entry<K,V> p = getFirstEntry();
Map.Entry<K,V> result = exportEntry(p);
// 删除第一个节点
if (p != null)
deleteEntry(p);
return result;
}
// 获取最后一个节点，并将改节点从TreeMap中删除。
public Map.Entry<K,V> pollLastEntry() {
// 获取最后一个节点
Entry<K,V> p = getLastEntry();
Map.Entry<K,V> result = exportEntry(p);
// 删除最后一个节点
if (p != null)
deleteEntry(p);
return result;
}
返回小于key的最大的键值对，没有的话返回null
public Map.Entry<K,V> lowerEntry(K key) {
return exportEntry(getLowerEntry(key));
}
返回小于key的最大的键值对所对应的KEY，没有的话返回null
public K lowerKey(K key) {
return keyOrNull(getLowerEntry(key));
}
返回不大于key的最大的键值对所对应的KEY，没有的话返回null
public K floorKey(K key) {
return keyOrNull(getFloorEntry(key));
}
返回大于key的最小的键值对，没有的话返回null
public Map.Entry<K,V> higherEntry(K key) {
return exportEntry(getHigherEntry(key));
}
