HashMap中的红黑树探究

众所周知，JDK1.8之后HashMap的结构发生了重大变化，不再是静态的数组+链表，而是在数组+链表和数组+红黑树之间有条件变换。

关于红黑树，也算是顶顶大名，常见于各类面试题，作为面试中的大BOSS。但是有一个问题不知道大家有没有想过——红黑树是一种二叉树，其中有一个特点是一个节点左子树上的所有元素都小于该元素，而其右子树上的元素都大于该元素，那么HashMap中的红黑树是怎么比较大小的呢？JDK中的TreeMap就是用的就是红黑树，而TreeMap对key的要求是非常严格的，当key没有实现Comparable接口时，必须在构造方法中传入比较器，否则就会报错（见下面测试代码）。因此TreeMap可以按key的顺序排序。但好像从来没听说过HashMap需要对key有什么特别的要求吧？

    @Test
    public void testTreeMap() {
        Map<C, Object> map = new TreeMap<>();
        map.put(new C(), new Object()); // java.lang.ClassCastException
    }

    class C{

    }

带着这样的疑问，我翻看了一下源码。不难想到，这相关的源码一定是出现在插入元素时，只要顺着put方法找就可以很快找到。可以看到TreeNode的putTreeVal方法会处理树中key的排序问题。它首先会比较hashCode值，如果相同会看是不是实现了Comparable接口。如果不幸既相等又没有实现Comparable，TreeNode的tieBreakOrder方法就是处理这种key无法比较问题（没有实现Comparable接口且hashCode值相等）的。相关的代码如下：

    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;
    }

最终用了System.identityHashCode这样一个native方法最终完成了比较，这个方法的返回值就是Object没被重写的hashCode，通常理解就是内存地址。

看了put自然而然就想看一下get。按常理来讲，向红黑树中插入数据用什么方式比较，取出时，就应该用相同的策略，否则会导致错误。那么HashMap是不是这样做的呢？

从树中找元素的方法是TreeNode的find方法，我就不放源码了。最终效果就是，如果key没法比较，就会对整个树进行遍历。稍加分析就会发现这是一个很怪的处理方式，因为如果没有转成树，链表的插入的查询都是O(n)的复杂度，而这种无法比较的插入复杂度是O(log(n))，而查询已经退化到了O(n)，也就是说还不如链表。

采用这种蹩脚的方式，开发JDK的大神们也确实有其苦衷。首先，不能再调用System.identityHashCode，因为在HashMap中只要hashCode相同，equals相同就要被认为是同一个对象，而System.identityHashCode显然不能满足这样的性质。其次，key不能比较，还得确保能在树中找到它，因此只能遍历了。

其实在HashMap类开头的一大片注释中，已经给我们解释过代码写成这样的原因了，原文如下：

If neither of these apply, we may waste about a factor of two in time and space compared to taking no precautions. But the only known cases stem from poor user programming practices that are already so slow that this makes little difference.

大意就是说，如果key无法比较，则会既浪费空间（TreeNode比普通Node大一倍），又浪费时间，但这是因为垃圾程序员写的烂代码导致的，反正都那么烂了，就那样吧。

综上所述，使用HashMap的话，一定要保证key的hashCode代码足够优秀，同时为了保险起见，最好实现Comparable接口。其实大家最常用的String，本身就是一个很好的key。