当前位置: 首页 > >

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

发布时间:

参考:http://stackoverflow.com/questions/22890967/java-hashmap-tail-traversing

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






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






参考stackoverflow的讨论,尾部遍历是为了避免在新列表插入数据时,遍历队尾的位置。因为,直接插入的效率更高。


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


例如原来顺序是:


?10 ?20 ?30 ?40


插入顺序如下


? 10


? ?20 ?10


? ?30 20 10


? ?40 30 20 10






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


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






存在问题:


但是采用队头插入的方式,导致了HashMap在“多线程环境下”的死循环问题:http://blog.csdn.net/xiaohui127/article/details/11928865?






JDK1.8的优化


通过增加tail指针,既避免了死循环问题(让数据直接插入到队尾),又避免了尾部遍历。代码如下:


?if (oldTab != null) {

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

? ? ? ? ? ? ? ? Node 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)e).split(this, newTab, j, oldCap);

? ? ? ? ? ? ? ? ? ? else { // preserve order

? ? ? ? ?
? ? ? ? ? ? ? Node loHead = null, loTail = null; ? ?// JDK1.8改进了rehash算法,扩容时,容量翻倍,新扩容部分,标识为hi,原来old的部分标识为lo
? ? ? ? ? ? ? ? ? ? ? ? Node hiHead = null, hiTail = null; ? ?// 声明了队尾和队头指针。

? ? ? ? ? ? ? ? ? ? ? ? Node next;

? ? ? ? ? ? ? ? ? ? ? ? do {

? ? ? ? ? ? ? ? ? ? ? ? ? ? next = e.next;

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

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? if (loTail == null)

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? loHead = e;

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? else

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? loTail.next = e;

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? loTail = e;

? ? ? ? ? ? ? ? ? ? ? ? ? ? }

? ? ? ? ? ? ? ? ? ? ? ? ? ? else {

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? if (hiTail == null)

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? hiHead = e;

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? else

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? hiTail.next = e;

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? hiTail = e;

? ? ? ? ? ? ? ? ? ? ? ? ? ? }

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

? ? ? ? ? ? ? ? ? ? ? ? if (loTail != null) {

? ? ? ? ? ? ? ? ? ? ? ? ? ? loTail.next = null;

? ? ? ? ? ? ? ? ? ? ? ? ? ? newTab[j] = loHead;

? ? ? ? ? ? ? ? ? ? ? ? }

? ? ? ? ? ? ? ? ? ? ? ? if (hiTail != null) {

? ? ? ? ? ? ? ? ? ? ? ? ? ? hiTail.next = null;

? ? ? ? ? ? ? ? ? ? ? ? ? ? newTab[j + oldCap] = hiHead;

? ? ? ? ? ? ? ? ? ? ? ? }

? ? ? ? ? ? ? ? ? ? }

? ? ? ? ? ? ? ? }

? ? ? ? ? ? }

? ? ? ? }









友情链接: