Java TreeMap 源码解析
TreeMap是用红黑树作为基础实现的，红黑树是一种二叉搜索树
红黑树示例
上图是从wiki截来的，需要说明的一点是：
Red-Black trees are more general purpose. The do relatively well on add, remove, and look-up but AVL trees have faster look-ups at the cost of slower add/remove. Java's general policy is to provide the best general purpose data structures.
Java uses quicksort for primitive objects as it is faster than merge sort in the average case . It uses merge sort for sorting objects as merge sort is a stable sorting algorithm.
http://daoluan.net/blog/category/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/
https://github.com/aorzecho/ds/blob/master/src/main/java/org/aorzecho/ds/java/util/TreeMap.java
final Entry<K,V> getIthEntry(Entry<K,V> entry, int i) {
if (i > size || i<=0)
throw new IndexOutOfBoundsException("Size is " + size
+ ", requested i=" + i + " out of bounds");
int r = 1;
if (entry.left != null)
r += entry.left.size;
if (i == r)
return entry;
else if (i < r)
return getIthEntry(entry.left, i);
else
return getIthEntry(entry.right, i-r);
}
static final class Entry<K,V> implements Map.Entry<K,V> {
K key;
V value;
Entry<K,V> left = null;
Entry<K,V> right = null;
Entry<K,V> parent;
boolean color = BLACK;
int size = 1;
}
https://kerflyn.wordpress.com/2011/05/20/how-treemap-can-save-your-day/
- Comparable一般表示类的自然序，比如定义一个Student类，学号为默认排序
- Comparator一般表示类在某种场合下的特殊分类，需要定制化排序。比如现在想按照Student类的age来排序
插入SortedMap中的key的类类都必须继承Comparable类（或指定一个comparator），这样才能确定如何比较（通过
k1.compareTo(k2)或comparator.compare(k1, k2)）两个key，否则，在插入时，会报ClassCastException的异常。
此为，SortedMap中key的顺序性应该与
equals方法保持一致。也就是说k1.compareTo(k2)或comparator.compare(k1, k2)为true时，k1.equals(k2)也应该为true。
NavigableMap是JDK1.6新增的，在SortedMap的基础上，增加了一些“导航方法”（navigation methods）来返回与搜索目标最近的元素。例如下面这些方法：
- lowerEntry，返回所有比给定Map.Entry小的元素
- floorEntry，返回所有比给定Map.Entry小或相等的元素
- ceilingEntry，返回所有比给定Map.Entry大或相等的元素
- higherEntry，返回所有比给定Map.Entry大的元素
TreeMap是用红黑树作为基础实现的，红黑树是一种二叉搜索树
三叉搜索树在将问题规模减少三分之二时，所需比较操作的次数是两次（二叉搜索树再将问题规模减少一半时，只需要一次比较操作）
我们不能把这两次给忽略了，对于更一般的情况：
n个元素，K叉树搜索树需要的平均比较次数为k*log(n/k)。
对于极端情况k＝n时，K叉树就转化为了线性表了，复杂度也就是
O(n)了，如果用数学角度来解这个问题，相当于：n为固定值时，k取何值时，k*log(n/k)的取值最小？
k*log(n/k)根据对数的运算规则可以转化为ln(n)*k/ln(k)，ln(n)为常数，所以相当于取k/ln(k)的极小值。这个问题对于大一刚学高数的人来说再简单不过了，我们这里直接看结果😊当k＝e时，k/ln(k)取最小值。
自然数e的取值大约为2.718左右，可以看到二叉树基本上就是这样最优解了
红黑树示例上图是从wiki截来的，需要说明的一点是：
叶子节点为上图中的NIL节点，国内一些教材中没有这个NIL节点，我们在画图时有时也会省略这些NIL节点，但是我们需要明确，当我们说叶子节点时，指的就是这些NIL节点。
红黑树通过下面5条规则，保证了树是平衡的：
- 树的节点只有红与黑两种颜色
- 根节点为黑色的
- 叶子节点为黑色的
- 红色节点的字节点必定是黑色的
- 从任意一节点出发，到其后继的叶子节点的路径中，黑色节点的数目相同
满足了上面5个条件后，就能够保证：
其实这个很好理解，主要是用了性质4与5，这里简单说下：
根节点到叶子节点的最长路径不会大于根节点到叶子最短路径的2倍。其实这个很好理解，主要是用了性质4与5，这里简单说下：
Serialization假设根节点到叶子节点最短的路径中，黑色节点数目为B，那么根据性质5，根节点到叶子节点的最长路径中，黑色节点数目也是B，最长的情况就是每两个黑色节点中间有个红色节点（也就是红黑相间的情况），所以红色节点最多为B－1个。这样就能证明上面的结论了。
private void writeObject(java.io.ObjectOutputStream s)
throws java.io.IOException {
// Write out the Comparator and any hidden stuff
s.defaultWriteObject();
// Write out size (number of Mappings)
s.writeInt(size);
// Write out keys and values (alternating)
for (Iterator<Map.Entry<K,V>> i = entrySet().iterator(); i.hasNext(); ) {
Map.Entry<K,V> e = i.next();
s.writeObject(e.getKey());
s.writeObject(e.getValue());
}
}
/**
* Reconstitute the {@code TreeMap} instance from a stream (i.e.,
* deserialize it).
*/
private void readObject(final java.io.ObjectInputStream s)
throws java.io.IOException, ClassNotFoundException {
// Read in the Comparator and any hidden stuff
s.defaultReadObject();
// Read in size
int size = s.readInt();
buildFromSorted(size, null, s, null);
}
http://stackoverflow.com/questions/14923407/why-red-black-tree-based-implementation-for-java-treemapRed-Black trees are more general purpose. The do relatively well on add, remove, and look-up but AVL trees have faster look-ups at the cost of slower add/remove. Java's general policy is to provide the best general purpose data structures.
Java uses quicksort for primitive objects as it is faster than merge sort in the average case . It uses merge sort for sorting objects as merge sort is a stable sorting algorithm.
http://daoluan.net/blog/category/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/
https://github.com/aorzecho/ds/blob/master/src/main/java/org/aorzecho/ds/java/util/TreeMap.java
final Entry<K,V> getIthEntry(Entry<K,V> entry, int i) {
if (i > size || i<=0)
throw new IndexOutOfBoundsException("Size is " + size
+ ", requested i=" + i + " out of bounds");
int r = 1;
if (entry.left != null)
r += entry.left.size;
if (i == r)
return entry;
else if (i < r)
return getIthEntry(entry.left, i);
else
return getIthEntry(entry.right, i-r);
}
static final class Entry<K,V> implements Map.Entry<K,V> {
K key;
V value;
Entry<K,V> left = null;
Entry<K,V> right = null;
Entry<K,V> parent;
boolean color = BLACK;
int size = 1;
}
https://kerflyn.wordpress.com/2011/05/20/how-treemap-can-save-your-day/
How to find a reservation from a given date
I group a set of reservations in a class that I’ve called Planning. Once instantiated, you can add reservations (method add()) and you can get a reservation at a given date (method getReservationAt()).
There are two steps to get a reservation close to a date.
- I first use the method floorEntry(). It gets you the map entry which key is the greatest one less than the given date.
- Second, I check if the reservation (that is the value of the entry) contains the given date.
public class Planning { public final TreeMap<Date, Reservation> reservations; public Planning() { reservations = new TreeMap<Date, Reservation>(); } public void add(Reservation reservation) { reservations.put(reservation.from, reservation); } public Reservation getReservationAt(Date date) { Entry<Date, Reservation> entry = reservations.floorEntry(date); if (entry == null) { return null; } Reservation reservation = entry.getValue(); if (!reservation.contains(date)) { return null; } return reservation; }}