java中和hash相關(guān)并且常用的有兩個類hashTable和hashMap,兩個類的底層存儲都是數(shù)組，這個數(shù)組不是普通的數(shù)組，而是被稱為散列表的東西。

散列表是一種將鍵映射到值的數(shù)據(jù)結(jié)構(gòu)。它用哈希函數(shù)來將鍵映射到小范圍的指數(shù)（一般為[0..哈希表大小-1]）。同時需要提供沖突和對沖突的解決方案。

今天我們來學(xué)習(xí)一下散列表的特性和作用。

文末有代碼地址，歡迎下載。

散列表中比較關(guān)鍵的三個概念就是散列表，hash函數(shù)，和沖突解決。

散列是一種算法（通過散列函數(shù)），將大型可變長度數(shù)據(jù)集映射為固定長度的較小整數(shù)數(shù)據(jù)集。

散列表是一種數(shù)據(jù)結(jié)構(gòu)，它使用哈希函數(shù)有效地將鍵映射到值，以便進行高效的搜索/檢索，插入和/或刪除。

散列表廣泛應(yīng)用于多種計算機軟件中，特別是關(guān)聯(lián)數(shù)組，數(shù)據(jù)庫索引，緩存和集合。

散列表必須至少支持以下三種操作，并且盡可能高效：

搜索（v） – 確定v是否存在于散列表中，

插入（v） – 將v插入散列表，

刪除（v） – 從散列表中刪除v。

因為使用了散列算法，將長數(shù)據(jù)集映射成了短數(shù)據(jù)集，所以在插入的時候就可能產(chǎn)生沖突，根據(jù)沖突的解決辦法的不同又可以分為線性探測，二次探測，雙倍散列和分離鏈接等沖突解決方法。

考慮這樣一個問題：找到給定的字符串中第一次重復(fù)出現(xiàn)的的字符。

怎么解決這個問題呢？最簡單的辦法就是進行n次遍歷，第一次遍歷找出字符串中是否有和第一個字符相等的字符，第二次遍歷找出字符串中是否有和第二個字符相等的字符，以此類推。

因為進行了n*n的遍歷，所以時間復(fù)雜度是O(n2)。

有沒有簡單點的辦法呢？

考慮一下字符串中的字符集合其實是有限的，假如都是使用的ASCII字符，那么我們可以構(gòu)建一個256長度的數(shù)組一次遍歷即可。

具體的做法就是遍歷一個字符就將相對于的數(shù)組中的相應(yīng)index中的值+1，當(dāng)我們發(fā)現(xiàn)某個index的值已經(jīng)是1的時候，就知道這個字符重復(fù)了。

數(shù)組的問題

那么數(shù)組的實現(xiàn)有什么問題呢？

數(shù)組的問題所在：

鍵的范圍必須很小。 如果我們有（非常）大范圍的話，內(nèi)存使用量會（非常的）很大。

鍵必須密集，即鍵值中沒有太多空白。 否則數(shù)組中將包含太多的空單元。

我們可以使用散列函數(shù)來解決這個問題。

通過使用散列函數(shù)，我們可以：

將一些非整數(shù)鍵映射成整數(shù)鍵，

將大整數(shù)映射成較小的整數(shù)。

通過使用散列函數(shù)，我們可以有效的減少存儲數(shù)組的大小。

hash的問題

有利就有弊，雖然使用散列函數(shù)可以將大數(shù)據(jù)集映射成為小數(shù)據(jù)集，但是散列函數(shù)可能且很可能將不同的鍵映射到同一個整數(shù)槽中，即多對一映射而不是一對一映射。

尤其是在散列表的密度非常高的情況下，這種沖突會經(jīng)常發(fā)生。

這里介紹一個概念：影響哈希表的密度或負載因子α= N / M，其中N是鍵的數(shù)量，M是哈希表的大小。

其實這個沖突的概率要比我們想象的更大，舉一個生日悖論的問題：

一個班級里面有多少個學(xué)生會使至少有兩人生日相同的概率大于 50%？

我們來計算一下上面的問題。

假設(shè)Q（n）是班級中n個人生日不同的概率。

Q（n）= 365/365×364/365×363/365×…×（365-n + 1）/ 365，即第一人的生日可以是365天中的任何一天，第二人的生日可以是除第一人的生日之外的任何365天，等等。

設(shè)P（n）為班級中 n 個人的相同生日的概率，則P（n）= 1-Q（n）。

計算可得，當(dāng)n=23的時候P(23) = 0.507> 0.5（50％）。

也就是說當(dāng)班級擁有23個人的時候，班級至少有兩個人的生日相同的概率已經(jīng)超過了50%。 這個悖論告訴我們：個人覺得罕見的事情在集體中卻是常見的。

好了，回到我們的hash沖突，我們需要構(gòu)建一個好的hash函數(shù)來盡量減少數(shù)據(jù)的沖突。

什么是一個好的散列函數(shù)呢？

能夠快速計算，即其時間復(fù)雜度是O（1）。

盡可能使用最小容量的散列表，

盡可能均勻地將鍵分散到不同的基地址∈[0..M-1]，

盡可能減少碰撞。

在討論散列函數(shù)的實現(xiàn)之前，讓我們討論理想的情況：完美的散列函數(shù)。

完美的散列函數(shù)是鍵和散列值之間的一對一映射，即根本不存在沖突。 當(dāng)然這種情況是非常少見的，如果我們事先知道了散列函數(shù)中要存儲的key，還是可以辦到的。

好了，接下來我們討論一下hash中解決沖突的幾種常見的方法。

先給出線性探測的公式：i描述為i =（base + step * 1）％M，其中base是鍵v的散列值，即h（v），step是從1開始的線性探測步驟。

線性探測的探測序列可以正式描述如下：

h（v）//基地址

（h（v）+ 1 * 1）％M //第一個探測步驟，如果發(fā)生碰撞

（h（v）+ 2 * 1）％M //第二次探測步驟，如果仍有碰撞

（h（v）+ 3 * 1）％M //第三次探測步驟，如果仍有沖突

…

（h（v）+ k * 1）％M //第k個探測步驟等…

先看個例子，上面的數(shù)組中，我們的基數(shù)是9，數(shù)組中已經(jīng)有1，3，5這三個元素。

現(xiàn)在我們需要插入10和12，根據(jù)計算10和12的hash值是1和3，但是1和3現(xiàn)在已經(jīng)有數(shù)據(jù)了，那么需要線性向前探測一位，最終插入在1和3的后面。

上面是刪除10的例子，同樣的先計算10的hash值=1，然后判斷1的位置元素是不是10，不是10的話，向前線性探測。

看下線性探測的關(guān)鍵代碼：

    //插入節(jié)點
    void insertNode(int key, int value)
    {
        HashNode temp = new HashNode(key, value);

        //獲取key的hashcode
        int hashIndex = hashCode(key);

        //find next free space
        while(hashNodes[hashIndex] != null && hashNodes[hashIndex].key != key
            && hashNodes[hashIndex].key != -1)
        {
            hashIndex++;
            hashIndex %= capacity;
        }
        //插入新節(jié)點，size+1
        if(hashNodes[hashIndex] == null || hashNodes[hashIndex].key == -1) {
            size++;
        }
        //將新節(jié)點插入數(shù)組
        hashNodes[hashIndex] = temp;
    }

如果我們把具有相同h(v)地址的連續(xù)存儲空間叫做clusters的話，線性探測有很大的可能會創(chuàng)建大型主clusters，這會增加搜索（v）/插入（v）/刪除（v）操作的運行時間。

為了解決這個問題，我們引入了二次探測。

先給出二次探測的公式：i描述為i =（base + step * step）％M，其中base是鍵v的散列值，即h（v），step是從1開始的線性探測步驟。

h（v）//基地址

（h（v）+ 1 * 1）％M //第一個探測步驟，如果發(fā)生碰撞

（h（v）+ 2 * 2）％M //第2次探測步驟，如果仍有沖突

（h（v）+ 3 * 3）％M //第三次探測步驟，如果仍有沖突

…

（h（v）+ k * k）％M //第k個探測步驟等…

就是這樣，探針按照二次方跳轉(zhuǎn)，根據(jù)需要環(huán)繞哈希表。

看一個二次探測的例子，上面的例子中我們已經(jīng)有38，3和18這三個元素了?，F(xiàn)在要向里面插入10和12。大家可以自行研究下探測的路徑。

再看一個二次探索刪除節(jié)點的例子。

看下二次探測的關(guān)鍵代碼：

    //插入節(jié)點
    void insertNode(int key, int value)
    {
        HashNode temp = new HashNode(key, value);

        //獲取key的hashcode
        int hashIndex = hashCode(key);

        //find next free space
        int i=1;
        while(hashNodes[hashIndex] != null && hashNodes[hashIndex].key != key
            && hashNodes[hashIndex].key != -1)
        {
            hashIndex=hashIndex+i*i;
            hashIndex %= capacity;
            i++;
        }

        //插入新節(jié)點，size+1
        if(hashNodes[hashIndex] == null || hashNodes[hashIndex].key == -1) {
            size++;
        }
        //將新節(jié)點插入數(shù)組
        hashNodes[hashIndex] = temp;
    }

在二次探測中，群集（clusters）沿著探測路徑形成，而不是像線性探測那樣圍繞基地址形成。 這些群集稱為次級群集（Secondary Clusters）。

由于在所有密鑰的探測中使用相同的模式，所以形成次級群集。

二次探測中的次級群集不如線性探測中的主群集那樣糟糕，因為理論上散列函數(shù)理論上應(yīng)該首先將鍵分散到不同的基地址∈[0..M-1]中。

為了減少主要和次要clusters，我們引入了雙倍散列。

先給出雙倍散列的公式：i描述為i =（base + step * h2(v)）％M，其中base是鍵v的散列值，即h（v），step是從1開始的線性探測步驟。

h（v）//基地址

（h（v）+ 1 * h2（v））％M //第一個探測步驟，如果有碰撞

（h（v）+ 2 * h2（v））％M //第2次探測步驟，如果仍有沖突

（h（v）+ 3 * h2（v））％M //第三次探測步驟，如果仍有沖突

…

（h（v）+ k * h2（v））％M //第k個探測步驟等…

就是這樣，探測器根據(jù)第二個散列函數(shù)h2（v）的值跳轉(zhuǎn)，根據(jù)需要環(huán)繞散列表。

看下雙倍散列的關(guān)鍵代碼：

    //插入節(jié)點
    void insertNode(int key, int value)
    {
        HashNode temp = new HashNode(key, value);

        //獲取key的hashcode
        int hashIndex = hash1(key);

        //find next free space
        int i=1;
        while(hashNodes[hashIndex] != null && hashNodes[hashIndex].key != key
            && hashNodes[hashIndex].key != -1)
        {
            hashIndex=hashIndex+i*hash2(key);
            hashIndex %= capacity;
            i++;
        }

        //插入新節(jié)點，size+1
        if(hashNodes[hashIndex] == null || hashNodes[hashIndex].key == -1) {
            size++;
        }
        //將新節(jié)點插入數(shù)組
        hashNodes[hashIndex] = temp;
    }

如果h2（v）= 1，則雙散列（Double Hashing）的工作方式與線性探測（Linear Probing）完全相同。 所以我們通常希望h2（v）> 1來避免主聚類。

如果h2（v）= 0，那么Double Hashing將會不起作用。