快捷導(dǎo)航

基于Java HashMap的死循環(huán)的啟示詳解

更新時(shí)間：2013年05月13日 11:43:23 作者：

本篇文章是對(duì)Java HashMap的死循環(huán)進(jìn)行了詳細(xì)的分析介紹，需要的朋友參考下

一、單線程改造為多線程也是個(gè)技術(shù)活

正如我們看到耗子叔叔博客里寫的那樣，原來是單線程的應(yīng)用程序，”后來，我們的程序性能有問題，所以需要變成多線程的，于是，變成多線程后到了線上，發(fā)現(xiàn)程序經(jīng)常占了100%的CPU“。

考慮到是淘寶的工程師曝出來的問題，他們的技術(shù)基礎(chǔ)一般都很扎實(shí)，連他們都用錯(cuò)了，所以把單線程改造為多線程并不是想象中的那么簡單，我認(rèn)為。

你可能很不服氣地反問，淘寶的工程師又怎么了，單線程改為多線程有什么難的？無非就是應(yīng)用現(xiàn)有的多線程技術(shù)嘛，你看，我有非常強(qiáng)烈的線程安全意識(shí)，我知道同步、死鎖、競態(tài)條件，還知道lock free和線程安全容器，還知道各種線程安全同步構(gòu)造……難道還寫不出線程安全的應(yīng)用程序？

實(shí)際情況是，線程安全的應(yīng)用程序并不一定因?yàn)槟阌性鷮?shí)的線程安全基礎(chǔ)和開發(fā)經(jīng)驗(yàn)就能夠?qū)懞玫摹?/P>

試著舉兩個(gè)例子：

1、使用線程安全容器通過索引取數(shù)據(jù)

很多人知道的線程安全容器，實(shí)際使用的時(shí)候并不一定不出現(xiàn)BUG，下面的（有隱患的）代碼就比較典型：

復(fù)制代碼代碼如下:

        static int GetFirstOrDefault(ThreadSafeList<int> list)
        {
            if (list.Count > 0)
            {
                return list[0];
            }
            return 0;
        }

上面的函數(shù)參數(shù)list如果一開始傳入一個(gè)元素總數(shù)為1的列表，大家能分析出上面的代碼會(huì)有什么問題嗎？

關(guān)于線程安全容器，之前我恰好也總結(jié)過一篇文章<深入線程安全容器的實(shí)現(xiàn)方法>。線程安全容器并不真正安全，上面有問題的代碼就是出自于這里。

2、多線程操作郵件的失誤

還有就是多線程應(yīng)用場景的分析可能不正確，曾經(jīng)因?yàn)橐粋€(gè)郵件收發(fā)程序的性能問題，我也大膽改造過應(yīng)用程序，改來改去就出現(xiàn)了重大BUG，

大家可以看看我痛心疾首總結(jié)過的<基于一個(gè)應(yīng)用程序多線程誤用的分析詳解>。

上面舉的這兩個(gè)例子，我只是想說明，多線程應(yīng)用程序中，因?yàn)榫€程安全產(chǎn)生的BUG其實(shí)是很微妙的，一個(gè)考慮不周或者認(rèn)識(shí)不夠深刻，出現(xiàn)問題的可能性簡直防不勝防。

二、ReHash的代價(jià)

上面第一點(diǎn)主要是閑談線程安全，接著我們也說說哈希表，深刻理解消耗成本很大的ReHash。

我們平常理解中的哈希表是“以空間換時(shí)間的一種數(shù)據(jù)結(jié)構(gòu)”。這樣說的太久了，大家可能會(huì)有一種直觀上的錯(cuò)覺，就是哈希表犧牲的是空間，爭取的是時(shí)間。

但是，ReHash的過程其實(shí)是空間和時(shí)間的雙重重大損失，因?yàn)榉治鲈创a，我們知道ReHash的過程其實(shí)就是一個(gè)動(dòng)態(tài)擴(kuò)容的過程，而哈希表的擴(kuò)容是個(gè)空間和時(shí)間消耗都非常驚人的內(nèi)部操作。

為什么說ReHash是個(gè)空間和時(shí)間消耗都非常驚人的內(nèi)部操作呢？

1、原來當(dāng)我們對(duì)哈希結(jié)構(gòu)的容器進(jìn)行擴(kuò)容時(shí)，散列表內(nèi)部要重新new一個(gè)更大的數(shù)組，然后把原來數(shù)組的內(nèi)容拷貝到新數(shù)組，并進(jìn)行重新散列；

2、new出來的這個(gè)更大的新數(shù)組容量有多大也是一門學(xué)問，一般來說，新數(shù)組的大小會(huì)設(shè)置成原數(shù)組雙倍大小的相近的一個(gè)素?cái)?shù)（.NET中這個(gè)素?cái)?shù)的生成還有一定的技巧）。

從1和2這兩點(diǎn)可以看出，ReHash的代價(jià)確實(shí)非常高。在不久以前我碰巧寫過一篇關(guān)于.NET容器的動(dòng)態(tài)擴(kuò)容的文章<解析從源碼分析常見的基于Array的數(shù)據(jù)結(jié)構(gòu)動(dòng)態(tài)擴(kuò)容機(jī)制的詳解>，其中也淺顯總結(jié)了.NET的HashTable的擴(kuò)容機(jī)制，現(xiàn)在對(duì)照J(rèn)ava中的HashMap源碼，看到熟悉的ReHash函數(shù)命名，再看一遍.NET中的實(shí)現(xiàn)，果然有比較才能有提高。

至于我們平時(shí)所理解的“以空間換時(shí)間“，其實(shí)是指哈希具有O(1)復(fù)雜度的數(shù)據(jù)檢索效率，但它受填充因子影響，空間開銷通常很大，空間利用率不高。

所以我們常常說哈希表適用于讀操作頻繁，寫操作較少應(yīng)用場景，比如把哈希表當(dāng)做緩存容器，于我心有戚戚焉。

最后看到這句“有人把這個(gè)問題報(bào)給了Sun，不過Sun不認(rèn)為這個(gè)是一個(gè)問題。因?yàn)镠ashMap本來就不支持并發(fā)。要并發(fā)就用ConcurrentHashmap…”

根據(jù)實(shí)際開發(fā)經(jīng)驗(yàn)，線程安全的容器并不真正線程安全，會(huì)用ConcurrentHashmap也只是進(jìn)入初級(jí)階段，同時(shí)忍不住要感慨下當(dāng)年如日中天風(fēng)光無限的Sun。

您可能感興趣的文章: