HashMap的尾部遍历问题--Tail Traversing

在看网上HashMap的resize()设计时，提到尾部遍历。

JDK1.7的HashMap在实现resize()时，新table[]的列表采用LIFO方式，即队头插入。这样做的目的是：避免尾部遍历。

避免尾部遍历是为了避免在新列表插入数据时，遍历到队尾的位置。因为，直接插入的效率更高。

对resize()的设计来说，本来就是要创建一个新的table，列表的顺序不是很重要。

但如果要确保插入队尾，还得遍历出链表的队尾位置，然后插入，是一种多余的损耗。

直接采用队头插入，会使得链表数据倒序

例如原来顺序是：

10 20 30 40

插入顺序如下

20 10

30 20 10

40 30 20 10

存在问题：

采用队头插入的方式，导致了HashMap在“多线程环境下”的死循环问题：http://www.cnblogs.com/chengdabelief/p/7419776.html

JDK1.8的优化

JDK1.7中rehash的时候，旧链表迁移新链表的时候，如果在新表的数组索引位置相同，则链表元素会倒置，JDK1.8不会倒置，通过增加tail指针，既避免了死循环问题（让数据直接插入到队尾），又避免了尾部遍历。代码如下：

final Node<K,V>[] resize() {

    Node<K,V>[] oldTab = table;

    int oldCap = (oldTab == null) ? 0 : oldTab.length;

    int oldThr = threshold;

    int newCap, newThr = 0;

    if (oldCap > 0) {

        // 超过最大值就不再扩充了，就只好随你碰撞去吧

        if (oldCap >= MAXIMUM_CAPACITY) {

            threshold = Integer.MAX_VALUE;

            return oldTab;

        }

        // 没超过最大值，就扩充为原来的2倍

        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&

                 oldCap >= DEFAULT_INITIAL_CAPACITY)

            newThr = oldThr << 1; // double threshold

    }

    else if (oldThr > 0) // initial capacity was placed in threshold

        newCap = oldThr;

    else {               // zero initial threshold signifies using defaults

        newCap = DEFAULT_INITIAL_CAPACITY;

        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);

    }

    // 计算新的resize上限

    if (newThr == 0) {

        float ft = (float)newCap * loadFactor;

        newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?

                  (int)ft : Integer.MAX_VALUE);

    }

    threshold = newThr;

    @SuppressWarnings({"rawtypes","unchecked"})

        Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];

    table = newTab;

    if (oldTab != null) {

        // 把每个bucket都移动到新的buckets中

        for (int j = 0; j < oldCap; ++j) {

            Node<K,V> e;

            if ((e = oldTab[j]) != null) {

                oldTab[j] = null;

                if (e.next == null)

                    newTab[e.hash & (newCap - 1)] = e;

                else if (e instanceof TreeNode)

                    ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);

                else { // preserve order

                    Node<K,V> loHead = null, loTail = null;

                    Node<K,V> hiHead = null, hiTail = null;

                    Node<K,V> next;

                    do {

                        next = e.next;

                        // 原索引

                        if ((e.hash & oldCap) == 0) {

                            if (loTail == null)

                                loHead = e;

                            else

                                loTail.next = e;

                            loTail = e;

                        }

                        // 原索引+oldCap

                        else {

                            if (hiTail == null)

                                hiHead = e;

                            else

                                hiTail.next = e;

                            hiTail = e;

                        }

                    } while ((e = next) != null);

                    // 原索引放到bucket里

                    if (loTail != null) {

                        loTail.next = null;

                        newTab[j] = loHead;

                    }

                    // 原索引+oldCap放到bucket里

                    if (hiTail != null) {

                        hiTail.next = null;

                        newTab[j + oldCap] = hiHead;

                    }

                }

            }

        }

    }

    return newTab;

}

巴特西

HashMap的尾部遍历问题--Tail Traversing

最新文章

热门文章