1.官方文檔的說(shuō)明
參考先前ConcurrentHashMap類(lèi)實(shí)現(xiàn)說(shuō)明翻譯：
TreeBins use a special form of comparison for search and
related operations (which is the main reason we cannot use
existing collections such as TreeMaps). TreeBins contain
Comparable elements, but may contain others, as well as
elements that are Comparable but not necessarily Comparable for
the same T, so we cannot invoke compareTo among them. To handle
this, the tree is ordered primarily by hash value, then by
Comparable.compareTo order if applicable. On lookup at a node,
if elements are not comparable or compare as 0 then both left
and right children may need to be searched in the case of tied
hash values. (This corresponds to the full list search that
would be necessary if all elements were non-Comparable and had
tied hashes.) On insertion, to keep a total ordering (or as
close as is required here) across rebalancings, we compare
classes and identityHashCodes as tie-breakers. The red-black
balancing code is updated from pre-jdk-collections
(http://gee.cs.oswego.edu/dl/classes/collections/RBCell.java)
based in turn on Cormen, Leiserson, and Rivest "Introduction to
Algorithms" (CLR).
Treebins在搜索和相關(guān)操作中使用了特殊形式的比較（這也是不能使用現(xiàn)存集合例如TreeMap的主要原因）脖母。Treebins包含Comparable元素疆导，但是也可能包含其他類(lèi)型的（不能調(diào)用compareTo的元素）蟆沫。
2.看看TreeMap對(duì)元素的要求
The map is sorted according to the Comparable natural
ordering of its keys, or by a Comparator provided at map
creation time, depending on which constructor is used.
- 要么元素是Comparable類(lèi)型的
- 要么提供一個(gè)比價(jià)器Comparator
其部分put代碼如下：
public V put(K key, V value) {
Comparator<? super K> cpr = comparator;
if (cpr != null) {
do {
parent = t;
cmp = cpr.compare(key, t.key);
...
}
else {
if (key == null)
throw new NullPointerException();
@SuppressWarnings("unchecked")
Comparable<? super K> k = (Comparable<? super K>) key;
do {
parent = t;
cmp = k.compareTo(t.key);
可見(jiàn)在插入元素時(shí)歉秫，要么調(diào)用比較器comparator的compara蛾洛，要么調(diào)用compareTo方法確定元素要插入紅黑樹(shù)的位置。
所以這里有一個(gè)核心區(qū)別：對(duì)于TreeMap雁芙，是一個(gè)SortedMap轧膘，本質(zhì)上是針對(duì)有序、可排序元素使用的兔甘。而ConcurrentHashMap是一個(gè)HashMap谎碍，本質(zhì)上并不要求元素有序，而是為了存儲(chǔ)鍵值對(duì)而已洞焙，只不過(guò)為了更快的存取蟆淀。因此，必然不要求其有序澡匪。另外存儲(chǔ)的元素是Comparable時(shí)熔任，但可能不是同一種類(lèi)型的。例如Integer和Double唁情。
public class CHMTest {
public static void main(String[] args) {
// Map<Number, String> map = new ConcurrentHashMap<>();
Map<Number, String> map = new TreeMap<>();
map.put(12, "12");
map.put(13.0, "13");
System.out.println(map);
}
}
使用TreeMap時(shí)結(jié)果會(huì)拋出異常：
Exception in thread "main" java.lang.ClassCastException: java.lang.Integer cannot be cast to java.lang.Double
at java.lang.Double.compareTo(Double.java:49)
at java.util.TreeMap.put(TreeMap.java:568)
at com.enjoy.learn.core.concurrency.CHMTest.main(CHMTest.java:21)
因?yàn)檎{(diào)用Double.compareTo時(shí)疑苔，會(huì)對(duì)入?yún)nteger進(jìn)行轉(zhuǎn)型，但是Double和Integer不屬于父子類(lèi)關(guān)系荠瘪。
但是顯然ConcurrentHashMap是可以的：
public static void main(String[] args) {
Map<Number, String> map = new ConcurrentHashMap<>();
// Map<Number, String> map = new TreeMap<>();
map.put(12, "12");
map.put(13.0, "13");
System.out.println(map);
}
結(jié)果：
{13.0=13, 12=12}
所以其紅黑樹(shù)為了兼容這種表現(xiàn)，必須進(jìn)行改進(jìn)赛惩，使得能夠放入任意鍵值對(duì)哀墓。
