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

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

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

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

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

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

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

1.       鍵式散列 

2.       開放地址法

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

清晰了這幾個(gè)定義，我們?cè)賮砜淳唧w的解決方式

鍵式散列：

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

                         78938-0000

                         45678-0001

                         72678-0002

                         24678-0001

                         16678-0001

                         98678-0003

                         85678-0002

                         45232-0004

步驟：

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

2.       int index=hash%表大小；

3.       逐步按順序插入對(duì)象中

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

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

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

int hash;

Object key;

Entry next;

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

開放地址法：

1.         線性地址探測(cè)法：

如何理解這個(gè)概念呢，一句話：就是通過算法規(guī)則在對(duì)象地址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的為止。這種處理方式也叫：線性地址探測(cè)法(offset-of-1)

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

對(duì)于上圖的注釋步驟說明：

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

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

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

2.         雙散列（余商法）

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

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

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

u       int hash=key.hasCode();

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

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

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

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

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

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