從原理到應(yīng)用分析什么是哈希？

一、什么是哈希？

哈希（hash）：將任意長(zhǎng)度的輸入（關(guān)鍵字），通過(guò)Hash算法變成固定長(zhǎng)度的輸出。這個(gè)映射的規(guī)則就是對(duì)應(yīng)的Hash算法，而原始數(shù)據(jù)映射后的二進(jìn)制串就是哈希值，通常哈希值代表了關(guān)鍵字的存儲(chǔ)位置。

但是為什么要這樣做呢？或者說(shuō)，哈希是怎樣來(lái)的呢？

哈希的出現(xiàn)解決了兩個(gè)問(wèn)題：存儲(chǔ)和搜索。

1. 存儲(chǔ)（數(shù)據(jù)結(jié)構(gòu)）：如果在容器中保存對(duì)象及其關(guān)聯(lián)的鍵，并且不用鍵來(lái)決定 （鍵/對(duì)象） 對(duì)的順序，那就必須對(duì)鍵值釆用其他方式來(lái)確定元素在內(nèi)存中的位置。

如果使用像 string 這樣的對(duì)象作為鍵，就會(huì)遇到一些問(wèn)題，可能的變量的數(shù)目是巨大的。具有 10 個(gè)字符的字母字符串可能的個(gè)數(shù)是 26^10。這個(gè)索引范圍沒(méi)有多大用處。我們需要一種機(jī)制來(lái)將它變?yōu)榭山邮艿姆秶?；而且理想情況下，這個(gè)機(jī)制可以為每個(gè)鍵生成唯一的值，根據(jù)這個(gè)值所在的位置來(lái)找到對(duì)應(yīng)的字符串。這正是哈希需要做的事情之一。

2. 搜索（算法/思想）：當(dāng)我們處理數(shù)據(jù)的時(shí)候，不外乎使用順序結(jié)構(gòu)、鏈表和樹結(jié)構(gòu)。但是使用這些結(jié)構(gòu)時(shí)，元素的關(guān)鍵字與其存儲(chǔ)位置之間通常沒(méi)有對(duì)應(yīng)的邏輯關(guān)系，這時(shí)候想要查找一個(gè)元素，我們根本不知道它在結(jié)構(gòu)中的存儲(chǔ)位置，甚至不知道它在不在結(jié)構(gòu)中，這要求我們必須要不斷地比較關(guān)鍵字進(jìn)行查找，如順序結(jié)構(gòu)查找的時(shí)間是O(N)，樹結(jié)構(gòu)是O(logN)，通常這帶來(lái)的結(jié)果是不斷for循環(huán)遍歷，極大地增加了代碼時(shí)間復(fù)雜度。

那么可不可以有更好的搜索方法呢？哈希函數(shù)應(yīng)運(yùn)而生：由上面的定義可知，hash完美解決了這一問(wèn)題，可以不經(jīng)過(guò)任何比較，直接從哈希表/集中得到要搜索的元素或判斷是否存在。

二、哈希會(huì)出現(xiàn)的問(wèn)題

哈希有兩種缺點(diǎn)：實(shí)際缺點(diǎn)和根本缺點(diǎn)。

1. 根本缺點(diǎn)：

哈希表的缺點(diǎn)它是基于數(shù)組的，數(shù)組創(chuàng)建后難于擴(kuò)展某些哈希表被基本填滿時(shí)，性能下降得非常嚴(yán)重，所以程序雖必須要清楚表中將要存儲(chǔ)多少數(shù)據(jù)（或者準(zhǔn)備好定期地把數(shù)據(jù)轉(zhuǎn)移到更大的哈希表中，這是個(gè)費(fèi)時(shí)的過(guò)程）。

而且，也沒(méi)有一種簡(jiǎn)便的方法可以以任何一種順序〔例如從小到大〕遍歷表中數(shù)據(jù)項(xiàng)。如果需要這種能力，就只能選擇其他數(shù)據(jù)結(jié)構(gòu)。

然而如果不需要有序遍歷數(shù)據(jù)，井且可以提前預(yù)測(cè)數(shù)據(jù)量的大小。那么哈希表在速度和易用性方面是無(wú)與倫比的。

2. 實(shí)際缺點(diǎn)：

哈希沖突：由于哈希算法被計(jì)算的數(shù)據(jù)是無(wú)限的，而計(jì)算后的結(jié)果范圍有限，因此總會(huì)存在不同的數(shù)據(jù)經(jīng)過(guò)計(jì)算后得到的值相同，這就是哈希沖突，即不同的關(guān)鍵字得到的值相同。

這樣的話我們前面所有的理想情況就成了笑談，所以處理問(wèn)題時(shí)要解決哈希沖突。

三、構(gòu)造哈希算法

基本原則：便于計(jì)算（函數(shù)計(jì)算時(shí)間<=查找時(shí)間）；（散列地址）分布均勻

（1）直接定址法

直接定值法是取關(guān)鍵字的某個(gè)線性函數(shù)值為散列地址，即 f(key) = a*key + b。其優(yōu)點(diǎn)是簡(jiǎn)單、均勻，不會(huì)產(chǎn)生沖突；但缺點(diǎn)是需要知道關(guān)鍵字的分布情況，希望數(shù)值是連續(xù)的。

（2）數(shù)字分析法

數(shù)字分析法通常適合處理關(guān)鍵字位數(shù)比較大的情況，例如我們現(xiàn)在要存儲(chǔ)外賣信息登記表，如果用手機(jī)號(hào)作為關(guān)鍵字，那么抽取后面的四位數(shù)字作為散列地址是不錯(cuò)的選擇。

（3）平方取中法

平方取中法是將關(guān)鍵字平方之后取中間若干位數(shù)字作為散列地址。這種方法適用于不知道關(guān)鍵字的分布，且數(shù)值的位數(shù)又不是很大的情況。

（4）折疊法

折疊法是將關(guān)鍵字從左到右分割成位數(shù)相等的幾部分，然后將這幾部分疊加求和，并按散列表表長(zhǎng)取后幾位作為散列地址。

（5）除留余數(shù)法

此方法最常用：f(key) = key mod p(p <= n)  n：散列表的長(zhǎng)度。

p的選擇非常非常非常重要。

（6）隨機(jī)數(shù)法

f(key) = random(key)

當(dāng)關(guān)鍵字的長(zhǎng)度不等時(shí)，采用這個(gè)方法構(gòu)造散列函數(shù)是比較合適的。

四、處理哈希沖突

（1）開放定址法

當(dāng)發(fā)生哈希沖突時(shí)，尋找下一個(gè)空的散列地址，只要散列表足夠大，空的散列地址總能找到，處理沖突的過(guò)程結(jié)束，記錄填入的位置：

fi(key) = (f(key)+di) MOD n       

di為增量序列，可以有下列三種取法：

1. di = 1,2,...,n-1：線性探測(cè)再散列；

2. di = 1^2,-1^2,...,k^2,-k^2(k<=n/2) 二次探測(cè)再散列

3. di = 偽隨機(jī)數(shù)序列：偽隨機(jī)探測(cè)再散列

（2）鏈地址法

（3）公共溢出區(qū)法

沒(méi)有沖突的元素放在基本表，有沖突的元素，將多余的元素放在沖突表。

五、C++ STL 容器：哈希表和哈希集

（1）無(wú)序哈希表unordered_map

1. 以鍵值對(duì)（pair類型）的形式存儲(chǔ)數(shù)據(jù)

2. 存儲(chǔ)的各個(gè)鍵值對(duì)的鍵互不相同且不允許被修改

3. 不會(huì)自行對(duì)存儲(chǔ)的鍵值對(duì)進(jìn)行排序

代碼如下：

#include <iostream>
#include <unordered_map> //哈希表頭文件
using namespace std;
 
int main(){
    //建立哈希表
    unordered_map<Type,Type> hashsmap
    //第一個(gè)Type是鍵的變量類型，第二個(gè)是值得變量類型，hashmap是該哈希表的名稱
    
    //插入鍵值對(duì)的兩種方法
    hashmap.insert(make_pair(key，value));
    hashmap[key] = value;
    
    //刪除鍵值對(duì)
    hashset.erase(key)
    
    //查詢鍵值
    cout<<hashmap[key]<<endl;
     
    //搜索鍵值對(duì)
    if(hashmap.count(key)>0) cout<<"exist"<<endl;
 
    //遍歷哈希表
    for (auto i = hashmap.begin(); i != hashmap.end(); i++) 
    {
        cout << "(" << i->first << "," << i->second << ") "<<endl;
    }
    
    /* 其他常用方法
     * empty() 若容器為空，返回true；
     * size() 返回當(dāng)前容器存有鍵值對(duì)的個(gè)數(shù)
     * at(key) 返回容器中存儲(chǔ)的鍵key對(duì)應(yīng)的值，如果key不存在，則會(huì)拋出out_of_range異常
     * clear() 清空容器
     * find(key) 查找以 key 為鍵的鍵值對(duì)，如果找到，則返回一個(gè)指向該鍵值對(duì)的正向迭代器；反之，                
     * 則返回一個(gè)指向容器中最后一個(gè)鍵值對(duì)之后位置的迭代器（如果 end() 方法返回的迭代器)     
     */
 
}

（2）無(wú)序哈希集unordered_set

無(wú)序哈希集是一種功能簡(jiǎn)單的哈希結(jié)構(gòu)：

1. 不再以鍵值對(duì)的形式存儲(chǔ)數(shù)據(jù)，而是直接存儲(chǔ)數(shù)據(jù)的值(存儲(chǔ)的鍵值對(duì) 鍵和值相同 所以只存value即可)；

2. 容器內(nèi)部存儲(chǔ)的各個(gè)元素的值都互不相等，且不能被修改；

3. 不會(huì)自行對(duì)內(nèi)部存儲(chǔ)的數(shù)據(jù)進(jìn)行排序。

代碼如下：

#include <iostream>
#include <unordered_set> //哈希集頭文件
using namespace std;
 
int main(){
    //建立哈希集
    unordered_set<Type> hashset
    //Type是哈希集中鍵的變量類型，hashset是該哈希集的名稱
    
    //插入鍵
    hashset.insert(key)
    
    //刪除鍵
    hashset.erase(key)
    
    //搜索鍵
    if(hashset.count(key) > 0) cout<<"exist"<<endl;
    
    //遍歷哈希集
    for (auto i = hashset.begin(); i != hashset.end(); i++) 
    {
        cout << (*i) << endl;
    }
    
    /* 其他常用方法
     * empty() 若容器為空，返回true；
     * size() 返回當(dāng)前容器存有元素的個(gè)數(shù)
     * clear() 清空容器
     * find(key)查找以值為 key 的元素，如果找到，則返回一個(gè)指向該元素的正向迭代器；反之，則返回一            
     * 個(gè)指向容器中最后一個(gè)元素之后位置的迭代器（如果 end() 方法返回的迭代器）
     */
 
}