哈希（hash，中文：散列；音譯：哈希），是一種算法思想，又稱散列算法、哈希函數(shù)、散列函數(shù)等。哈希函數(shù)能指導(dǎo)任何一種數(shù)據(jù)，構(gòu)造出一種儲(chǔ)存結(jié)構(gòu)，這種儲(chǔ)存結(jié)構(gòu)能夠通過某種函數(shù)使得元素的儲(chǔ)存位置和數(shù)據(jù)本身的值（一般稱之為key值）能夠建立一種映射關(guān)系，這樣在查找數(shù)據(jù)時(shí)就可以通過同一個(gè)哈希函數(shù)通過key值迅速找到元素的位置。
創(chuàng)新互聯(lián)主營(yíng)隴南網(wǎng)站建設(shè)的網(wǎng)絡(luò)公司,主營(yíng)網(wǎng)站建設(shè)方案,重慶APP開發(fā)公司,隴南h5小程序設(shè)計(jì)搭建,隴南網(wǎng)站營(yíng)銷推廣歡迎隴南等地區(qū)企業(yè)咨詢這種查找思想類似于數(shù)組的隨機(jī)訪問，它的時(shí)間復(fù)雜度為 O ( 1 ) O(1) O(1)。不同于以往，即便是紅黑樹，它的查找時(shí)間復(fù)雜度也是 O ( l o g 2 N ) ) O(log_2N)) O(log2?N))。原因是不論是順序結(jié)構(gòu)還是平衡樹中，元素的key值和儲(chǔ)存之間沒有映射關(guān)系，因此在查找元素時(shí)必須以key值進(jìn)行若干次比較，而這恰恰增加了時(shí)間復(fù)雜度。
map和set底層都是用二叉搜索樹實(shí)現(xiàn)的，因而他們都是有序的。而unordered_set和unorder_map中的元素都是無序的，原因是它們底層都使用了哈希思想實(shí)現(xiàn)。前者能使用雙向迭代器，后者是單向迭代器。
這樣看，前者更占優(yōu)勢(shì)，但為什么還有有unordered（無序）。因?yàn)楹笳叩讓邮褂昧斯Ｋ惴▽?shí)現(xiàn)，所以使用這種容器查找數(shù)據(jù)的效率最高，時(shí)間復(fù)雜度是 O ( 1 ) O(1) O(1)，雖然后者的插入效率略低，但仍然能夠持平。
在了解unordered_set和unorder_map容器之前，需要對(duì)哈希思想有一定了解。
從哈希查找的效率可以知道，哈希專攻的是查找功能。
1.2 例子生活中也有不少直接或間接使用哈希思想的例子，比如：
因?yàn)橛羞@樣的需求，一種新的數(shù)據(jù)結(jié)構(gòu)誕生了：散列表。
散列表（hash table）也叫做哈希表，它提供了鍵（key）和值（value）之間的映射關(guān)系，只要給出一個(gè)key，就能迅速找到對(duì)應(yīng)的value，時(shí)間復(fù)雜度接近 O ( 1 ) O(1) O(1)。
在列舉出來的例子中，大多數(shù)元素的key值都是以字符串的形式存儲(chǔ)的，那么如何用一個(gè)哈希函數(shù)將字符串轉(zhuǎn)化為一個(gè)整型的數(shù)組下標(biāo)值呢？
1.3 散列表的基本原理 1.3.1 哈希函數(shù)哈希表的本質(zhì)就是數(shù)組，使用哈希函數(shù)算出來的每個(gè)元素對(duì)應(yīng)的位置都是數(shù)組的下標(biāo)。這就是哈希函數(shù)保證查找元素的時(shí)間復(fù)雜度如此低的主要原因。
在不同的語(yǔ)言中，哈希函數(shù)的實(shí)現(xiàn)都有所區(qū)別。最簡(jiǎn)單的哈希函數(shù)實(shí)現(xiàn)方式是按數(shù)組長(zhǎng)度取模運(yùn)算：
為了演示方便，key值本身就是整型值，在后文中會(huì)介紹將字符串轉(zhuǎn)化為整型值的哈希函數(shù)：
h
a
s
h
(
k
e
y
)
=
k
e
y
?
%
?
c
a
p
a
c
i
t
y
hash(key) = key \ \% \ capacity
hash(key)=key?%?capacity
例如，對(duì)于集合中元素：{0, 3, 15, 8, 12}，它們存儲(chǔ)在數(shù)組長(zhǎng)度為10的哈希表中的位置如上。
1.3.2 哈希表的讀寫操作從這樣的表述中大概可以猜到，要想讓查找效率時(shí)間復(fù)雜度達(dá)到 O ( 1 ) O(1) O(1)，就必須使用數(shù)組存放數(shù)據(jù)，才能實(shí)現(xiàn)隨機(jī)訪問的效果。
根據(jù)key值用哈希函數(shù)算出來的存儲(chǔ)位置就是數(shù)組的下標(biāo)，
這種查找和插入的過程是類似的，都是先用（要存放的元素或要查找的元素的）key值計(jì)算處它的存儲(chǔ)位置，然后存放或取出該元素。
當(dāng)查找元素時(shí)，只需要通過key值使用同一個(gè)哈希函數(shù)即可直接找到元素對(duì)應(yīng)的位置，查找效率堪比數(shù)組。
為什么說「堪比」呢？
如上面的例子中，如果集合中多了幾個(gè)這樣的元素：
現(xiàn)在，新增的元素經(jīng)過同一個(gè)哈希函數(shù)得到的數(shù)組下標(biāo)值都已經(jīng)被占有了，像這種不同的值映射到同一位置的情況，就叫做哈希沖突。
造成哈希沖突的原因之一是：哈希函數(shù)的設(shè)計(jì)不合理。
哈希函數(shù)的設(shè)計(jì)原則：
哈希沖突是無法避免的，解決哈希沖突的方法主要有兩種，一種是開放尋址法，一種是鏈表法。
1.4.1 開放尋址法閉散列，也叫開放定址法，當(dāng)發(fā)生哈希沖突時(shí)，可以將元素放在被占的元素的下一個(gè)不為空的位置，以此類推，直到放滿哈希表為止。
開放尋址法根據(jù)“開放”的程度不同，分為兩種：
H i = ( H 0 ? + ? i ) ? % ? c a p ? , ( i = 1 , 2 , 3 , . . . ) H_i = (H_0 \ + \ i)\ \% \ cap \ ,(i = 1, 2, 3,...) Hi?=(H0??+?i)?%?cap?,(i=1,2,3,...)
其中：
同樣，以上面的例子而言：
思路簡(jiǎn)單，容易實(shí)現(xiàn)。
缺陷像這樣按數(shù)組長(zhǎng)度取模運(yùn)算的哈希函數(shù)，我們把它叫做除留余數(shù)法（下文還會(huì)介紹若干常見哈希函數(shù)）。隨著哈希表中數(shù)據(jù)的增多，發(fā)生哈希沖突的次數(shù)也會(huì)增加，且不限于key值相同與否，上圖中的示例中兩個(gè)key值僅沖突了一次。如果再插入key值=20的元素，就要發(fā)生6次哈希沖突。
隨著元素個(gè)數(shù)的增多，插入元素發(fā)生哈希沖突的可能性越大，查找的效率也會(huì)隨之變低。
從宏觀看，發(fā)生線性沖突的主要原因就是因?yàn)椴迦朐氐姆植疾痪鶆?，根?jù)key值通過哈希函數(shù)算出來的下標(biāo)值總是集中在某些區(qū)域。那么線性探測(cè)就像“違章建筑”，各自侵占別的哈希值的位置。
分布不均造成的“違章建筑”，從數(shù)組的容量利用率來看，就是插入的元素太“滿”了才會(huì)把別的元素?cái)D到其他地方，進(jìn)而產(chǎn)生鏈?zhǔn)椒磻?yīng)。所以可以限制插入元素的個(gè)數(shù)，減少不同的集中區(qū)域之間交叉的可能性。
負(fù)載因子負(fù) 載 因 子 ? = ? 有 效 數(shù) 據(jù) 個(gè) 數(shù) ? / ? 數(shù) 組 長(zhǎng) 度 負(fù)載因子\ = \ 有效數(shù)據(jù)個(gè)數(shù)\ / \ 數(shù)組長(zhǎng)度 負(fù)載因子?=?有效數(shù)據(jù)個(gè)數(shù)?/?數(shù)組長(zhǎng)度
改變負(fù)載因子有兩方面，有效數(shù)據(jù)個(gè)數(shù)（分子）和數(shù)組長(zhǎng)度（分母），由于數(shù)據(jù)個(gè)數(shù)無法限制，那么我們可以通過改變數(shù)組長(zhǎng)度進(jìn)而改變負(fù)載因子。
同樣地，將上面例子中數(shù)組的大小增加到20：
當(dāng)增加數(shù)組長(zhǎng)度時(shí)，上面的同一組數(shù)據(jù)中，不論是未發(fā)生還是發(fā)生沖突的，都更均勻地分散在數(shù)組中。
負(fù)載因子的表達(dá)式說明負(fù)載因子其實(shí)就是空間利用率，負(fù)載因子越小，空間利用率越低。
一般而言，對(duì)于開放定址法，負(fù)載因子一般控制在[0.7, 0.8]，超過0.8就會(huì)導(dǎo)致在查找時(shí)的效率呈指數(shù)級(jí)下降。
原因是CPU緩存不命中率(cache missing)會(huì)呈指數(shù)級(jí)上升。
鏈接：淺談 Cache
簡(jiǎn)言之，根據(jù)局部性原理，CPU下次訪問的數(shù)據(jù)很可能在上次訪問的數(shù)據(jù)的周圍。
所以，使用數(shù)組實(shí)現(xiàn)線性探測(cè)時(shí)，控制擴(kuò)容與否的主要因素已經(jīng)不再是它是否已滿，而是負(fù)載因子是否超出范圍。負(fù)載因子的存在，會(huì)讓哈希表永遠(yuǎn)不會(huì)滿。
二次探測(cè)線性探測(cè)的缺點(diǎn)就是容易因?yàn)楣Ｖ颠^于密集而出現(xiàn)“違章建筑”，出現(xiàn)鏈?zhǔn)椒磻?yīng)，一堆影響另一堆。雖提供了可行的方案，使用負(fù)載因子控制容量，但是它的應(yīng)用場(chǎng)景也是有限的。
而二次探測(cè)是在線性探測(cè)的基礎(chǔ)上而言的：
H
i
=
(
H
0
?
+
?
i
2
)
??
%
?
c
a
p
,
?
(
i
=
1
,
2
,
3
,
.
.
.
)
H_i= (H_0\ +\ i ^2) \ \ \% \ cap ,\ (i = 1,2,3,...)
Hi?=(H0??+?i2)??%?cap,?(i=1,2,3,...)
其中：
如果 j = i 2 j = i^2 j=i2即
H i = ( H 0 ? + ? j ) ?? % ? c a p , ? ( j = 1 , 4 , 9 , . . . ) H_i= (H_0\ +\ j) \ \ \% \ cap ,\ (j = 1,4,9,...) Hi?=(H0??+?j)??%?cap,?(j=1,4,9,...)
用一個(gè)例子理解：
理解二次探測(cè)的過程，最重要的是理解i的含義，遇到幾次沖突，i就是幾。
優(yōu)點(diǎn)二次探測(cè)是對(duì)線性探測(cè)的優(yōu)化，它對(duì)元素的分散程度大于線性探測(cè)中控制負(fù)載因子帶來的效果更好，畢竟是平方運(yùn)算，當(dāng)沖突次數(shù)越多，存放的位置也會(huì)離第一個(gè)沖突的位置越遠(yuǎn)，也就越分散。
缺陷由于二次探測(cè)是線性探測(cè)的優(yōu)化，所以它也需要用負(fù)載因子控制哈希表的容量。
總地來說，開放尋址法（閉散列）大的缺陷就是空間利用率較低，這同時(shí)也是哈希的缺陷，即使不采用上述優(yōu)化，這種處理方式也會(huì)浪費(fèi)一些空間。
1.4.2 鏈表法閉散列，也叫鏈表法、鏈地址法、拉鏈法。將同一個(gè)哈希值對(duì)應(yīng)的不同的key值視為一個(gè)集合，用一個(gè)鏈表保存起來，把它叫做哈希桶。即每個(gè)哈希桶存放的都是哈希值相同的不同key值，每個(gè)哈希桶（鏈表）的首地址會(huì)被保存在哈希表（數(shù)組）中，下標(biāo)對(duì)應(yīng)的就是哈希桶的哈希值。
插入元素時(shí)，只需要根據(jù)key值通過哈希函數(shù)得出的下標(biāo)找到對(duì)應(yīng)的鏈表（哈希桶），依次往后鏈接即可。
用例子理解哈希桶組成的哈希表：
將數(shù)組橫著放，鏈表豎著放，這樣就能理解為什么把這個(gè)存儲(chǔ)相同哈希值的不同key值的鏈表叫做哈希桶了。
優(yōu)點(diǎn)一個(gè)題外話：
學(xué)到這里突然明白了為什么要有鏈表的存在，因?yàn)樗芙鉀Q像這樣的哈希沖突問題，非常巧妙。
這也是數(shù)據(jù)結(jié)構(gòu)存在的意義，Data Structure，就是用來存取數(shù)據(jù)的結(jié)構(gòu)。例如在Linux操作系統(tǒng)中，一切皆文件，要對(duì)文件管理就必須先描述它們之間的關(guān)系，然后用統(tǒng)一的方法組織，這樣才能對(duì)文件管理。
不會(huì)產(chǎn)生數(shù)據(jù)之間的鏈?zhǔn)椒磻?yīng)，不同哈希值對(duì)應(yīng)的key值不會(huì)互相侵占位置。所以負(fù)載因子的存在只會(huì)降低空間利用率，所以開散列的負(fù)載因子可以超過1，一般控制在1以下。
極端情況：
全部元素的key值對(duì)應(yīng)的哈希值都相同，它們都發(fā)生哈希沖突，全部都鏈接到同一個(gè)哈希桶中：
這樣查找的效率退化為 O ( N ) O(N) O(N)，在此之前，我們學(xué)過的最高效的查找結(jié)構(gòu)就是紅黑樹，可以將鏈表?yè)Q成紅黑樹。時(shí)間復(fù)雜度就提升到 O ( l o g 2 N ) O(log_2N) O(log2?N)。
在Java常用的HashMap中，當(dāng)一個(gè)桶中元素個(gè)數(shù)超過8時(shí)，就會(huì)將鏈表?yè)Q成紅黑樹。當(dāng)少于8時(shí)，依然會(huì)使用鏈表存儲(chǔ)數(shù)據(jù)。但這不是必須的，因?yàn)橛械臅r(shí)候哈希表中負(fù)載因子也會(huì)增大，最終會(huì)使哈希表擴(kuò)容，哈希沖突次數(shù)減少，一個(gè)桶中元素的個(gè)數(shù)也會(huì)減少。
2. 實(shí)現(xiàn)閉散列哈希表實(shí)現(xiàn)閉散列哈希表，其實(shí)就是控制數(shù)組下標(biāo)對(duì)元素進(jìn)行增刪查改操作。
2.1 哈希表存儲(chǔ)結(jié)構(gòu)閉散列的查找有個(gè)坑，如果出現(xiàn)這種情況：
所以可以用枚舉常量規(guī)定每個(gè)位置的狀態(tài)：
重慶分公司
重慶分公司
// 枚舉常量表示位置狀態(tài)
enum State
{EMPTY,
EXIST,
DELETE
};用枚舉常量標(biāo)識(shí)狀態(tài)時(shí)可行的，原因是如果按照原來的思路，通常會(huì)將未存放的位置的值置為-1等，但假如要放入的元素key值本來就為-1呢？
每個(gè)位置有三種情況，即已被占有（EXIST）、已被刪除（DELETE）、未被占有（EMPTY）。之所以要設(shè)置為DELETE，就是為了避免上面的坑。
單位存儲(chǔ)結(jié)構(gòu)那么，哈希表中每個(gè)位置都應(yīng)該包含位置的狀態(tài)和數(shù)據(jù)：
// 哈希表中每個(gè)位置的存儲(chǔ)結(jié)構(gòu)
templatestruct HashData
{pair_kv;
State _state = EMPTY;
}; 由于哈希是由key值計(jì)算的數(shù)組下標(biāo)，存的是元素的value值，所以每個(gè)元素存儲(chǔ)的是一個(gè)鍵值對(duì)，可以用pair結(jié)構(gòu)體保存。
當(dāng)創(chuàng)建出一個(gè)位置時(shí)，它的默認(rèn)狀態(tài)是空，所以給_state以缺省值EMPTY。
哈希表對(duì)于整個(gè)哈希表(HashTable)而言，其本質(zhì)是一個(gè)數(shù)組，因?yàn)殚]散列的優(yōu)化中會(huì)使用負(fù)載因子控制數(shù)組長(zhǎng)度，所以需要一個(gè)動(dòng)態(tài)長(zhǎng)度的數(shù)組，在此，我們直接使用STL中的vector容器，它的每個(gè)元素的類型都是HashData。
templateclass HashTable
{public:
// ...
private:
vector>_table; // 哈希表
size_t _n = 0; // 負(fù)載因子
}; 注意，數(shù)組元素的類型只是每個(gè)位置的類型，因?yàn)槊總€(gè)位置要包含狀態(tài)和數(shù)據(jù)，所以它不僅僅是一個(gè)下標(biāo)指定的位置。
key值轉(zhuǎn)整型在本文開頭介紹哈希函數(shù)時(shí)，說到key值是要轉(zhuǎn)為整型才能對(duì)數(shù)組長(zhǎng)度取模運(yùn)算的，上文中都是以整型的key值為例，所以并未提到key值轉(zhuǎn)整型的例子。由于現(xiàn)實(shí)中key值還可能是字符串等類型，所以可以使用仿函數(shù)+模板特化的方式來匹配不同類型的key值轉(zhuǎn)化為整型值。
直接轉(zhuǎn)整型當(dāng)key值本身是整型時(shí)，只需要返回強(qiáng)轉(zhuǎn)為size_t后的值即可。
size_t 類型定義在cstddef頭文件中，該文件是C標(biāo)準(zhǔn)庫(kù)的頭文件stddef.h的C++版。 它是一個(gè)與機(jī)器相關(guān)的unsigned類型，其大小足以保證存儲(chǔ)內(nèi)存中對(duì)象的大小。 --來源于網(wǎng)絡(luò)
至于為什么要轉(zhuǎn)化成unsigned類型，是因?yàn)楫?dāng)%取模運(yùn)算操作符的右邊為負(fù)數(shù)時(shí)，本身就會(huì)發(fā)生隱式類型轉(zhuǎn)換，將負(fù)數(shù)轉(zhuǎn)換為正數(shù)。
如：
-17 % 10 = -7
17 % -10 = 7
-17 % -10 = -7
// 仿函數(shù)
templatestruct HashFunc
{size_t operator()(const K& key)
{return (size_t)key;
}
}; 同時(shí)，哈希表的類中也要增加一個(gè)模板參數(shù)，以將key值轉(zhuǎn)化為整型值：
template>class HashTable
{// ...
} 將key值轉(zhuǎn)化函數(shù)的缺省值設(shè)置為HashFunc。
字符串轉(zhuǎn)整型許多場(chǎng)景中，key值都是字符串類型的，將字符串轉(zhuǎn)化為整型值有很多辦法，比如首字符ASCII值，但是這樣哈希沖突的概率太大了。字符串作為一種經(jīng)常被使用的類型，有許多大佬都對(duì)字符串轉(zhuǎn)整型的哈希函數(shù)有自己的見解，其主流思想是：
BKDRHash算法：
這是是Kernighan和Dennis在《The C programming language》中提出的，它對(duì)每次累加后的結(jié)果再乘以素?cái)?shù)131。
至于為什么是素?cái)?shù)131，這是個(gè)數(shù)學(xué)問題，眾所周知計(jì)算機(jī)科學(xué)家都是數(shù)學(xué)家。
因?yàn)槲覀冎耙呀?jīng)實(shí)現(xiàn)了整型本身轉(zhuǎn)整型的仿函數(shù)，所以如果想要讓別的類型轉(zhuǎn)化為整型，需要用到模板的特化：
// BKDRHash算法
template<>struct HashFunc{size_t operator()(const string& key)
{size_t ret = 0;
for(auto& e : key)
{ret *= 131;
ret += e;
}
return ret;
}
}; // 查找函數(shù)
HashData* Find(const K& key)
{if (_table.size() == 0)
{return nullptr;
}
Hash hash;
size_t size = _table.size();
size_t start = hash(key) % size; // 根據(jù)key值通過哈希函數(shù)得到下標(biāo)值
size_t hashi = start;
while (_table[hashi]._state != EMPTY)
{if (_table[hashi]._state != DELETE && _table[hashi]._kv.first == key)
{return &_table[hashi];
}
hashi++;
hashi %= size;
if (hashi == start)
{break;
}
}
return nullptr;
} 因?yàn)閿U(kuò)容改變了數(shù)組的長(zhǎng)度，哈希函數(shù)也隨之變化，每個(gè)元素的位置都有可能改變。
更新哈希表的步驟bool Insert(const pairkv)
{if (Find(kv.first) != nullptr) // 哈希表中已存在相同key值的元素
{return false;
}
// 擴(kuò)容操作
if (_table.size() == 0 || _size * 10 / _table.size() >= 7) // 擴(kuò)容
{size_t newSize = _table.size() == 0 ? 10 : _table.size() * 2;
HashTablenewHashTable; // 創(chuàng)建新哈希表
newHashTable._table.resize(newSize); // 擴(kuò)容
for (auto& e : _table) // 遍歷原哈希表
{if (e._state == EXIST)
{newHashTable.Insert(e._kv); // 映射到新哈希表
}
}
_table.swap(newHashTable._table);
}
// 插入操作
Hash hash;
size_t size = _table.size();
size_t hashi = hash(kv.first) % size; // 得到key值對(duì)應(yīng)的哈希值
while (_table[hashi]._state == EXIST) // 線性探測(cè)
{int i = 0;
i++;
hashi = (hashi + i) % size;
}
// 探測(cè)到空位置，下標(biāo)是hashi
_table[hashi]._kv = kv; // 插入元素，更新位置上的kv值
_table[hashi]._state = EXIST; // 更新位置的狀態(tài)
++_size; // 更新有效元素個(gè)數(shù)
return true;
} 刪除一個(gè)元素只需要將該位置的狀態(tài)改成DELETE即可。
// 刪除函數(shù)
bool Erase(const K& key)
{HashData* find = Find(key);
if(find != nullptr)
{find->_state = DELETE;
_size--;
return true;
}
return false;
} 開頭介紹的鏈表法，哈希表（數(shù)組）的每一個(gè)位置存儲(chǔ)的都是一個(gè)鏈表的頭結(jié)點(diǎn)地址。每個(gè)哈希桶存儲(chǔ)的數(shù)據(jù)都是一個(gè)結(jié)點(diǎn)類型，這個(gè)結(jié)點(diǎn)類就是鏈表中的結(jié)點(diǎn)。
結(jié)點(diǎn)類templatestruct HashNode
{pair_kv; // 鍵值對(duì)
HashNode* _next; // 后繼指針
// 結(jié)點(diǎn)構(gòu)造函數(shù)
HashNode(const pairkv)
:_kv(kv)
, _next(nullptr)
{}
}; 由于模板參數(shù)和命名的繁雜，為了代碼的可讀性，可以將結(jié)點(diǎn)類typedef為Node：
typedef HashNodeNode; 哈希表底層一個(gè)動(dòng)態(tài)長(zhǎng)度的數(shù)組，同樣地，使用STL的vector做為哈希表。數(shù)組中的每個(gè)元素類型都是Node*。
templateclass HashTable
{typedef HashNodeNode;
public:
// ...
private:
vector_table;
size_t _size = 0;
}; // 查找函數(shù)
HashNode* Find(const K& key)
{if(_table.size() == 0)
{return nullptr;
}
size_t pos = key % _table.size(); // 得到下標(biāo)值
HashNode* cur = _table[pos]; // 找到哈希桶首地址
while (cur) // 遍歷鏈表
{if (cur->_kv.first == key)
{return cur;
}
cur = cur->_next;
}
return nullptr;
} 步驟和閉散列哈希表的插入是類似的，不同的是開散列的負(fù)載因子是到1才會(huì)擴(kuò)容。
插入步驟因?yàn)閿U(kuò)容改變了數(shù)組的長(zhǎng)度，哈希函數(shù)也隨之變化，每個(gè)元素的位置都有可能改變。
更新哈希表的步驟當(dāng)擴(kuò)容需要將舊哈希表數(shù)據(jù)遷移到新哈希表中時(shí)，直接在遍歷的同時(shí)通過新的哈希函數(shù)計(jì)算出的下標(biāo)值鏈接到對(duì)應(yīng)的哈希桶（鏈表）即可。不復(fù)用Insert函數(shù)的原因是Insert函數(shù)會(huì)在其內(nèi)部new一個(gè)Node然后再插入，像這樣遷移數(shù)據(jù)的動(dòng)作不斷new和delete（函數(shù)結(jié)束會(huì)自動(dòng)delete釋放資源）的操作會(huì)帶來不必要的開銷。
哈希桶可以用任意鏈表實(shí)現(xiàn)，單雙鏈表皆可。但是在此為了代碼上的簡(jiǎn)單，使用了單鏈表，因?yàn)榇斯?jié)重點(diǎn)是學(xué)習(xí)哈希思想，鏈表應(yīng)該在之前就已經(jīng)掌握了。其次，對(duì)單鏈表的操作是頭插和頭刪。原因是不管是什么類型的鏈表，它的插入和查找的時(shí)間復(fù)雜度都是
O
(
N
)
O(N)
O(N)，這么做的目的是提高插入（主要）和刪除的效率。
// 插入函數(shù)
bool Insert(const pair& kv)
{if(Find(kv.first) != nullptr) // 元素已經(jīng)存在
{return false;
}
// 擴(kuò)容操作
if(_size == _table.size())
{size_t oldSize = _table.size();
size_t newSize = oldSize == 0 ? 10 : 2 * oldSize;
vectornewTable; // 建立新表
newTable.resize(newSize); // 擴(kuò)容
for(size_t i = 0; i< oldSize; i++) // 轉(zhuǎn)移數(shù)據(jù)
{Node* cur = _table[i]; // 下標(biāo)i對(duì)應(yīng)的鏈表的首地址
while(cur)
{Node* next = cur->_next;
size_t hashi = cur->_kv.first % newSize;// 新下標(biāo)值
cur->_next = newTable[hashi]; // 重新鏈接
newTable[hashi] = cur;
cur = next; // 鏈表向后迭代
}
_table[i] = nullptr;
}
_table.swap(newTable); // 替換新哈希表
}
// 頭插元素
size_t hashi = kv.first % _table.size();
Node* newnode = new Node(kv);
newnode->_next = _table[hashi];
_table[hashi] = newnode;
_size++;
return true;
} 由于哈希桶是由鏈表實(shí)現(xiàn)的，所以即使先用Find找到key值對(duì)應(yīng)的結(jié)點(diǎn)，刪除時(shí)依然要遍歷鏈表，因?yàn)閱捂湵淼膭h除需要知道它上一個(gè)結(jié)點(diǎn)的地址。
// 刪除函數(shù)
bool Erase(const K& key)
{size_t pos = key % _table.size(); // 得到key值對(duì)應(yīng)的哈希桶下標(biāo)
Node* prev = nullptr;
Node* cur = _table[pos];
while (cur)
{if(cur->_kv.first == key) // 找到和key值對(duì)應(yīng)的結(jié)點(diǎn)
{if (prev == nullptr) // 找到的結(jié)點(diǎn)在鏈表首部
{_table[pos] = cur->_next; // 直接將頭部往后移動(dòng)一個(gè)單位
}
else // 找到的結(jié)點(diǎn)不在鏈表首部
{prev->_next = cur->_next; // 直接跳過它即可
}
delete cur; // 釋放結(jié)點(diǎn)資源
_size--; // 更新計(jì)數(shù)器
return true;
}
prev = cur; // 迭代
cur = cur->_next;
}
return false;
}在本文的開頭介紹了一個(gè)哈希函數(shù)BKDRHash算法，它對(duì)每次累加后的結(jié)果再乘以素?cái)?shù)131。我想原理都是類似的，對(duì)于哈希思想，要想發(fā)揮它的優(yōu)勢(shì)，即查找，就必須揚(yáng)長(zhǎng)避短，避免哈希沖突。
這里有一篇文章和一個(gè)討論詳細(xì)介紹了哈希表的大小是素?cái)?shù)能減少哈希沖突的原因：哈希表的大小為何是素?cái)?shù)、Why is it best to use a prime number as a mod in a hashing function?
文中一開始例子中的數(shù)列，因子是數(shù)列元素之間的間隔。
總地來說，這是由模運(yùn)算這種運(yùn)算方式?jīng)Q定的：
A
?
%
?
B
A \ \% \ B
A?%?B
其中：
由于 A % B A\%B A%B的結(jié)果是 A / B A/B A/B的余數(shù)，這個(gè)余數(shù)就是哈希表的下標(biāo)，也是判斷哈希沖突的依據(jù)。當(dāng)A和B之間存在非1的公共因子時(shí)，它們會(huì)出現(xiàn)多次結(jié)果相同的情況（這就是產(chǎn)生哈希沖突的情況），假設(shè)其中一個(gè)相同的結(jié)果是C。
原因：
A總是能通過B乘以一個(gè)非負(fù)整數(shù)再加上C來表示，例如：A是4的倍數(shù)，B是8：
| A%B | 結(jié)果 |
|---|---|
| 4%8 | 4 |
| 8%8 | 0 |
| 12%8 | 4 |
| 16%8 | 0 |
| 20%8 | 4 |
對(duì)于A和B，用結(jié)果表示A：
| A | = | B | * | 非負(fù)整數(shù) | + | 結(jié)果 |
|---|---|---|---|---|---|---|
| 4 | = | 8 | * | 0 | + | 4 |
| 8 | = | 8 | * | 1 | + | 0 |
| 12 | = | 8 | * | 1 | + | 4 |
| 16 | = | 8 | * | 2 | + | 0 |
| 20 | = | 8 | * | 2 | + | 4 |
這個(gè)表格也是計(jì)算A%B的原理，出現(xiàn)相同的結(jié)果的原因就是A和B之間存在若干非1公共因子。想降低發(fā)生哈希沖突的概率，就是減少出現(xiàn)相同哈希值的次數(shù)，所以就要減少A和B的公共因子個(gè)數(shù)，由于每個(gè)數(shù)都有一個(gè)因子是1，所以使哈希表的長(zhǎng)度為素?cái)?shù)。
在stl_hashtable.h中，專門有一個(gè)數(shù)組保存了素?cái)?shù)，相鄰素?cái)?shù)之間相差一倍，每當(dāng)需要擴(kuò)容時(shí)，都從這個(gè)數(shù)組中找下一個(gè)素?cái)?shù)作為新哈希表的長(zhǎng)度。
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
};所以上面的擴(kuò)容操作中可以用這個(gè)素?cái)?shù)數(shù)組優(yōu)化。
// 獲取新哈希表素?cái)?shù)長(zhǎng)度
size_t GetNextPrime(size_t prime)
{const int PRIMECOUNT = 28;
size_t i = 0;
for (i = 0; i< PRIMECOUNT; i++)
{if (MyPrimeList[i] >prime)
return MyPrimeList[i];
}
return MyPrimeList[i];
}哈希函數(shù)除了上面常用的直接定址法和除留余數(shù)法以外，還有下面幾種常見的哈希函數(shù)：
平方取中法假設(shè)關(guān)鍵字為 1234，對(duì)它平方就是 1522756，抽取中間的 3 位 227 作為哈希地址。使用場(chǎng)景：不知道關(guān)鍵字的分布，而位數(shù)又不是很大的情況。
折疊法折疊法是將關(guān)鍵字從左到右分割成位數(shù)相等的幾部分（最后一部分位數(shù)可以短些），然后將這幾部分疊加求和，并按哈希表表長(zhǎng)，取后幾位作為哈希地址。
使用場(chǎng)景：折疊法適合事先不需要知道關(guān)鍵字的分布，或關(guān)鍵字位數(shù)比較多的情況。
隨機(jī)數(shù)法選擇一個(gè)隨機(jī)函數(shù)，取關(guān)鍵字的隨機(jī)函數(shù)值為它的哈希地址，即
H
a
s
h
(
K
e
y
)
=
r
a
n
d
o
m
(
K
e
y
)
Hash(Key)=random(Key)
Hash(Key)=random(Key)
其中：
使用場(chǎng)景：通常應(yīng)用于關(guān)鍵字長(zhǎng)度不等時(shí)。
數(shù)字分析法設(shè)有N個(gè)M位數(shù)，每一位可能有X種不同的符號(hào)，這X中不同的符號(hào)在各位上出現(xiàn)的頻率不一定相同，可能在某些位上分布比較均勻，每種符號(hào)出現(xiàn)的機(jī)會(huì)均等，而在某些位上分布不均勻，只有幾種符號(hào)經(jīng)常出現(xiàn)。此時(shí)，我們可根據(jù)哈希表的大小，選擇其中各種符號(hào)分布均勻的若干位作為哈希地址。
假設(shè)要存儲(chǔ)某家公司員工登記表，如果用手機(jī)號(hào)作為關(guān)鍵字，那么極有可能前7位都是相同的，那么我們可以選擇后面的四位作為哈希地址。
如果這樣的抽取方式還容易出現(xiàn)沖突，還可以對(duì)抽取出來的數(shù)字進(jìn)行反轉(zhuǎn)（如1234改成4321）、右環(huán)位移（如1234改成4123）、左環(huán)位移（如1234改成2341）、前兩數(shù)與后兩數(shù)疊加（如1234改成12+34=46）等操作。
數(shù)字分析法通常適合處理關(guān)鍵字位數(shù)比較大的情況，或事先知道關(guān)鍵字的分布且關(guān)鍵字的若干位分布較均勻的情況。
你是否還在尋找穩(wěn)定的海外服務(wù)器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機(jī)房具備T級(jí)流量清洗系統(tǒng)配攻擊溯源，準(zhǔn)確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級(jí)服務(wù)器適合批量采購(gòu)，新人活動(dòng)首月15元起，快前往官網(wǎng)查看詳情吧
