【源码分析】hashmap中的红黑树是如何进行排序的 |
您所在的位置：网站首页 › hashmap排序规则 › 【源码分析】hashmap中的红黑树是如何进行排序的 |
|
使用过jdk1.8的童鞋们应该知道，jdk1.8对hashmap又进行了性能上的升级，虽然对于我们这些常年使用map只含有几十个key的业务员来说（斜眼笑），貌似没什么影响，但是，我们还是需要去了解一下的。 首先我们知道，hashmap的底层数据结构是数组+链表。 只有当hash发生碰撞时，才会形成链表，所以对链表部分进行了优化。 假设一个人的名字（String）作为key，他叫Lebron，他有1w个物品。 如果要找到他的女朋友，girlfriend.class，（假设只能有一个女朋友）那么找到她的时间复杂度为O(N)。 jdk1.8对这部分链表进行了优化，采用红黑树的形式,时间复杂度为O(lgn)。不过红黑树的形成是有一定规则的哟~ static final int TREEIFY_THRESHOLD = 8; static final int UNTREEIFY_THRESHOLD = 6;源码中这2个参数代表着，当链表大于8时，才进行红黑树排序。 当操作tree以后，tree的size小于6，重新变为链表结构。 今天我们学习一下是怎么帮我们进行自动排序的，因为树形结构是需要实现Comparable的才能进行排序的。 static Class comparableClassFor(Object x) { if (x instanceof Comparable) { Class c; Type[] ts, as; Type t; ParameterizedType p; if ((c = x.getClass()) == String.class) // bypass checks return c; if ((ts = c.getGenericInterfaces()) != null) { for (int i = 0; i < ts.length; ++i) { if (((t = ts[i]) instanceof ParameterizedType) && ((p = (ParameterizedType)t).getRawType() == Comparable.class) && (as = p.getActualTypeArguments()) != null && as.length == 1 && as[0] == c) // type arg is c return c; } } } return null; }comparableClassFor方法是用来寻找此类是否有实现Comparable接口（它先判断了String，String类也实现了Comparable）。 static int compareComparables(Class kc, Object k, Object x) { return (x == null || x.getClass() != kc ? 0 : ((Comparable)k).compareTo(x)); } compareComparables方法是在使用过comparableClassFor后才使用的，因为第一步已经获取到了比较器，那么就可以快乐的将链表里的object逐个去比较啦。 那么问题来了，这个class不是String类，也没有实现Comparable接口怎么办呢。 终极解决方案！ 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) |
今日新闻 |
推荐新闻 |
| CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |