HashMap-红黑树

1. 为什么引入红黑树
   桶的链表查找是O(n)，引入红黑树是O(lgn)
2. 红黑树的key比较
   2.1 如果key实现了compareable，则使用compareable
   2.2 如果为实现compareable，比较逻辑如下：
   如果有一个为null，通过System.identityHashCode比较；通过class.getName比较。

        /* Tie-breaking utility for ordering insertions when equal
        * hashCodes and non-comparable. We don't require a total
        * order, just a consistent insertion rule to maintain
        * equivalence across rebalancings. Tie-breaking further than
        * necessary simplifies testing a bit.
        */
       static int tieBreakOrder(Object a, Object b) {
           int d;
           if (a == null || b == null ||
               (d = a.getClass().getName().
                compareTo(b.getClass().getName())) == 0)
               d = (System.identityHashCode(a) <= System.identityHashCode(b) ?
                    -1 : 1);
           return d;
       }

3. 为什么链表达到8转为红黑树