何时以及如何将HashMap从链表转换为红黑树？

我正在浏览java 8的功能,发现当桶上的条目集数量增加时,哈希映射使用红黑树而不是链表.

但是,这不需要密钥是可比较的还是存在密钥的某些顺序,这是如何工作的？这种转换何时实际发生？如何？

当一个存储桶中至少有 8个条目(TREEIFY_THRESHOLD)且存储桶总数超过64(MIN_TREEIFY_CAPACITY)时,该单个存储桶将转换为完美平衡的红黑树节点.

当您删除条目(UNTREEIFY_THRESHOLD== 6)时,您应该注意(如果需要)收缩.

密钥应该是正确的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;
 }

因此,类名作为String用于比较,如果还不行,那么System.identityHashCode使用(马尔萨利亚XOR-Shift算法)来决定的左侧和右侧.

当发生这种情况时回答你的问题 - 调用resize时.当你必须调整你的大小时HashMap- 有些事情正在发生; 比如桶的数量增加了两倍(在一个条目将移动或不移动的情况下再考虑一个比特)或某个桶被转换为树.这个过程(再次,如果你真的关心)是相当缓慢的,有些人说Java HashMap是"sloooooooow,然后是快速快速;然后它是sloooooo,然后它快速快速"(我仍然认为这是嘲弄,但那里是PauselessHashMap实施).

这带来了两个有趣的观点.首先是选择你Map最初的正确尺寸(即使粗略的估计会做),即:

 new HashMap<>(256); // choosing the size

这将避免一些调整大小.

第二个是为什么转换为a Tree很重要(想想数据库索引及其原因BTREE......).在完美的树中找到具有INTEGER.MAX_VALUE条目的条目(理论上)需要多少步骤.最多32个.