哈希化就是想辦法將我們要保存的數(shù)據(jù)對應一個數(shù)組下標，在數(shù)組的該位置下保存數(shù)據(jù)；我們可以把這個過程專業(yè)一點的說一下：把要保存的數(shù)據(jù)，通過哈希函數(shù)轉化為對應的數(shù)組下標；現(xiàn)在我們的目標就是怎么編寫一個哈希函數(shù)可以使得字符串變成數(shù)組下標；

這里我們可以假設一個字符串t數(shù)組的大小為30，String[] str = new String[30];   要存“cats”這個單詞，最容易想到的辦法就是用ASCII碼，但是由于ASCII碼太多了不好記，于是我們可以自己設置一套規(guī)則，我就假設a到z分別對應1到26，外加空格對應0，現(xiàn)在一套最簡陋的規(guī)則就出來了,我那么“cats”這個單詞：c = 3,a = 1,t = 20,s = 19，現(xiàn)在“cats”有兩種辦法變成數(shù)組的下標；

額外補充一下：假如我們要保存的字符串有50個，那么我們new的數(shù)組大小一定要是它的兩倍大，即 new String[100];，后面會說到這個原因

2.1哈希函數(shù)實現(xiàn)一

怎么實現(xiàn)比較好呢？別想那么多，直接相加就好，3+1+20+19 = 43，這個時候就有個小問題，我們的數(shù)組的大小為30，也就是說數(shù)組下標最大值是29，而這里我們的數(shù)字為43，怎么將43變成29以內的數(shù)（包括29）呢？因為任何數(shù)除以30的余數(shù)只都在0-29之間，于是我們用43除以30拿到余數(shù)13，那么我們就把”cats“放到數(shù)組下標為13的位置,str[13] = "cats";

這種哈希函數(shù)的實現(xiàn)很容易，但是往往越容易的東西缺點就越大，最大的缺陷就是有很多單詞變成數(shù)字是相同的，比如was，tin，give等100多個單詞變成數(shù)字后都是43，然后我們恰巧添加單詞的時候就是這些單詞，現(xiàn)在問題來了，多個單詞最后算出來的數(shù)組下標很大概率上是一樣的，也就是數(shù)組一個位置要放多個數(shù)據(jù)，怎么解決這個問題呢？我們可以換一種哈希函數(shù)的實現(xiàn)來降低這個概率

2.2 哈希函數(shù)實現(xiàn)二

由2.1可以知道太多的單詞變成數(shù)字的結果是一樣的，那么我們就要想辦法為每一個單詞都對應一個獨一無二的整數(shù)，然后用這個整數(shù)除以數(shù)組的大小取余數(shù)，就可以知道該單詞在數(shù)組中的存放位置；

于是啊，我們可以利用冪的連乘來得到這個獨一無二的整數(shù)，比如“cats”用這種計算方法：3*273+1*272+20*271+19*270，有點類似二進制變成十進制，通過這個算法，可以得到一個獨一無二的整數(shù)，其他的任何單詞通過這種方法算出來的結果幾乎是不可能相等的，有興趣的可以試試；然后將這個計算結果除以30取余數(shù)，就可以得到一個數(shù)組的位置，然后將該字符串丟到里面即可；

不知道大家有沒有發(fā)現(xiàn)這種方法的一個問題，因為數(shù)組的大小是一定的，而且我們是通過取余數(shù)來得到數(shù)組的位置，那么問題來了，即使是兩個不相同的整數(shù)分別除以30，最后的余數(shù)是相等的；

就比如有兩個字符串通過冪的連乘最后得到32和62（當然我們這里肯定不會得到這兩個整數(shù)，為了好理解隨便拿兩個數(shù)），雖然這兩個數(shù)是獨一無二的，但是除以30余數(shù)都為2，那么兩個數(shù)據(jù)要保存到哈希表中肯定會有沖突，下后面我們來解決一下這個沖突；

有個簡單的哈希函數(shù)實現(xiàn)看一下（雖然還可以進行修改一下，但是這個已經差不多了）；

3.沖突

沖突的原因就是兩個獨一無二的整數(shù)除以數(shù)組的大小，取余數(shù)是相等的，而數(shù)組中一個位置只能存一個數(shù)據(jù)，這就導致了沖突，解決沖突的辦法有兩種；

3.1 解決方法一（開放地址法）

還記得前面說過數(shù)組的大小要為實際數(shù)量的兩倍嗎？就是為了這個時候用的，假如一個單詞已經放在了數(shù)組的第15個位置那里，另外一個單詞本來也要放在第15的位置，由于這個位置已經被別人占了。那就放在數(shù)組的另外一個位置上，反正還有很多數(shù)組比較大，這種方式叫做------開放地址法

3.2 解決方法二（鏈地址法 ）

既然有兩個數(shù)據(jù)都要放在數(shù)組的一個位置上，那就想辦法把第二個數(shù)據(jù)連在第一個數(shù)據(jù)后面，通過第一個數(shù)據(jù)可以找到第二個數(shù)據(jù)，而數(shù)組中只保存第一個數(shù)據(jù)的地址；其實就是一句話，數(shù)組中每個位置放一個鏈表；

這種方法的好處很明顯，完美解決上述沖突，不需要用什么花里胡哨的操作；缺陷就是當鏈表太長了，我們要查詢這個鏈表的最后面的數(shù)據(jù)，只能慢慢遍歷這個鏈表，而我們知道，鏈表的優(yōu)勢是插入和刪除，而對于查詢這種操作是比較坑爹的，而我們前面用了紅黑樹這樣的結構來完美解決鏈表的缺點；最后，我們就差不多想到了一個比較實用的方法：數(shù)組的每個位置都存放一個鏈表，當鏈表的節(jié)點很少的時候，那就用鏈表吧！但是當鏈表慢慢的變長，當節(jié)點數(shù)目到達一個界限的時候，我們就把這個鏈表變成一個紅黑樹，比較完美的方案，這也叫做------鏈地址法 

順便一提，jdk7的HashMap就是數(shù)組中放鏈表，即使鏈表很長也不會變紅黑樹；jdk8中的HashMap才增加了變紅黑樹這個操作

4.開放地址法

所謂的開放地址法就是：根據(jù)我們要保存的數(shù)據(jù)計算出來的數(shù)組下標的那個位置已經存放了數(shù)據(jù)，這個時候我們就要再找一個空位置，然后將要保存的數(shù)據(jù)丟進去即可，那么怎么找比較好呢？這里提供三種方式，線性探測，二次探測和再哈希法，下面就看看這三種方式到底是怎么工作的；

4.1 線程探測

看名字線性就知道是從前往后尋找空的位置，舉個很簡單的例子，當一個字符串經過運算對應于數(shù)組下標為52，然而此時52這個位置上已經有了數(shù)據(jù)，那么就嘗試放到53的位置，假如53的位置也已經放了數(shù)據(jù)，那就放到54位置，就這樣一直往后慢慢找，直到找到一個空的位置就把數(shù)據(jù)放進去；而此時找的次數(shù)越多，假如已經找到56的位置，那么從53到56這么多位置叫做填充序列，當填充序列很長的時候，我們就稱為原始聚集，下圖所示：

這里填充序列的中有5個填充單元，我們也可以說步數(shù)為1，每次探測都是前進一步；我們可以知道當探測的次數(shù)越多的時候，說明聚集越嚴重，下一次再想添加到這個位置的數(shù)據(jù)的效率就越低；

還有就是當哈希表填充得越滿，效率也就越低，所以當哈希表快滿了之后就要擴展，而java中數(shù)組是不能直接進行擴展的，需要再新建一個數(shù)組，然后想辦法將這個哈希表中的數(shù)據(jù)復制到新的數(shù)組中，注意，這里不能直接復制，因為新的數(shù)組的容量和原來的數(shù)組不一樣，那么原來哈希表中所有的數(shù)據(jù)必須要重新哈?；?，然后放入到新的數(shù)組中，非常耗時....

4.2 二次探測

根據(jù)前面我們的線性探測可以知道，假如經過哈希函數(shù)計算出來的原始數(shù)組下標為x，那么線性探測的位置是x+1，x+2，x+3，x+4.....,；那么 進行二次探測找的位置就是x+12，x+22，x+32，x+42.....其實就是按照步數(shù)的平方進行探測看里面有沒有數(shù)據(jù)，沒有的話才放進去新的數(shù)據(jù)，二次探測可以防止聚集太長所導致的效率下降問題；

對于二次探測來說，如果當前計算出來的位置為x，首先會探測x后面一個位置，如果這個位置有數(shù)據(jù)，那就多往后4個位置看有沒有數(shù)據(jù)，假如還是有數(shù)據(jù)，那么二次探測可能會覺得你這個聚集特別長，于是這次跳得更遠的位置，當前位置后面的16的位置等等，直到最后跳過整個數(shù)組， 這樣可以避免一個一個的位置慢慢探測的底下效率，二次探測下圖所示：

二次探測也有點問題，會導致二次聚集，那什么又是二次聚集呢？其實跟原始聚集差不多吧！比如184，302，420，544這幾個整數(shù)都要放到哈希表中，而且這幾個數(shù)經過哈希算法算出來的數(shù)組下標都為7，302需要以1步長進行探測，而420要先以1為步長，然后以4步長進行探測，而544要先以1為步長，然后以4為步長，最后以16步長進行探測，假如后面還有數(shù)據(jù)對應的數(shù)組下標為7，那么還是要重復這個步驟，而且是越來越長....這也是一種聚集，個人感覺從某種意義來說和原始聚集性質差不多吧！

二次探測不常用，因為有更好的辦法解決，就是再哈希法；

4.3 再哈希法

用再哈希法可以消除原始聚集和二次聚集，那么什么是再哈希法呢？我們可以知道產生原始聚集和二次聚集的原因其實差不多，都是由于多個數(shù)據(jù)添加到哈希表中的同一個位置，然后根據(jù)步長一個一個位置的探測，直到找到一個空的位置，如果需要找的位置特別多，那么這就是聚集，添加的效率的就會大幅度降低； 

那么我們就要想一種方法即使多個數(shù)據(jù)要放在哈希表的同一個位置，但是不需要從頭開始一個一個位置的探測，如果每個數(shù)據(jù)都可以產生一個獨一無二的步長那不就好了么！然后直接根據(jù)這個步長探測該位置將數(shù)據(jù)丟進去就ok了；

于是我們準備了兩個哈希函數(shù)，一個哈希函數(shù)就是我們上面說到的可以產生對應的數(shù)組下標，另外一個哈希函數(shù)可以產生步長，其實就是多個數(shù)據(jù)放在同一個位置產發(fā)生沖突，就用這個哈希函數(shù)再次哈希化產生一個步長，根據(jù)這個步長進行探測就可以了，而不用每次都從第一個步長開始；比如下面就有一個產生步長的哈希函數(shù)，我們可以知道步長的范圍是1-constant，注意步長不能為0，否則就原地踏步了。。。

上圖中，假如我們往哈希表中添加的數(shù)據(jù)是數(shù)字，那就直接將數(shù)據(jù)和數(shù)組大小取余得到數(shù)組下標，這里的key就是我們的數(shù)據(jù)，constant只要是小于數(shù)組容量的一個質數(shù)，隨便什么都可以

順便一提：再哈希法使用的前提必須保證數(shù)組的容量為一個質數(shù)，因為這樣才能使得所有位置都被探測到；可以試試假如數(shù)組容量為15，步長為5，一個數(shù)據(jù)經過計算得到額數(shù)組下標為0，那么探測的位置應該為：（0+5）%15 = 5,、（5+5）%15 = 10，（10+5）%15 = 0，只會探測0、5、10這三個位置；但是如果數(shù)組容量為質數(shù)13，步長為5，第一個數(shù)據(jù)下標還是0，那么探測位置為：（0+5）%13 = 5,、（5+5）%13 = 10，（10+5）%13 = 2、（2+5）%13 = 7，（7+5）%13 = 12，（12+5）%13 = 4，（4+5）%13 = 9等等，可以看到每次探測的位置都不一樣，可以探測到數(shù)組中所有位置只要有空的就把數(shù)據(jù)當進去即可；

假如使用的是開放地址法，那么探測序列就用這個再哈希法生成，其實很容易！

5.鏈地址法 

可以看到上面的開放地址法有點麻煩，需要找到探測序列真的是日了狗了，麻煩的我都不想看了，如果可以不用這么麻煩那該多好呀，ok，那就用鏈地址法吧！就類似下面這樣的結構，原始的數(shù)組中不直接保存數(shù)據(jù)，每個位置只是保存第一個數(shù)據(jù)的引用，通過該位置第一個引用就可以取到后面所有的數(shù)據(jù)！如果鏈表太長遍歷起來就比較費勁，可以轉為紅黑樹效率就高了很多；

這里其實沒什么好說的，因為數(shù)組和鏈表的使用很熟悉了，沒什么特別難的東西，基本邏輯：只需要新建一個MyHashTable的類，這個類中有幾個屬性：一個數(shù)組，一個int類型的屬性標識數(shù)組真實容量的大??；最好有個節(jié)點類為靜態(tài)內部類，這個靜態(tài)內部類中實現(xiàn)了對鏈表的增刪改查的操作；然后在MyHashTable類中寫一個哈希函數(shù)的方法，根據(jù)這個哈希函數(shù)得出來的數(shù)組下標，最后對數(shù)組的增刪改查了！

6.總結

哈希表其實還可以用在外部存儲中，也就是硬盤中，有興趣的可以看看，不過我感覺到這里就差不多了！其實哈希表的內容沒多少吧，最主要的就是哈希函數(shù)的選取，選擇一個好的哈希函數(shù)可以使得我們的哈希表的效率更高！然后就是數(shù)組中存數(shù)據(jù)的方式，可以直接在數(shù)組中存數(shù)據(jù)，也可以在數(shù)組中存節(jié)點的引用，其實吧，知不知道二維數(shù)組？在我們這個數(shù)組中每個位置存的是另外一個數(shù)組的引用，這樣其實也行，由于擴展起來很困難，使用鏈表比使用二維數(shù)組好。。。