什么是哈希表

哈希表是以 Key-Value 形式存儲(chǔ)的的數(shù)據(jù)結(jié)構(gòu)，當(dāng)我們需要查找某個(gè)值，只需要輸入相應(yīng)的Key值即可。
首先我們看看整個(gè)哈希表的邏輯機(jī)構(gòu)圖

邏輯結(jié)構(gòu)圖

哈希的整個(gè)思路也比較簡(jiǎn)單，首先將Key按照特定的哈希算法（算法的選擇，根據(jù)需要而定）函數(shù)H(Key)生成哈希值，再將哈希值轉(zhuǎn)為數(shù)組的一個(gè)索引（Index）；因?yàn)椴煌墓Ｖ悼赡塬@得同意額索引，也有可能不同的Key 但哈希值相同，所以接下來(lái)就是處理索引沖突。

常見(jiàn)的哈希函數(shù)

.正整數(shù)
如果Key是正整數(shù)，常用的哈希算法就是對(duì)Key取模運(yùn)算，也就是對(duì)于長(zhǎng)度為L(zhǎng)的數(shù)組，那么對(duì)于任意的正整數(shù)N，獲得 index = N%L
.字符串
對(duì)于字符串也可以采用取模的運(yùn)算 來(lái)獲取索引值，但是須將字符串轉(zhuǎn)為正整數(shù)，常用的方法就是將字符串中的每個(gè)字符進(jìn)行hash
例如Java中：

public int hashCode() {
        int h = hash;
        if (h == 0 && value.length > 0) {
            char val[] = value;

            for (int i = 0; i < value.length; i++) {
                h = 31 * h + val[i];
            }
            hash = h;
        }
        return h;
    }

哈希沖突

拉鏈法

通過(guò)H（key）可以將哈希值轉(zhuǎn)為0 至 L-1范圍內(nèi)的索引，但是對(duì)于索引相同的情況，就需要有一種方法來(lái)解決這種問(wèn)題。
一種比較簡(jiǎn)單的辦法就是，將長(zhǎng)度為L(zhǎng) 的數(shù)組的每一個(gè)元素指向一個(gè)條鏈表，鏈表中的每一個(gè)節(jié)點(diǎn)都存儲(chǔ)散列值為該索引的鍵值對(duì)，這就是拉鏈法。下圖很清楚的描述了什么是拉鏈法。
如下圖所示

網(wǎng)絡(luò)圖片

圖中，”John Smith”和”Sandra Dee” 通過(guò)哈希函數(shù)都指向了152 這個(gè)索引，該索引又指向了一個(gè)鏈表， 在鏈表中依次存儲(chǔ)了這兩個(gè)字符串。
該方法的基本思想就是選擇足夠長(zhǎng)度的數(shù)組，使得所有的鏈表都盡可能的短小，以保證查找的效率。對(duì)采用拉鏈法的哈希實(shí)現(xiàn)的查找分為兩步，首先是根據(jù)散列值找到對(duì)應(yīng)的鏈表，然后沿著鏈表順序找到相應(yīng)的哈希值H(key)。此鏈表可以自己實(shí)現(xiàn)。當(dāng)然，您也可以使用Java里面內(nèi)置的LinkedList。使用拉鏈法最關(guān)鍵的就是選擇合適長(zhǎng)度的數(shù)組，使得因?yàn)殒湵硖L(zhǎng)而增加查找時(shí)間，又不會(huì)因?yàn)榭罩玫逆湵淼睦速M(fèi)空間。

開(kāi)放地址法

這種方法也稱(chēng)再散列法，其基本思想是：當(dāng)關(guān)鍵字key的哈希地址p=H（key）出現(xiàn)沖突時(shí)，以p為基礎(chǔ)，產(chǎn)生另一個(gè)哈希地址p₁，如果p₁仍然沖突，再以p為基礎(chǔ)，產(chǎn)生另一個(gè)哈希地址p₂，以此類(lèi)推直到找出一個(gè)不沖突的哈希地址p_i ，將相應(yīng)元素存入其中。這種方法有一個(gè)通用的再散列函數(shù)形式：
Hi=（H（key）+d_i）% m （i=1，2，…，n)
其中H（key）為哈希函數(shù)，m 為表長(zhǎng)，d_i稱(chēng)為增量序列。增量序列的取值方式不同，相應(yīng)的再散列方式也不同。主要有以下三種：

1.線性探測(cè)再散列法

d_i(i=1，2，3，…，m-1)
這種方法的特點(diǎn)是：沖突發(fā)生時(shí)，順序查看表中下一單元地址，直到找出一個(gè)空單元或查遍全表。

2.二次探測(cè)再散列

d_i=1²，-1²，2²，-2²，…，k²，-k² ( k<=m/2)
這種方法的特點(diǎn)是：沖突發(fā)生時(shí)，在表的左右進(jìn)行跳躍式探測(cè)，比較靈活。

3.偽隨機(jī)探測(cè)再散列

d_i=偽隨機(jī)數(shù)序列。具體實(shí)現(xiàn)時(shí)，應(yīng)建立一個(gè)偽隨機(jī)數(shù)發(fā)生器，（如i=(i+p) % m），并給定一個(gè)隨機(jī)數(shù)做起點(diǎn)。

例如，已知哈希表長(zhǎng)度m=11，哈希函數(shù)為：H（key）= key % 11，則H（47）=3，H（26）=4，H（60）=5，假設(shè)下一個(gè)關(guān)鍵字為69，則H（69）=3，與47沖突。
如果用線性探測(cè)再散列處理沖突，下一個(gè)哈希地址為H₁=（3 + 1）% 11 = 4，仍然沖突，再找下一個(gè)哈希地址為H₂=（3 + 2）% 11 = 5，還是沖突，繼續(xù)找下一個(gè)哈希地址為H₃=（3 + 3）% 11 = 6，此時(shí)不再?zèng)_突，將69填入5號(hào)單元。
如果用二次探測(cè)再散列處理沖突，下一個(gè)哈希地址為H₁=3 + 1²）% 11 = 4，仍然沖突，再找下一個(gè)哈希地址為H₂=（3 - 1²）% 11 = 2，此時(shí)不再?zèng)_突，將69填入2號(hào)單元。
如果用偽隨機(jī)探測(cè)再散列處理沖突，且偽隨機(jī)數(shù)序列為：2，5，9，……..，則下一個(gè)哈希地址為H₁=（3 + 2）% 11 = 5，仍然沖突，再找下一個(gè)哈希地址為H₂=（3 + 5）% 11 = 8，此時(shí)不再?zèng)_突，將69填入8號(hào)單元。

再哈希法

這種方法是同時(shí)構(gòu)造多個(gè)不同的哈希函數(shù)：
H=RH_i（key） （i=1，2，…，k)
當(dāng)哈希地址H=RH_i（key）發(fā)生沖突時(shí)，再計(jì)算H=RH_i+1（key，以此類(lèi)推直到?jīng)_突不再產(chǎn)生。這種方法不易產(chǎn)生聚集，但增加了計(jì)算時(shí)間。

建立公共溢出區(qū)

這種方法的基本思想是：將哈希表分為基本表和溢出表兩部分，凡是和基本表發(fā)生沖突的元素，一律填入溢出表。