一、哈希的概念及其性質(zhì)

1.哈希概念

在順序結(jié)構(gòu)以及平衡樹中，元素關(guān)鍵碼與其存儲位置之間沒有對應(yīng)的關(guān)系，因此在查找一個元素時，必須要經(jīng)過關(guān)鍵碼的多次比較。比如順序表需要從第一個元素依次向后進行查找，順序查找時間復(fù)雜度為O(N)，平衡樹中需要從第一層開始逐層往下進行比較，查找的次數(shù)為樹的高度，即O(logN)，搜索的效率取決于搜索過程中元素的比較次數(shù)

盡管紅黑樹或者AVL樹的查找效率已經(jīng)很高了，但是還是不夠極致，理想的搜索方法：可以不經(jīng)過任何比較，一次直接從表中得到要搜索的元素。

如果構(gòu)造一種存儲結(jié)構(gòu)，通過某種函數(shù)(hashFunc)使元素的存儲位置與它的關(guān)鍵碼之間能夠建立一一映射的關(guān)系，那么在查找時通過該函數(shù)可以很快找到該元素，當(dāng)向該結(jié)構(gòu)中：

插入元素時 : 根據(jù)待插入元素的關(guān)鍵碼，以此函數(shù)計算出該元素的存儲位置并按此位置進行存放

搜索元素時 : 對元素的關(guān)鍵碼進行同樣的計算，把求得的函數(shù)值當(dāng)做元素的存儲位置，在結(jié)構(gòu)中按此位置取元素比較，若關(guān)鍵碼相等，則搜索成功

該方式即為哈希(散列)方法，哈希方法中使用的轉(zhuǎn)換函數(shù)稱為哈希(散列)函數(shù)，構(gòu)造出來的結(jié)構(gòu)稱為哈希表(Hash Table)(或者稱散列表)

我們需要注意的是，不管是順序查找，平衡樹查找還是哈希查找，其key值都是唯一的，也就是說，搜索樹和哈希表中都不允許出現(xiàn)相同的key 值

2.哈希函數(shù)

哈希函數(shù)設(shè)計原則：

1.哈希函數(shù)的定義域必須包括需要存儲的全部關(guān)鍵碼，而如果散列表允許有m個地址時，其值域必須在0到m-1之間

2.哈希函數(shù)計算出來的地址能均勻分布在整個空間中

3.哈希函數(shù)應(yīng)該比較簡單

常見哈希函數(shù)

1.直接定址法–(常用)

直接定址法取關(guān)鍵字的某個線性函數(shù)為散列地址：Hash（Ke）= A*Key + B

它的優(yōu)點是簡單，且不會引起哈希沖突–哈希沖突是指多個不同的key值映射到同一個存儲位置，由于直接定址法的key值經(jīng)過哈希函數(shù)轉(zhuǎn)換后得到的值一定是唯一的，所以不存在哈希沖突

直接定址法適用于數(shù)據(jù)范圍比較集中的情況，這樣key值映射到哈希表之后，哈希表的空間利用率高，浪費非空間較少，不適用與數(shù)據(jù)分散的情況，因為這樣會導(dǎo)致空間的利用率很低，從而造成空間浪費

下面是一道哈希定址法的典型例子：

387.字符串中第一個唯一字符[LeetCode]

class Solution {
public:int firstUniqChar(string s) {int arr[26]={0};for(size_t i=0;i<s.size();++i){// 題目中說明只有小寫字母，我們減去字符得到的數(shù)作為下標arr[s[i]-'a']++;}// 遍歷查找第一個為1的下標for(size_t i=0;i<s.size();++i){if(arr[s[i]-'a']==1){return i;}}return -1;}
};

2.除留余數(shù)法–(常用)

除留余數(shù)法思想 : 設(shè)散列表中允許的地址數(shù)為m，取一個不大于m，但最接近或者等于m的質(zhì)數(shù)p作為除數(shù)，按照哈希函數(shù)：Hash(key) = key% p(p<=m),將關(guān)鍵碼轉(zhuǎn)換成哈希地址

我們使用key值對哈希表的大小進行取模得到的樹作為哈希映射的地址，將key保存到該地址中，除留余數(shù)法的優(yōu)點是可以處理數(shù)據(jù)范圍分散的數(shù)據(jù)，缺點是會引發(fā)哈希沖突，比如對于數(shù)據(jù)集合：

數(shù)據(jù)集合{1，7，6，4，5，9}；

哈希函數(shù)設(shè)置為：hash(key) = key % capacity; capacity為存儲元素底層空間總的大小。

此時，如果我們繼續(xù)插入數(shù)據(jù)11，那么通過哈希函數(shù)計算出應(yīng)該存儲在下標為1的位置，但是下標為 1的位置引進存放了數(shù)據(jù)1，此時就會發(fā)生哈希沖突

3.平方取中法–(了解)

假設(shè)關(guān)鍵字為1234，對它平方就是1522756，抽取中間的3位227作為哈希地址；再比如關(guān)鍵字為4321，對它平方就是18671041，抽取中間的3位671(或710)作為哈希地址

平方取中法比較適合：不知道關(guān)鍵字的分布，而位數(shù)又不是很大的情況

4.折疊法–(了解)

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

折疊法適合事先不需要知道關(guān)鍵字的分布，適合關(guān)鍵字位數(shù)比較多的情況

5.隨機數(shù)法–(了解)

選擇一個隨機函數(shù)，取關(guān)鍵字的隨機函數(shù)值為它的哈希地址，即H(key) = random(key),其中random為隨機數(shù)函數(shù)。

通常應(yīng)用于關(guān)鍵字長度不等時采用此法

6.數(shù)學(xué)分析法–(了解)

設(shè)有n個d位數(shù)，每一位可能有r種不同的符號，這r種不同的符號在各位上出現(xiàn)的頻率不一定相同，可能在某些位上分布比較均勻，每種符號出現(xiàn)的機會均等，在某些位上分布不均勻只有某幾種符號經(jīng)常出現(xiàn)?？筛鶕?jù)散列表的大小，選擇其中各種符號分布均勻的若干位作為散列地址。

假設(shè)要存儲某家公司員工登記表，如果用手機號作為關(guān)鍵字，那么極有可能前7位都是 相同的，那么我們可以選擇后面的四位作為散列地址，如果這樣的抽取工作還容易出現(xiàn) 沖突，還可以對抽取出來的數(shù)字進行反轉(zhuǎn)(如1234改成4321)、右環(huán)位移(如1234改成4123)、左環(huán)移位、前兩數(shù)與后兩數(shù)疊加(如1234改成12+34=46)等方法

數(shù)字分析法通常適合處理關(guān)鍵字位數(shù)比較大的情況，如果事先知道關(guān)鍵字的分布且關(guān)鍵字的若干位分布較均勻的情況

注意：哈希函數(shù)設(shè)計的越精妙，產(chǎn)生哈希沖突的可能性就越低，但是無法避免哈希沖突

3.哈希沖突

對于兩個數(shù)據(jù)元素的關(guān)鍵字字$k_i$和 K_j(i != j)，有$k_i$ != $k_j$，但有：Hash($k_i$) == Hash($k_j$)，即：不同關(guān)鍵字通過相同哈希哈數(shù)計算出相同的哈希地址，該種現(xiàn)象稱為哈希沖突或哈希碰撞

解決哈希沖突兩種常見的方法是：閉散列和開散列

1.閉散列：也叫開放定址法，當(dāng)發(fā)生哈希沖突時，如果哈希表未被裝滿，說明在哈希表中必然還有空位置，那么可以把key存放到?jīng)_突位置中的“下一個”空位置中去

2.開散列法又叫鏈地址法(開鏈法)，首先對關(guān)鍵碼集合用散列函數(shù)計算散列地址，具有相同地址的關(guān)鍵碼歸于同一子集合，每一個子集合稱為一個桶，各個桶中的元素通過一個單鏈表鏈接起來，各鏈表的頭結(jié)點存儲在哈希表中,即發(fā)生哈希沖突之后，把key直接鏈接在該位置的下面

二、閉散列

閉散列：也叫開放定址法，當(dāng)發(fā)生哈希沖突時，如果哈希表未被裝滿，說明在哈希表中必然還有空位置，那么可以把key存放到?jīng)_突位置中的“下一個”空位置中去。那如何尋找下一個空位置呢？這里有兩種方法–線性探測法和二次探測法

1.線性探測

線性探測法是指從發(fā)生沖突的位置開始，依次向后探測，直到尋找到下一個空位置為止，比如下面的場景中，現(xiàn)在需要插入元素44，先通過哈希函數(shù)計算哈希地址，hashAddr為4，因此44理論上應(yīng)該插在該位置，但是該位置已經(jīng)放了值為4的元素，即發(fā)生哈希沖突，則我們可以向后尋找一個空的位置即下標為8 的位置進插入

下面我們來模擬實現(xiàn)哈希函數(shù)的除留余數(shù)法，并使用閉散列的線性探測法來解決哈希沖突的問題

2.哈希表的基本框架

哈希表節(jié)點結(jié)構(gòu)的定義如下：

#pragma once
#include <vector>namespace closeHash
{// 定義一個位置的狀態(tài)enum state{EMPTY,  // 空EXIST,  // 存在數(shù)據(jù)DELETE, //該位置數(shù)據(jù)被刪除};// 哈希表每個節(jié)點下標位置存儲的數(shù)據(jù)的結(jié)果template<class K,class V>struct HashData{pair<K, V> _kv;state _state = EMPTY;  // 默認為空};template<class K,class V, class Hash = HashFunc<K>>class HashTable{typedef HashData<K, V> Data;private:vector<Data> _tables;size_t _n = 0;  // 表中存儲的有效數(shù)據(jù)的個數(shù)};
}

為了方便，在哈希表中我們使用vector來存儲數(shù)據(jù)，并增加了一個變量n來記錄表中有效數(shù)據(jù)的個數(shù)，同時，哈希表的每一個下標位置存儲的數(shù)據(jù)都是一個KV模型的鍵值對，此外我們還需要使用一個state變量來記錄每一個位置的狀態(tài)。

原因是因為我們可能是刪除哈希表中的數(shù)據(jù)，但是我們在插入的時候，當(dāng)key映射的下標位置被占用時，key會向后尋找下一個空的位置進行插入，但是如果key走到數(shù)據(jù)尾部還沒有找到就會從數(shù)組的起始位置開始尋找。 假如我們刪除了其中的一個節(jié)點，此時我們需要查找一個節(jié)點，由于被占用的原因該節(jié)點在被刪除節(jié)點的位置的后面，我們一步一步向后找的時候，在走到被刪除節(jié)點的位置，發(fā)現(xiàn)該位置沒有數(shù)據(jù)之后就會返回false，但事實上這個數(shù)據(jù)是存在的，即使我們說刪除之后我們將該位置的數(shù)據(jù)修改為一個數(shù)字，但是選擇哪一個呢？0，-1/1都不合適，因為插入的數(shù)據(jù)是可能的任何數(shù)據(jù)，但是當(dāng)我們使用一個state來標識一個位置的狀態(tài)的時候，我們查找走到已經(jīng)被刪除位置的時候，發(fā)現(xiàn)該位置的數(shù)據(jù)被刪除了，但是查找會繼續(xù)向后進行查找。

所以，在哈希表中每個位置的數(shù)據(jù)增加了一個state變量類似標記該位置的狀態(tài)。

3.哈希表的操作

1.哈希表的插入

插入一個分為兩步：

1.通過哈希函數(shù)獲取待插入元素在哈希表中的位置

2.如果該位置中沒有元素則直接插入新元素，如果該位置中有元素發(fā)生哈希沖突，使用線性探測找到下一個空位置，插入新元素

我們插入的時候需要考慮擴容的問題，這個我們在哈希表擴容的時候再進行詳細的講解。

插入代碼如下：

template<class K>
struct HashFunc
{size_t operator()(const K& key){return (size_t)key;}
};
// 插入
bool Insert(const pair<K, V>& kv)
{// 已經(jīng)存在該值返回falseif (Find(kv.first))return false;// 大于標定負載因子，就需要擴容if (_n * 10 / _tables.size() > 7){// 使用一個新的哈希表，進行插入，然后進行交換兩個哈希表的_tablesHashTable<K, V> newHT;newHT._tables.resize(_tables.size() * 2);for (auto& e : _tables){if (e._state == EXIST){newHT.Insert(e._kv);}}_tables.swap(newHT._tables);}Hash hf;size_t hashi = hf(kv.first) % _tables.size();while (_tables[hashi]._state == EXIST){hashi++;hashi %= _tables.size();}//插入之后將該位置的狀態(tài)該為存在_tables[hashi]._kv = kv;_tables[hashi]._state = EXIST;++_n;return true;
}

2.哈希表的查找

通過哈希函數(shù)得到余數(shù)即數(shù)組下標，取出下標位置的key與目標key進行比較，相等就返回該位置的地址，如果查找到狀態(tài)為空的下標位置就返回nullptr，但是這樣有幾個需要注意的地方：

1.當(dāng)遇到狀態(tài)為空的下標位置才返回nullptr，而不是遇到狀態(tài)為刪除的位置就返回nullptr，因為我們要查找的數(shù)據(jù)可能在刪除數(shù)據(jù)的后面

2.將查找函數(shù)的返回值定義為Data*，而不是bool，這樣可以方便我們進行刪除和修改(修改key對應(yīng)的value)，查找到之后直接通過指針的解引用修改value與state

3.哈希表經(jīng)過不斷的插入和刪除，最終可能會出現(xiàn)一種極端的情況–哈希表中元素的狀態(tài)全為EXIST和DELETE，此時如果我們找空就會造成死循環(huán)，所以我們需要對這種情況進行單獨的處理

// 查找
// 查找返回那個位置的地址
Data* Find(const K& key)
{Hash hf;// 仿函數(shù)對象size_t hashi = hf(key) % _tables.size();// 記錄hashi的起始位置，避免哈希表中元素全為EXISR和DELETE造成死循環(huán)size_t starti = hashi;while (_tables[hashi]._state != EMPTY){// key相等且state為EXIST才表示找到if (_tables[hashi]._state == EXIST && _tables[hashi]._kv.first == key){return &_tables[hashi];}++hashi;hashi %= _tables.size();// 如果找了一圈都沒有找到，則跳出循環(huán)if(starti == hashi)break;}return nullptr;
}

3.哈希表的刪除

哈希表的刪除我們復(fù)用查找函數(shù)，查到到就通過查找函數(shù)的返回值將下標位置數(shù)據(jù)的狀態(tài)置為DELETE即可，沒有找到就返回false

代碼如下：

// 刪除
bool Erase(const K& key)
{Data* ret = Find(key);if (ret){// 刪除之后將該位置的狀態(tài)改為刪除ret->_state = DELETE;--_n;return true;}else{return false;}
}

4.哈希表的擴容

哈希表的擴容和普通順序表容器的擴容不同，它不是容器滿了才進行擴容，而是會有一個負載因子，當(dāng)負載因子 超過一定大小時才會進行擴容，書上對負載因子的表述如下：

哈希的擴容并不是簡單的擴大空間，而是需要將已經(jīng)插入到哈希表中的元素取出全部重新進行插入，因為擴容后會導(dǎo)致哈希表的長度改變，那么key通過哈希函數(shù)映射到的位置也會發(fā)生改變，所以需要重新進行插入

我們這里使用一個HashTable對象進行插入，然后交換二者的數(shù)組

// 插入
bool Insert(const pair<K, V>& kv)
{// 已經(jīng)存在該值返回falseif (Find(kv.first))return false;// 大于標定負載因子，就需要擴容if (_n * 10 / _tables.size() > 7){// 使用一個新的哈希表，進行插入，然后進行交換兩個哈希表的_tablesHashTable<K, V> newHT;newHT._tables.resize(_tables.size() * 2);for (auto& e : _tables){if (e._state == EXIST){newHT.Insert(e._kv);}}_tables.swap(newHT._tables);}Hash hf;size_t hashi = hf(kv.first) % _tables.size();while (_tables[hashi]._state == EXIST){hashi++;hashi %= _tables.size();}//插入之后將該位置的狀態(tài)該為存在_tables[hashi]._kv = kv;_tables[hashi]._state = EXIST;++_n;return true;
}

5.哈希表的仿函數(shù)

我們插入的key值不是整數(shù)的時候，但是我們要讓key與哈希表的長度取模得到映射位置，此時我們就需要進行兩次轉(zhuǎn)換，先將其他類型的數(shù)據(jù)轉(zhuǎn)換成整數(shù)，再將該整數(shù)作為key轉(zhuǎn)換為下標，比如我們統(tǒng)計水果數(shù)量的時候，就需要先將字符串轉(zhuǎn)換為整數(shù)作為key值，然后再進行映射。

由于key值可以是不同類型的數(shù)據(jù)，我們不能只考慮字符串，字符串我們可以選擇使用[]的方式獲得第一個字符，但是對于其他類型就不再適用了，所以我們需要使用仿函數(shù)來幫我們解決這個問題。

我們可以為哈希表增加一個模板參數(shù)，給模板參數(shù)是一個仿函數(shù)，仿函數(shù)分為設(shè)計者提供的默認的仿函數(shù)和用戶提供的仿函數(shù)，系統(tǒng)默認提供的仿函數(shù)可以將一些常見的key的類型全部轉(zhuǎn)換為整形，比如字符串，指針，整數(shù)。而用戶提供的仿函數(shù)則可以根據(jù)用戶自己的需求將對應(yīng)的key值轉(zhuǎn)換為整形。

代碼如下：

template<class K>
struct HashFunc
{size_t operator()(const K& key){return (size_t)key;}
};// 特化 --針對string類型寫一個仿函數(shù)--轉(zhuǎn)成整形
template<>
struct HashFunc<string>
{size_t operator()(const string& key){size_t hash = 0;for (auto& ch : key){hash *= 131;hash += ch;}return hash;}
};

有了仿函數(shù)之后，我們只需要在key與TableSize取模的地方使用仿函數(shù)對象將key轉(zhuǎn)換為整形即可。這樣，對于常見的key類型，哈希表可以通過內(nèi)置的默認仿函數(shù)來完成下標的映射，對于用戶自定義的key類型，需要我們自己提供對應(yīng)的仿函數(shù)類來完成下標的映射

6.字符串的哈希算法

哈希表中key值的類型在我們?nèi)粘Ｉ钪羞\用十分的廣泛，我們可以取第一個字符來進行映射，但是這樣很容易發(fā)生哈希沖突–只要字符串的首字母相同就會發(fā)生沖突，我們也可以考慮將字符串的所有字符的ASCII值加起來作為key值進行映射，但是對于這樣的字符串–“abc" “acb” “bca” "aad"等等，這樣的字符串的ASCII值相等也會發(fā)生哈希沖突

所有就有人專門研究看字符串哈希算法，即如何將字符串轉(zhuǎn)換為整形可以使得將哈希沖突率變得很低，下面的一篇博客介紹了許多優(yōu)秀非字符串哈希算法，我們可以借鑒學(xué)習(xí)學(xué)習(xí)：各種字符串Hash-clq-博客園(cnblogs.com)

其中BKDR哈希字符串算法是最出名也是平均分最高的，上面我們的代碼中字符串算法就是使用的該算法

7.完整代碼

這里我們需要注意的是，哈希表的拷貝構(gòu)造，析構(gòu)，賦值重載使用我們編譯器默認生成的即可–對于自定義類型編譯器會調(diào)用自定義類型的拷貝構(gòu)造，析構(gòu)和賦值重載，由于table是vector類型的成員變量，而vector中實現(xiàn)了深拷貝與析構(gòu)，所以不需要我們自己來實現(xiàn)

HashTable.h

#pragma once#include <vector>template<class K>
struct HashFunc
{size_t operator()(const K& key){return (size_t)key;}
};// 特化 --針對string類型寫一個仿函數(shù)--轉(zhuǎn)成整形
template<>
struct HashFunc<string>
{size_t operator()(const string& key){size_t hash = 0;for (auto& ch : key){hash *= 131;hash += ch;}return hash;}
};namespace closeHash
{// 定義一個位置的狀態(tài)enum state{EMPTY,  // 空EXIST,  // 存在數(shù)據(jù)DELETE, //該位置數(shù)據(jù)被刪除};template<class K,class V>struct HashData{pair<K, V> _kv;state _state = EMPTY;};template<class K,class V, class Hash = HashFunc<K>>class HashTable{typedef HashData<K, V> Data;public:// 默認構(gòu)造HashTable():_n(0){_tables.resize(10);}// 插入bool Insert(const pair<K, V>& kv){// 已經(jīng)存在該值返回falseif (Find(kv.first))return false;// 大于標定負載因子，就需要擴容if (_n * 10 / _tables.size() > 7){// 使用一個新的哈希表，進行插入，然后進行交換兩個哈希表的_tablesHashTable<K, V> newHT;newHT._tables.resize(_tables.size() * 2);for (auto& e : _tables){if (e._state == EXIST){newHT.Insert(e._kv);}}_tables.swap(newHT._tables);}Hash hf;size_t hashi = hf(kv.first) % _tables.size();while (_tables[hashi]._state == EXIST){hashi++;hashi %= _tables.size();}//插入之后將該位置的狀態(tài)該為存在_tables[hashi]._kv = kv;_tables[hashi]._state = EXIST;++_n;return true;}// 查找
// 查找返回那個位置的地址Data* Find(const K& key){Hash hf;// 仿函數(shù)對象size_t hashi = hf(key) % _tables.size();// 記錄hashi的起始位置，避免哈希表中元素全為EXISR和DELETE造成死循環(huán)size_t starti = hashi;while (_tables[hashi]._state != EMPTY){// key相等且state為EXIST才表示找到if (_tables[hashi]._state == EXIST && _tables[hashi]._kv.first == key){return &_tables[hashi];}++hashi;hashi %= _tables.size();// 如果找了一圈都沒有找到，則跳出循環(huán)if (starti == hashi)break;}return nullptr;}// 刪除bool Erase(const K& key){Data* ret = Find(key);if (ret){// 刪除之后將該位置的狀態(tài)改為刪除ret->_state = DELETE;--_n;return true;}else{return false;}}private:vector<Data> _tables;size_t _n = 0;  // 表中存儲的有效數(shù)據(jù)的個數(shù)};
}

Test.cpp

#define _CRT_SECURE_NO_WARNINGS 1#include <iostream>
using namespace std;#include "HashTable.h"void TestHT1()
{closeHash::HashTable<int, int> ht;int a[] = { 18, 8, 7, 27, 57, 3, 38, 18 };for (auto e : a){ht.Insert(make_pair(e, e));}ht.Insert(make_pair(17, 17));ht.Insert(make_pair(5, 5));cout << ht.Find(7) << endl;cout << ht.Find(8) << endl;ht.Erase(7);cout << ht.Find(7) << endl;cout << ht.Find(8) << endl;
}void TestHT2()
{string arr[] = { "蘋果", "西瓜", "香蕉", "草莓", "蘋果", "西瓜", "蘋果", "蘋果", "西瓜", "蘋果", "香蕉", "蘋果", "香蕉" };//HashTable<string, int, HashFuncString> countHT;closeHash::HashTable<string, int> countHT;for (auto& e : arr){closeHash::HashData<string, int>* ret = countHT.Find(e);if (ret){ret->_kv.second++;}else{countHT.Insert(make_pair(e, 1));}}HashFunc<string> hf;cout << hf("abc") << endl;cout << hf("bac") << endl;cout << hf("cba") << endl;cout << hf("aad") << endl;
}
int main()
{//TestHT1();TestHT2();return 0;
}

8.二次探測

線性探測優(yōu)點：實現(xiàn)非常簡單，

線性探測缺點：一旦發(fā)生哈希沖突，所有的沖突連在一起，容易產(chǎn)生數(shù)據(jù)堆積”，即：不同關(guān)鍵碼占據(jù)了可利用的空位置，使得尋找某關(guān)鍵碼的位置需要許多次比較，導(dǎo)致搜索效率降低。如何緩解呢？

線性探測的缺陷是產(chǎn)生沖突的數(shù)據(jù)堆積在一塊，這與其找下一個空位置有關(guān)系，因為找空位置的方式就是挨著往后逐個去找，因此二次探測為了避免該問題，找下一個空位置的方法為：$H_i$ = ($H_0$ + $i^2$ )% m,或者：$H_i$ = ($H_0$ - $i^2$ )% m。其中：i =1,2,3…，$H_0$是通過散列函數(shù)Hash(x)對元素的關(guān)鍵碼key進行計算得到的位置，m是表的大小。即根據(jù)余數(shù)找到下標位置，如果位置被占用，不是去挨著的下一個位置找，而是去余數(shù)+i的平方的位置找插入位置，其中i是尋找的次數(shù)

研究表明：當(dāng)表的長度為質(zhì)數(shù)且表裝載因子a不超過0.5時，新的表項一定能夠插入，而且任何一個位置都不會被探查兩次。因此只要表中有一半的空位置，就不會存在表滿的問題。在搜索時可以不考慮表裝滿的情況，但在插入時必須確保表的裝載因子a不超過0.5，如果超出必須考慮增容

比散列最大的缺陷就是空間利用率比較低，這也是哈希的缺陷.最后二次探測法在一定程度上減輕了哈希沖突的概率，但也沒有從根源上解決問題。

三、開散列

1.開散列概念

開散列法又叫鏈地址法(開鏈法)，首先對關(guān)鍵碼集合用散列函數(shù)計算散列地址，具有相同地址的關(guān)鍵碼歸于同一子集合，每一個子集合稱為一個桶，各個桶中的元素通過一個單鏈表鏈接起來，各鏈表的頭結(jié)點存儲在哈希表中。

即在發(fā)生哈希沖突的時候，把key作為一個節(jié)點直接鏈接在對應(yīng)下面位置的哈希桶

從上圖可以看出，開散列中每個桶中放的都是發(fā)生哈希沖突的元素。

2.開散列的節(jié)點結(jié)構(gòu)

由于開散列的不同沖突的元素之間不會相互影響，所以開散列不再需要status變量來記錄每一個下面位置的狀態(tài)，此外開散列的每個下標位置鏈接的都是一個哈希桶，所以vector中的每一個元素都是一個節(jié)點的指針，指向單鏈表中的第一個元素，所以_tables是一個指針數(shù)組，這樣就不會去占用別人的位置，所以不管在插入還是查找方面，開散列都要比閉散列要更加的高效，所以C++STL中的unordered_set和unordered_map以及Java中的HashSet和HashMap的底層都是使用哈希表的開散列方式實現(xiàn)的。最后，為了使得不同類型的key都能夠計算出其映射的下標位置，所以我們需要傳遞一個仿函數(shù)：

// 仿函數(shù)
template<class K>
struct HashFunc
{size_t operator()(const K& key){return (size_t)key;}
};// 特化 --針對string類型寫一個仿函數(shù)--轉(zhuǎn)成整形
template<>
struct HashFunc<string>
{size_t operator()(const string& key){size_t hash = 0;for (auto ch : key){hash *= 131;hash += ch;}return hash;}
};
// 哈希表達節(jié)點結(jié)構(gòu)--單鏈表
template<class K, class V>
struct HashNode
{pair<K, V> _kv;HashNode<K, V>* _next;HashNode(const pair<K, V>& kv):_kv(kv), _next(nullptr){}
};// 哈希表
template<class K, class V, class Hash=HashFunc<K>>
class HashTable
{typedef HashNode<K, V> Node;
private:vector<Node*> _tables; //指針數(shù)組size_t _n;// 表中有效數(shù)據(jù)的個數(shù)
};

3.開散列的操作

1.開散列的插入

開散列插入和閉散列一樣，首先需要根據(jù)key值與哈希表的大小得到映射的下標的位置，此外，由于哈希表中每個下標位置都是一個哈希桶，即一個單鏈表，那么我們插入的時候只需要將沖突的元素鏈接到哈希桶中即可。這里鏈接有兩種方式：

1.將發(fā)生哈希沖突的元素鏈接到單鏈表的末尾，即尾插

2.將發(fā)生哈希沖突的元素鏈接到單鏈表的頭部，即頭插

但是由于單鏈表尾插需要從頭結(jié)點開始遍歷進行找尾，這樣插入的效率就比較低，所以我們選擇頭插的方式

插入部分代碼如下：

bool Insert(const pair<K, V>& kv)
{if (Find(kv.first))return false;//調(diào)用仿函數(shù)的匿名對象將key轉(zhuǎn)換為整數(shù)size_t hashi = Hash()(kv.first) % _tables.size();// 頭插Node* newnode = new Node(kv);newnode->_next = _tables[hashi];_tables[hashi] = newnode;++_n;return true;
}

2.開散列的查找

開散列的查找只需要根據(jù)取模得到下標，由于下標位置存儲的是單鏈表首元素的地址，我們進行遍歷即可

Node* Find(const K& key)
{size_t hashi = Hash()(key) % _tables.size();Node* cur = _tables[hashi];while (cur){if (cur->_kv.first == key){return cur;}else{cur = cur->_next;}}return nullptr;
}

3.開散列的刪除

和閉散列不同的是，開散列的刪除不能直接通過查找函數(shù)的返回值進行刪除，因為單鏈表在刪除節(jié)點時還需要改變父節(jié)點的指向，讓其指向下一個節(jié)點，和單鏈表的刪除相同，所以我們需要遍歷單鏈表找到刪除的節(jié)點進行刪除

bool Erase(const K& key)
{// 通過哈希映射站到下標位置size_t hashi = Hash()(key) % _tables.size();Node* prev = nullptr;Node* cur = _tables[hashi];while (cur){if (cur->_kv.first == key){// 頭刪//if (prev == nullptr)if(cur == _tables[hashi]){//_tables[hashi] = nullptr;_tables[hashi] = cur->_next;}else{prev->_next = cur->_next;}delete cur;--_n;return true;}else{cur = cur->_next;prev = cur;}}return false;
}

4.開散列的擴容

桶的個數(shù)是一定的，隨著元素的不斷插入，每個桶中元素的個數(shù)不斷增多，極端情況下，可能會導(dǎo)致一個桶中鏈表節(jié)點非常多，會影響的哈希表的性能，因此在一定條件下需要對哈希表進行增容，那該條件怎么確認呢？開散列最好的情況是：每個哈希桶中剛好掛一個節(jié)點，再繼續(xù)插入元素時，每一次都會發(fā)生哈希沖突，因此，在元素個數(shù)剛好等于桶的個數(shù)時，可以給哈希表增容。

開散列最好的情況是每一個哈希桶中都只有一個元素，再繼續(xù)插入元素的時候，每一次就會發(fā)生哈希沖突，因此，我們可以在元素的個數(shù)等于桶的個數(shù)的時候進行擴容，即負載因子為1

這樣我們可以采用兩種擴容的方式:

1.采用閉散列擴容的思路-通過復(fù)用insert函數(shù)來進行擴容，但是開散列每個插入的時候都需要新開辟節(jié)點，在插入完畢之后，我們還需要釋放表中原來的節(jié)點，這樣就會使得效率很低

2.我們可以創(chuàng)建一個vector，取出舊表中的每一個節(jié)點鏈接到新的表中，然后再交換舊表和新表，這樣就沒有開辟節(jié)點和釋放節(jié)點的消耗了，從而大大提高了擴容的效率。注：我們不能直接將原表中的整個哈希桶鏈接到新表中，因為新表的大小改變后原表中的元素可能會映射到表的其他位置

所以開散列的析構(gòu)函數(shù)需要我們自己實現(xiàn)，因為默認生成的析構(gòu)函數(shù)不會釋放掉哈希桶

我們每次擴容不一定都在擴容2倍，有人提出了表的大小為質(zhì)數(shù) 的時候哈希沖突的概率會低一些，當(dāng)使用質(zhì)數(shù)作為除數(shù)時，能夠更加均勻地散列key值，就會較少哈希沖突的發(fā)生。庫中可以這樣實現(xiàn)的，但是也不是必須的，所以我們這里使用一個數(shù)組，保存一組質(zhì)數(shù)，大概是2倍的關(guān)系，但是在42億之后就不會再進行擴容了，其實我們也不用擔(dān)心，因為我們整數(shù)的數(shù)據(jù)一共才42億，是可以存儲得下的。

但是在某一些極端場景下，或者面對某些碰撞攻擊時(對方知道我們好像表的長度以及取模的邏輯，這個時候就專門設(shè)計一些沖突的數(shù)據(jù)，使得效率就不變得很低)，那么機會導(dǎo)致單鏈表的長度過長，從而降低哈希的查找與刪除的效率。

為了應(yīng)對這種情況，Java 8中使用的HashMap在使用紅黑樹來優(yōu)化哈希沖突的情況，因為紅黑樹可以保證查找，插入和刪除的時間復(fù)雜度為O(logN)，效率就會比鏈表快很多，此外，C++11也引入了一個新的數(shù)據(jù)結(jié)構(gòu)–開發(fā)定址哈希表(open addressing table)，用于存儲哈希沖突時的元素，開放定址哈希表是一種不使用鏈表來解決哈希沖突的實現(xiàn)方式。這種實現(xiàn)方式中，如果一個槽(slot)已經(jīng)被占用了，就會嘗試找到下一個可用的槽，直達找到一個空槽，因為開發(fā)地址哈希表可以更好的利用緩沖，從而提高查找性能。C++11之后的版本中，unordered_map的哈希桶使用了兩種不同的數(shù)據(jù)結(jié)構(gòu)，包括單鏈表和開放定址哈希表–當(dāng)桶中元素較少時，使用鏈表，當(dāng)桶的元素較多的時候，會自動轉(zhuǎn)換為開放定址哈希表

STL源碼中的實現(xiàn)：

// Note: assumes long is at least 32 bits.
static const int __stl_num_primes = 28;
static const unsigned long __stl_prime_list[__stl_num_primes] =
{53,         97,         193,       389,       769,1543,       3079,       6151,      12289,     24593,49157,      98317,      196613,    393241,    786433,1572869,    3145739,    6291469,   12582917,  25165843,50331653,   100663319,  201326611, 402653189, 805306457, 1610612741, 3221225473, 4294967291
};inline unsigned long __stl_next_prime(unsigned long n)
{const unsigned long* first = __stl_prime_list;const unsigned long* last = __stl_prime_list + __stl_num_primes;const unsigned long* pos = lower_bound(first, last, n);return pos == last ? *(last - 1) : *pos;
}

擴容代碼如下：

// 負載因子控制在1，超過就擴容
if (_tables.size() == _n)
{ 創(chuàng)建一個哈希表對象，然后進行插入，之后交換雙方的vector//HashTable<K, V> newHT;//newHT._tables.resize(_tables.size() * 2);//for (size_t i = 0; i < _tables.size(); ++i)//{//	Node* cur = _tables[i];//	while (cur)//	{//		newHT.Insert(cur->_kv);//		cur = cur->_next;//	}//}//_tables.swap(newHT._tables);vector<Node*> newTables;//newTables.resize(_tables.size() * 2, nullptr);newTables.resize(__stl_next_prime(_tables.size()), nullptr);for (size_t i = 0; i < _tables.size(); ++i){Node* cur = _tables[i];while (cur){// 保存下一個節(jié)點Node* next = cur->_next;size_t hashi = Hash()(cur->_kv.first) % newTables.size();//進行頭插cur->_next = newTables[i];newTables[i] = cur;cur = next;}_tables[i] = nullptr;}_tables.swap(newTables);
}

5.開散列完整代碼實現(xiàn)

namespace buckethash
{template<class K, class V>struct HashNode{pair<K, V> _kv;HashNode<K, V>* _next;HashNode(const pair<K, V>& kv):_kv(kv), _next(nullptr){}};template<class K, class V, class Hash=HashFunc<K>>class HashTable{typedef HashNode<K, V> Node;public:// 構(gòu)造HashTable():_n(0){_tables.resize(__stl_next_prime(0));}// 析構(gòu)~HashTable(){for (size_t i = 0; i < _tables.size(); ++i){Node* cur = _tables[i];while (cur){Node* next = cur->_next;delete cur;cur = next;}_tables[i] = nullptr;}}bool Insert(const pair<K, V>& kv){if (Find(kv.first))return false;// 負載因子控制在1，超過就擴容if (_tables.size() == _n){ 創(chuàng)建一個哈希表對象，然后進行插入，之后交換雙方的vector//HashTable<K, V> newHT;//newHT._tables.resize(_tables.size() * 2);//for (size_t i = 0; i < _tables.size(); ++i)//{//	Node* cur = _tables[i];//	while (cur)//	{//		newHT.Insert(cur->_kv);//		cur = cur->_next;//	}//}//_tables.swap(newHT._tables);vector<Node*> newTables;//newTables.resize(_tables.size() * 2, nullptr);newTables.resize(__stl_next_prime(_tables.size()), nullptr);for (size_t i = 0; i < _tables.size(); ++i){Node* cur = _tables[i];while (cur){// 保存下一個節(jié)點Node* next = cur->_next;size_t hashi = Hash()(cur->_kv.first) % newTables.size();//進行頭插cur->_next = newTables[i];newTables[i] = cur;cur = next;}_tables[i] = nullptr;}_tables.swap(newTables);}size_t hashi = Hash()(kv.first) % _tables.size();// 頭插Node* newnode = new Node(kv);newnode->_next = _tables[hashi];_tables[hashi] = newnode;++_n;return true;}Node* Find(const K& key){size_t hashi = Hash()(key) % _tables.size();Node* cur = _tables[hashi];while (cur){if (cur->_kv.first == key){return cur;}else{cur = cur->_next;}}return nullptr;}bool Erase(const K& key){size_t hashi = Hash()(key) % _tables.size();Node* prev = nullptr;Node* cur = _tables[hashi];while (cur){if (cur->_kv.first == key){// 頭刪//if (prev == nullptr)if(cur == _tables[hashi]){//_tables[hashi] = nullptr;_tables[hashi] = cur->_next;}else{prev->_next = cur->_next;}delete cur;--_n;return true;}else{cur = cur->_next;prev = cur;}}return false;}inline unsigned long __stl_next_prime(unsigned long n){static const int __stl_num_primes = 28;static const unsigned long __stl_prime_list[__stl_num_primes] ={53, 97, 193, 389, 769,1543, 3079, 6151, 12289, 24593,49157, 98317, 196613, 393241, 786433,1572869, 3145739, 6291469, 12582917, 25165843,50331653, 100663319, 201326611, 402653189, 805306457,1610612741, 3221225473, 4294967291};for (int i = 0; i < __stl_num_primes; ++i){if (__stl_prime_list[i] > _n){return __stl_prime_list[i];}}return __stl_prime_list[__stl_num_primes - 1];}private:vector<Node*> _tables;size_t _n;};
}

6.開散列與閉散列比較

應(yīng)用鏈地址法處理溢出，需要增設(shè)鏈接指針，似乎增加了存儲開銷。事實上：由于開地址法必須保持大量的空閑空間以確保搜索效率，如二次探查法要求裝載因子a <=0.7，而表項所占空間又比指針大的多，所以使用鏈地址法反而比開地址法節(jié)省存儲空間。