正是由于这些规则和要求的限制，红黑树保证了较高的查找效率，所以现在就可以理解为什么 Java 8 的 ConcurrentHashMap 要引入红黑树了。好处就是避免在极端的情况下冲突链表变得很长，在查询的时候，效率会非常慢。而红黑树具有自平衡的特点，所以，即便是极端情况下，也可以保证查询效率在 O(log(n))。
事实上，链表长度超过 8 就转为红黑树的设计，更多的是为了防止用户自己实现了不好的哈希算法时导致链表过长，从而导致查询效率低，而此时转为红黑树更多的是一种保底策略，用来保证极端情况下查询的效率。
通常如果 hash 算法正常的话，那么链表的长度也不会很长，那么红黑树也不会带来明显的查询时间上的优势，反而会增加空间负担。所以通常情况下，并没有必要转为红黑树，所以就选择了概率非常小，小于千万分之一概率，也就是长度为 8 的概率，把长度 8 作为转化的默认阈值。
所以如果平时开发中发现 HashMap 或是 ConcurrentHashMap 内部出现了红黑树的结构，这个时候往往就说明我们的哈希算法出了问题，需要留意是不是我们实现了效果不好的 hashCode 方法，并对此进行改进，以便减少冲突。
源码分析
putVal方法，关键词：CAS、helpTransfer、synchronized、addCount
1 final V putVal(K key, V value, boolean onlyIfAbsent) { 2 if (key == null || value == null) { 3 throw new NullPointerException(); 4 } 5 //计算 hash 值 6 int hash = spread(key.hashCode()); 7 int binCount = 0; 8 for (Node<K, V>[] tab = table; ; ) { 9 Node<K, V> f; 10 int n, i, fh; 11 //如果数组是空的，就进行初始化 12 if (tab == null || (n = tab.length) == 0) { 13 tab = initTable(); 14 } 15 // 找该 hash 值对应的数组下标 16 else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) { 17 //如果该位置是空的，就用 CAS 的方式放入新值 18 if (casTabAt(tab, i, null, 19 new Node<K, V>(hash, key, value, null))) { 20 break; 21 } 22 } 23 //hash值等于 MOVED 代表在扩容 24 else if ((fh = f.hash) == MOVED) { 25 tab = helpTransfer(tab, f); 26 } 27 //槽点上是有值的情况 28 else { 29 V oldVal = null; 30 //用 synchronized 锁住当前槽点，保证并发安全 31 synchronized (f) { 32 if (tabAt(tab, i) == f) { 33 //如果是链表的形式 34 if (fh >= 0) { 35 binCount = 1; 36 //遍历链表 37 for (Node<K, V> e = f; ; ++binCount) { 38 K ek; 39 //如果发现该 key 已存在，就判断是否需要进行覆盖，然后返回 40 if (e.hash == hash && 41 ((ek = e.key) == key || 42 (ek != null && key.equals(ek)))) { 43 oldVal = e.val; 44 if (!onlyIfAbsent) { 45 e.val = value; 46 } 47 break; 48 } 49 Node<K, V> pred = e; 50 //到了链表的尾部也没有发现该 key，说明之前不存在，就把新值添加到链表的最后 51 if ((e = e.next) == null) { 52 pred.next = new Node<K, V>(hash, key, 53 value, null); 54 break; 55 } 56 } 57 } 58 //如果是红黑树的形式 59 else if (f instanceof TreeBin) { 60 Node<K, V> p; 61 binCount = 2; 62 //调用 putTreeVal 方法往红黑树里增加数据 63 if ((p = ((TreeBin<K, V>) f).putTreeVal(hash, key, 64 value)) != null) { 65 oldVal = p.val; 66 if (!onlyIfAbsent) { 67 p.val = value; 68 } 69 } 70 } 71 } 72 } 73 if (binCount != 0) { 74 //检查是否满足条件并把链表转换为红黑树的形式，默认的 TREEIFY_THRESHOLD 阈值是 8 75 if (binCount >= TREEIFY_THRESHOLD) { 76 treeifyBin(tab, i); 77 } 78 //putVal 的返回是添加前的旧值，所以返回 oldVal 79 if (oldVal != null) { 80 return oldVal; 81 } 82 break; 83 } 84 } 85 } 86 addCount(1L, binCount); 87 return null; 88 }