了解HashMap原理對于日后的緩存機制多少有些認(rèn)識。在網(wǎng)絡(luò)中也有很多方面的帖子，但是很多都是輕描淡寫，很少有把握的比較準(zhǔn)確的信息，在這里試著不妨說解一二。

    對于HashMap主要以鍵值(key-value)的方式來體現(xiàn)，籠統(tǒng)的說就是采用key值的哈希算法來，外加取余最終獲取索引，而這個索引可以認(rèn)定是一種地址，既而把相應(yīng)的value存儲在地址指向內(nèi)容中。這樣說或許比較概念化，也可能復(fù)述不夠清楚，來看列式更加清晰：

其實最終就是這兩個式子決定了值得存儲位置。但是以上兩個表達(dá)式還有欠缺。為什么這么說？例如在key.hashCode()后可能存在是一個負(fù)整數(shù)，你會問：是啊，那這個時候怎么辦呢？所以在這里就需要進(jìn)一步加強改造式子2了，修改后的：

到這里又迷惑了，為什么上面是這樣的呢？對于先前我們談到在hash有可能產(chǎn)生負(fù)數(shù)的情況，這里我們使用當(dāng)前的hash做一個“與”操作，在這里需要和int最大的值相“與”。這樣的話就可以保證數(shù)據(jù)的統(tǒng)一性，把有符號的數(shù)值給“與”掉。而一般這里我們把二進(jìn)制的數(shù)值轉(zhuǎn)換成16進(jìn)制的就變成了：Ox7FFFFFFF。（注：與操作的方式為，不同為0，相同為1）。而對于hashCode()的方法一般有：

說道這里大家可能會說，到這里算完事了吧。但是你可曾想到如果數(shù)據(jù)都采用上面的方式，最終得到的可能index會相同怎么辦呢？如果你想到的話，那恭喜你!又增進(jìn)一步了，這里就是要說到一個名詞：沖突率。是的就是前面說道的一旦index有相同怎么辦？數(shù)據(jù)又該如何存放呢，而且這個在數(shù)據(jù)量非常龐大的時候這個基率更大。這里按照算法需要明確的一點：每個鍵（key）被散列分布到任何一個數(shù)組索引的可能性相同，而且不取決于其它鍵分布的位置。這句話怎么理解呢？從概率論的角度，也就是說如果key的個數(shù)達(dá)到一個極限，每個key分布的機率都是均等的。更進(jìn)一步就是：即便key1不等于key2也還是可能key1.hashCode()=key2.hashCode()。

對于早期的解決沖突的方法有折疊法（folding)，例如我們在做系統(tǒng)的時候有時候會采用部門編號附加到某個單據(jù)標(biāo)號后，這里比如產(chǎn)生一個9～11位的編碼。通過對半折疊做。

現(xiàn)在的策略有：

1.       鍵式散列 

2.       開放地址法

在了解這兩個策略前，我們先定義清楚幾個名詞解釋：

清晰了這幾個定義，我們再來看具體的解決方式

鍵式散列：

我們直接看一個實例，這樣就更加清晰它的工作方式，從而避免文字定義。我們這里還是來舉一個圖書編號的例子，下面比如有這樣一些編號：

                         78938-0000

                         45678-0001

                         72678-0002

                         24678-0001

                         16678-0001

                         98678-0003

                         85678-0002

                         45232-0004

步驟：

1.       把編號作為key,即：int hash=key.hashCode();

2.       int index=hash%表大小；

3.       逐步按順序插入對象中

現(xiàn)在問題出現(xiàn)了：對于編號通過散列算法后很可能產(chǎn)生相同的索引值，意味著存在沖突。

解釋上面的操作：如果對于key.hashCode()產(chǎn)生了沖突（比如途中對于插入24678-0001對于通過哈希算法后可能產(chǎn)生的index或許也是501），既而把相應(yīng)的前驅(qū)有相同的index的對象指向當(dāng)前引用。這也就是大家認(rèn)定的單鏈表方式。以此類推…

而這里存在沖突對象的元素放在Entry對象中，Entry具有以下一些屬性：

int hash;

Object key;

Entry next;

對于Entry對象就可以直接追溯到鏈表數(shù)據(jù)結(jié)構(gòu)體中查閱。

開放地址法：

1.         線性地址探測法：

如何理解這個概念呢，一句話：就是通過算法規(guī)則在對象地址N+1中查閱找到為NULL的索引內(nèi)容。

處理方式：如果index索引與當(dāng)前的index有沖突，即把當(dāng)前的索引index+1。如果在index+1已經(jīng)存在占位現(xiàn)象（index+1的內(nèi)容不為NULL）試圖接著index+2執(zhí)行。。。直到找到索引為內(nèi)容為NULL的為止。這種處理方式也叫：線性地址探測法(offset-of-1)

如果采用線性地址探測法會帶來一個效率的不良影響?，F(xiàn)在我們來分析這種方式會帶來哪些不良因素。大家試想下如果一個非常龐大的數(shù)據(jù)存儲在Map中，假如在某些記錄集中有一些數(shù)據(jù)非常相似（他們產(chǎn)生的索引在內(nèi)存的某個塊中非常的密集），也就是說他們產(chǎn)生的索引地址是一個連續(xù)數(shù)值，而造成數(shù)據(jù)成塊現(xiàn)象。另一個致命的問題就是在數(shù)據(jù)刪除后，如果再次查詢可能無法定到下一個連續(xù)數(shù)字，這個又是一個什么概念呢？例如以下圖片就很好的說明開發(fā)地址散列如何把數(shù)據(jù)按照算法插入到對象中：

對于上圖的注釋步驟說明：

從數(shù)據(jù)“78938-0000”開始通過哈希算法按順序依次插入到對象中，例如78938-0000通過換

算得到索引為0，當(dāng)前所指內(nèi)容為NULL所以直接插入；45678-0001同樣通過換算得到索引為地址501所指內(nèi)容，當(dāng)前內(nèi)容為NULL所以也可以插入；72678-0002得到索引502所指內(nèi)容，當(dāng)前內(nèi)容為NULL也可以插入；請注意當(dāng)24678-0001得到索引也為501，當(dāng)前地址所指內(nèi)容為45678-0001。即表示當(dāng)前數(shù)據(jù)存在沖突，則直接對地址501+1=502所指向內(nèi)容為72678-0002不為NULL也不允許插入，再次對索引502+1=503所指內(nèi)容為NULL允許插入。。。依次類推只要對于索引存在沖突現(xiàn)象，則逐次下移位知道索引地址所指為NULL；如果索引不沖突則還是按照算法放入內(nèi)容。對于這樣的對象是一種插入方式，接下來就是我們的刪除(remove)方法了。按照常理對于刪除，方式基本區(qū)別不大。但是現(xiàn)在問題又出現(xiàn)了，如果刪除的某個數(shù)據(jù)是一個存在沖突索引的內(nèi)容，帶來后續(xù)的問題又會接踵而來。那是什么問題呢？我們還是同樣來看看圖示的描述，對于圖-2中如果刪除(remove)數(shù)據(jù)24678-0001的方法如下圖所示：

對于我們會想當(dāng)然的覺得只要把指向數(shù)據(jù)置為NULL就可以,這樣的做法對于刪除來說當(dāng)然是沒有問題的。如果再次定位檢索數(shù)據(jù)16678-0001不會成功，因為這個時候以前的鏈路已經(jīng)堵上了，但是需要檢索的數(shù)據(jù)事實上又存在。那我們?nèi)绾蝸斫鉀Q這個問題呢？對于JDK中的Entry類中的方法存在一個：boolean markedForRemoval;它就是一個典型的刪除標(biāo)志位，對于對象中如果需要刪除時，我們只是對于它做一個“軟刪除”即置一個標(biāo)志位為true就可以。而插入時，默認(rèn)狀態(tài)為false就可以。這樣的話就變成以下圖所示：

通過以上方式更好的解決沖突地址刪除數(shù)據(jù)無法檢索其他鏈路數(shù)據(jù)問題了。

2.         雙散列（余商法）

在了解開放地址散列的時候我們一直在說解決方法，但是大家都知道一個數(shù)據(jù)結(jié)構(gòu)的完善更多的是需要高效的算法。這當(dāng)中我們卻沒有涉及到。接下來我們就來看看在開放地址散列中它存在的一些不足以及如何改善這樣的方法，既而達(dá)到無論是在方法的解決上還是在算法的復(fù)雜度上更加達(dá)到高效的方案。

在圖2-1中類似這樣一些數(shù)據(jù)插入進(jìn)對象，存在沖突采用不斷移位加一的方式，直到找到不為NULL內(nèi)容的索引地址。也正是由于這樣一種可能加大了時間上的變慢。大家是否注意到像圖這樣一些數(shù)據(jù)目前呈現(xiàn)出一種連續(xù)索引的插入，而且是一種成塊是的數(shù)據(jù)。如果數(shù)據(jù)量非常的龐大，或許這種可能性更大。盡管它解決了沖突，但是對于數(shù)據(jù)檢索的時間度來說，我們是不敢想象的。所有分布到同一個索引index上的key保持相同的路徑：index,index+1,index+2…依此類推。更加糟糕的是索引鍵值的檢索需要從索引開始查找。正是這樣的原因，對于線性探索法我們需要更進(jìn)一步的改進(jìn)。而剛才所描述這種成塊出現(xiàn)的數(shù)據(jù)也就定義成：簇。而這樣一種現(xiàn)象稱之為：主簇現(xiàn)象。

（主簇：就是沖突處理允許簇加速增長時出現(xiàn)的現(xiàn)象）而開放式地址沖突也是允許主簇現(xiàn)象產(chǎn)生的。那我們?nèi)绾蝸肀苊膺@種主簇現(xiàn)象呢？這個方式就是我們要來說明的：雙散列解決沖突法了。主要的方式為：

u       int hash=key.hasCode();

u       int index=(hash&Ox7FFFFFFF)%table.length;

u       按照以上方式得到索引存在沖突，則開始對當(dāng)前索引移位，而移位方式為：

        offset=(hash&Ox7FFFFFFF)/table.length;

u       如果第一次移位還存在同樣的沖突，則繼續(xù)：當(dāng)前沖突索引位置（索引號+余數(shù)）%表.length

u       如果存在的余數(shù)恰好是表的倍數(shù)，則作偏移位置為一下移，依此類推

這樣雙散列沖突處理就避免了主簇現(xiàn)象。至于HashSet的原理基本和它是一致的，這里不再復(fù)述。在這里其實還是主要說了一些簡單的解決方式，而且都是在一些具體參數(shù)滿足條件下的說明，像一旦數(shù)據(jù)超過初始值該需要rehash，加載因子一旦大于1.0是何種情況等等。還有很多問題都可以值得我們更加進(jìn)一步討論的，比如：在java.util.HashMap中的加載因子為什么會是0.75，而它默認(rèn)的初始大小為什么又是16等等這些問題都還值得說明。要說明這些問題可能又需要更加詳盡的說明清楚。