首页 > 其他 > 详细

JDK1.7中HashMap的闭环链表问题

时间:2020-04-14 19:51:06      阅读:130      评论:0      收藏:0      [点我收藏+]

问题描述:

  Jdk1.7中,HashMap的扩容机制采用“头插法”,即元素hash到新数组槽到时候,采用在链表头部插入的方式。其原因是:在尾部追加元素,时间复杂度是O(n),头部插入能提升性能。

  虽然我们知道HashMap不是线程安全的,但是这种写法,在并发进行扩容(resize)时,会引起闭环链表问题。

原因分析:

  

 void resize(int newCapacity) {
        Entry[] oldTable = table;
        int oldCapacity = oldTable.length;
        if (oldCapacity == MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return;
        }

        Entry[] newTable = new Entry[newCapacity];
        transfer(newTable, initHashSeedAsNeeded(newCapacity));
        table = newTable;
        threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
    }

    /**
     * Transfers all entries from current table to newTable.
     */
    void transfer(Entry[] newTable, boolean rehash) {
        int newCapacity = newTable.length;
        for (Entry<K,V> e : table) {
            while(null != e) {
                Entry<K,V> next = e.next;//这行代码是导致问题的关键代码。
                if (rehash) {
                    e.hash = null == e.key ? 0 : hash(e.key);
                }
                int i = indexFor(e.hash, newCapacity);
                e.next = newTable[i];
                newTable[i] = e;
                e = next;
            }
        }
    }

 

JDK1.7中HashMap的闭环链表问题

原文:https://www.cnblogs.com/akid1994/p/12700068.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!