办理斗嘴

在上文中我们已经多次提到碰撞斗嘴，昆山软件开发，可是散列函数不行能是完美的，key漫衍完全匀称的环境是不存在的，所以碰撞斗嘴老是难以制止。

那么产生碰撞斗嘴时怎么办？总不能扬弃数据吧？必需要有一种公道的要领来办理这个问题，HashMap利用了叫做疏散链接（Separate chaining，也有人翻译成拉链法）的计策来办理斗嘴。它的主要思想是每个bucket都该当是一个相互独立的数据布局，当产生斗嘴时，只需要把数据放入bucket中（因为bucket自己也是一个可以存放数据的数据布局），这样查询一个key所耗损的时间为会见bucket所耗损的时间加上在bucket中查找的时间。

HashMap的buckets数组其实就是一个链表数组，在产生斗嘴时只需要把Entry（还记得Entry吗？HashMap的Entry实现就是一个简朴的链表节点，它包括了key和value以及hash code）放到链表的尾部，假如未产生斗嘴（位于该下标的bucket为null），那么就把该Entry做为链表的头部。并且HashMap还利用了Lazy计策，buckets数组只会在第一次挪用put()函数时举办初始化，这是一种防备内存挥霍的做法，像ArrayList也是Lazy的，它在第一次挪用add()时才会初始化内部的数组。

不外链表固然实现简朴，可是在查找的效率上只有O(n)，并且我们大部门的操纵都是在举办查找，在hashCode()设计的不长短常精采的环境下，碰撞斗嘴大概会频繁产生，链表也会变得越来越长，这个效率长短常差的。Java 8对其实现了优化，链表的节点数量在达到阈值时会转化为红黑树，这样查找所需的时间就只有O(log n)了，阈值的界说如下：

/**
 * The bin count threshold for using a tree rather than list for a
 * bin.  Bins are converted to trees when adding an element to a
 * bin with at least this many nodes. The value must be greater
 * than 2 and should be at least 8 to mesh with assumptions in
 * tree removal about conversion back to plain bins upon
 * shrinkage.
 */
static final int TREEIFY_THRESHOLD = 8;

假如在插入Entry时发明一条链表高出阈值，就会执行以下的操纵，对该链表举办树化；相对的，假如在删除Entry（或举办扩容）时发明红黑树的节点太少（按照阈值UNTREEIFY_THRESHOLD），也会把红黑树退化成链表。

/**
 * 替换指定hash所处位置的链表中的所有节点为TreeNode，
 * 假如buckets数组太小，就举办扩容。
 */
final void treeifyBin(Node<K,V>[] tab, int hash) {
    int n, index; Node<K,V> e;
    // MIN_TREEIFY_CAPACITY = 64，小于该值代表数组中的节点并不是许多
    // 所以选择举办扩容，只有数组长度大于该值时才会举办树化。
    if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
        resize();
    else if ((e = tab[index = (n - 1) & hash]) != null) {
        TreeNode<K,V> hd = null, tl = null;
        // 转换链表节点为树节点，留意要处理惩罚好毗连干系
        do {
            TreeNode<K,V> p = replacementTreeNode(e, null);
            if (tl == null)
                hd = p;
            else {
                p.prev = tl;
                tl.next = p;
            }
            tl = p;
        } while ((e = e.next) != null);
        if ((tab[index] = hd) != null)
            hd.treeify(tab); // 从新部开始结构树
    }
}
    // 该函数界说在TreeNode中
    final void treeify(Node<K,V>[] tab) {
        TreeNode<K,V> root = null;
        for (TreeNode<K,V> x = this, next; x != null; x = next) {
            next = (TreeNode<K,V>)x.next;
            x.left = x.right = null;
            if (root == null) { // 初始化root节点
                x.parent = null;
                x.red = false;
                root = x;
            }
            else {
                K k = x.key;
                int h = x.hash;
                Class<?> kc = null;
                for (TreeNode<K,V> p = root;;) {
                    int dir, ph;
                    K pk = p.key;
                    // 确定节点的偏向
                    if ((ph = p.hash) > h)
                        dir = -1;
                    else if (ph < h)
                        dir = 1;
                    // 假如kc == null
                    // 而且k没有实现Comparable接口
                    // 可能k与pk是没有可较量性的（范例差异）
                    // 可能k与pk是相等的（返回0也有大概是相等）
                    else if ((kc == null &&
                              (kc = comparableClassFor(k)) == null) ||
                             (dir = compareComparables(kc, k, pk)) == 0)
                        dir = tieBreakOrder(k, pk);
                    // 确定偏向后插入节点，批改红黑树的均衡
                    TreeNode<K,V> xp = p;
                    if ((p = (dir <= 0) ? p.left : p.right) == null) {
                        x.parent = xp;
                        if (dir <= 0)
                            xp.left = x;
                        else
                            xp.right = x;
                        root = balanceInsertion(root, x);
                        break;
                    }
                }
            }
        }
        // 确保给定的root是该bucket中的第一个节点
        moveRootToFront(tab, root);
    }
    static int tieBreakOrder(Object a, Object b) {
        int d;
        if (a == null || b == null ||
            (d = a.getClass().getName().
             compareTo(b.getClass().getName())) == 0)
            // System.identityHashCode()将挪用并返回传入工具的默认hashCode()
            // 也就是说，无论是否重写了hashCode()，都将挪用Object.hashCode()。
            // 假如传入的工具是null，那么就返回0
            d = (System.identityHashCode(a) <= System.identityHashCode(b) ?
                 -1 : 1);
        return d;
    }