文章目錄

• 哈希
• 哈希（散列）函數(shù)
• • 常見的哈希函數(shù)
  • 字符串哈希函數(shù)
• 哈希沖突
• • 閉散列（開放地址法）
  • 開散列（鏈地址法/拉鏈法）
  • 負(fù)載因子以及增容
  • • 對于閉散列
  • 對于開散列結(jié)構(gòu)
• 具體實(shí)現(xiàn)
• • 哈希表（閉散列）
  • • 創(chuàng)建
    • 插入
    • 查找
    • 刪除
    • 完整代碼
  • 哈希桶（開散列）
  • • 插入
    • 查找
    • 刪除
    • 完整代碼

---

哈希

哈希（散列）是一種數(shù)據(jù)結(jié)構(gòu)，通過散列算法將元素值轉(zhuǎn)換為散列值進(jìn)行存儲。使得元素存儲的位置與元素本身建立起了映射關(guān)系，如果要查、改數(shù)據(jù)，就可以直接到對應(yīng)的位置去，使得時(shí)間復(fù)雜度達(dá)到了 O(1) ，原因如下：

若結(jié)構(gòu)中存在和 關(guān)鍵字K 相等的記錄，則必定在 f(K) 的存儲位置上。由此，不需比較便可直接取得所查記錄。

稱上面的對應(yīng)關(guān)系 f 為 散列函數(shù)（Hash function），按這個(gè)映射關(guān)系事先建立的表為散列表，這一映象過程稱為 散列造表 或 散列 ，最終所得的存儲位置稱 散列地址 。

---

哈希（散列）函數(shù)

哈希函數(shù)用來建立元素與其存儲位置的映射關(guān)系。

對于哈希函數(shù)來說，必須具有以下特點(diǎn)：

• 哈希函數(shù)的定義域必須包括需要存儲的全部關(guān)鍵碼，而如果散列表允許有 m 個(gè)地址時(shí)，其值域必須在 0 到 m-1 之間。
• 哈希函數(shù)計(jì)算出來的地址能均勻分布在整個(gè)空間中（防止產(chǎn)生密集的哈希沖突）

哈希沖突大量出現(xiàn)往往都是因?yàn)楣：瘮?shù)設(shè)計(jì)的不夠合理，但是即使再優(yōu)秀的哈希函數(shù)，也只能盡量減少哈希沖突的次數(shù)，無法避免哈希沖突。

---

常見的哈希函數(shù)

直接定址法（常見）
哈希函數(shù)：Hash(Key) = A * Key + B
這是最簡單的哈希函數(shù)，直接取關(guān)鍵字本身或者他的線性函數(shù)來作為散列地址。

除留余數(shù)法（常見）
哈希函數(shù) ：Hash(key) = key % capacity
幾乎是最常用的哈希函數(shù)，用一個(gè)數(shù)來對 key 取模，一般來說這個(gè)數(shù)都是容量。

平方取中法
對關(guān)鍵字進(jìn)行平方，然后取中間的幾位來作為地址。

折疊法
折疊法是將關(guān)鍵字從左到右分割成位數(shù)相等的幾部分（最后一部分位數(shù)可以短些），然后將這幾部分疊加求和（去除進(jìn)位），并按散列表表長，取后幾位作為散列地址。
折疊法適合事先不需要知道關(guān)鍵字的分布，適合關(guān)鍵字位數(shù)比較多的情況.

隨機(jī)數(shù)法
選擇一個(gè)隨機(jī)函數(shù)，取關(guān)鍵字的隨機(jī)函數(shù)值為它的哈希地址，即 H(key) = random(key)，其中 random 為隨機(jī)數(shù)函數(shù)。通常應(yīng)用于關(guān)鍵字長度不等時(shí)。

數(shù)學(xué)分析法
分析一組數(shù)據(jù)，比如一組員工的出生年月日，這時(shí)我們發(fā)現(xiàn)出生年月日的前幾位數(shù)字大體相同，這樣的話，出現(xiàn)沖突的幾率就會很大，但是我們發(fā)現(xiàn)年月日的后幾位表示月份和具體日期的數(shù)字差別很大，如果用后面的數(shù)字來構(gòu)成散列地址，則沖突的幾率會明顯降低。因此數(shù)字分析法就是找出數(shù)字的規(guī)律，盡可能利用這些數(shù)據(jù)來構(gòu)造沖突幾率較低的散列地址。

---

字符串哈希函數(shù)

因?yàn)楣：瘮?shù)的常用方法如直接定址、除留余數(shù)、平方取中等方法需要用的 key值 為整型，而大部分時(shí)候我們的 key 都是 string，由于無法對 string 進(jìn)行算數(shù)運(yùn)算，所以需要考慮新的方法。

常見的字符串哈希算法有 BKD、SDB、RS 等，這些算法大多通過一些公式來對字符串每一個(gè) 字符的 ascii值 或者 字符串的大小 進(jìn)行計(jì)算，來推導(dǎo)出一個(gè)不容易產(chǎn)生沖突的 key值 。

例如 BKDHash ：

struct _Hash<std::string> {const size_t& operator()(const std::string& key){// BKDR字符串哈希函數(shù)size_t hash = 0;for (size_t i = 0; i < key.size(); i++){hash *= 131;hash += key[i];}return hash;} };

這里推薦兩篇文章，一篇具體對比各類字符串哈希函數(shù)的效率，一篇是實(shí)現(xiàn)：

• 字符串Hash函數(shù)對比
• 各種字符串Hash函數(shù)

---

哈希沖突

對不同的關(guān)鍵字可能得到同一散列地址，即 key1≠key2 ，而 f(key1)=f(key2) ，這種現(xiàn)象稱碰撞（哈希沖突）。

哈希沖突使得多個(gè)數(shù)據(jù)映射的位置相同，但是每個(gè)位置又只能存儲一個(gè)數(shù)據(jù)，所以就需要通過某種方法來解決哈希沖突。

查找過程中，關(guān)鍵碼的比較次數(shù)，取決于產(chǎn)生沖突的多少，產(chǎn)生的沖突少，查找效率就高；產(chǎn)生的沖突多，查找效率就低。因此，影響產(chǎn)生沖突多少的因素，也就是影響查找效率的因素。影響產(chǎn)生沖突多少有以下三個(gè)因素：

散列函數(shù)是否均勻；

處理沖突的方法；

散列表的負(fù)載因子（裝填因子）。

第一點(diǎn)取決于上面講過的哈希函數(shù)，不再贅述，下面詳細(xì)講一下2、3點(diǎn)。

處理沖突的方法可分為兩類：開散列方法( open hashing，也稱為拉鏈法，separate chaining ) 和 閉散列方法( closed hashing，也稱為開地址方法，open addressing )。這兩種方法的不同之處在于：開散列法把發(fā)生沖突的關(guān)鍵碼存儲在散列表主表之外，而閉散列法把發(fā)生沖突的關(guān)鍵碼存儲在表中另一個(gè)槽內(nèi)。

---

閉散列（開放地址法）

因?yàn)殚]散列是順序的結(jié)構(gòu)，所以可以通過遍歷哈希表，來將沖突的數(shù)據(jù)放到空的位置上。

線性探測
線性探測即為從發(fā)生沖突的位置開始，依次向后探測，直到尋找到下一個(gè)空位置為止。
這種方法實(shí)現(xiàn)起來極為簡單，但是效率也不高，因?yàn)槿绻晃恢卯a(chǎn)生了大量的哈希沖突，就會導(dǎo)致每次都在同一個(gè)位置進(jìn)行探測，例如我在10這里連續(xù)沖突100次，此時(shí)所有探測的次數(shù)加起來就會高達(dá)100！

二次探測
二次探測即為從發(fā)生沖突的位置開始，每次往后探測 ±k²(k<=m/2，m為散列表長) 個(gè)位置，如：1²，-(1²)，2²，-(2²) 等。
這樣的話就將每次探測的效率從 O(N) 提升到了 O(logN) ，即使有著大量的沖突堆積，也不會導(dǎo)致效率過低。

偽隨機(jī)數(shù)探測
這種方法并不常見，實(shí)現(xiàn)方法是：創(chuàng)建一個(gè)偽隨機(jī)數(shù)序列，根據(jù)序列內(nèi)容決定每次往后探測的長度。

---

開散列（鏈地址法/拉鏈法）

先用哈希函數(shù)計(jì)算每個(gè)數(shù)據(jù)的散列地址，把具有相同地址的元素歸于同一個(gè)集合之中，把該集合處理為一個(gè)鏈表，鏈表的頭節(jié)點(diǎn)存儲于哈希表之中。

鏈地址法在每一個(gè)映射位置都建立起一個(gè)鏈表（數(shù)據(jù)過多時(shí)可能會轉(zhuǎn)為建立紅黑樹），將每次插入的數(shù)據(jù)都直接連接上這個(gè)鏈表，這樣就不會像閉散列一樣進(jìn)行大量的探測，但是如果鏈表過長也會導(dǎo)致效率低下。

---

負(fù)載因子以及增容

哈希沖突出現(xiàn)的較為密集，往往代表著此時(shí)數(shù)據(jù)過多，而能夠映射的地址過少，而要想解決這個(gè)問題，就需要通過 負(fù)載因子（裝填因子） 的判斷來進(jìn)行增容。

負(fù)載因子的大小 = 表中數(shù)據(jù)個(gè)數(shù) / 表的容量（長度）

對于閉散列

對于閉散列來說，因?yàn)槠涫且环N線性的結(jié)構(gòu)，所以一旦負(fù)載因子過高，就很容易出現(xiàn)哈希沖突的堆積，所以當(dāng)負(fù)載因子達(dá)到一定程度時(shí)就需要進(jìn)行增容，并且增容后，為了保證映射關(guān)系，還需要將數(shù)據(jù)重新映射到新位置。

經(jīng)過算法科學(xué)家的計(jì)算， 負(fù)載因子應(yīng)當(dāng)嚴(yán)格的控制在 0.7-0.8 以下，所以一旦負(fù)載因子到達(dá)這個(gè)范圍，就需要進(jìn)行增容。

因?yàn)槌粲鄶?shù)法等方法通常是按照表的容量來計(jì)算，所以科學(xué)家的計(jì)算，當(dāng)對一個(gè)質(zhì)數(shù)取模時(shí)，沖突的幾率會大大的降低，并且因?yàn)樵鋈莸膮^(qū)間一般是 1.5-2 倍，所以算法科學(xué)家列出了一個(gè)增容質(zhì)數(shù)表，按照這樣的規(guī)律增容，沖突的幾率會大大的降低。

這也是 STL 中 unordered_map/unordered_set 使用的增容方法。

//算法科學(xué)家總結(jié)出的一個(gè)增容質(zhì)數(shù)表，按照這樣增容的效率更高const int PRIMECOUNT = 28;const size_t primeList[PRIMECOUNT] = {53ul, 97ul, 193ul, 389ul, 769ul,1543ul, 3079ul, 6151ul, 12289ul, 24593ul,49157ul, 98317ul, 196613ul, 393241ul, 786433ul,1572869ul, 3145739ul, 6291469ul, 12582917ul, 25165843ul,50331653ul, 100663319ul, 201326611ul, 402653189ul, 805306457ul,1610612741ul, 3221225473ul, 4294967291ul};

hashmap 的負(fù)載因子為什么默認(rèn)是 0.75 ？

比如說當(dāng)前的容器容量是 16，負(fù)載因子是 0.75,16*0.75=12，也就是說，當(dāng)容量達(dá)到了 12 的時(shí)候就會進(jìn)行擴(kuò)容操作。而負(fù)載因子定義為 0.75 的原因是：

• 當(dāng)負(fù)載因子是 1.0 的時(shí)候，也就意味著，只有當(dāng)散列地址全部填充了，才會發(fā)生擴(kuò)容。意味著隨著數(shù)據(jù)增長，最后勢必會出現(xiàn)大量的沖突，底層的紅黑樹變得異常復(fù)雜。雖然空間利用率上去了，但是查詢時(shí)間效率降低了。
• 負(fù)載因子是 0.5 的時(shí)候，這也就意味著，當(dāng)數(shù)組中的元素達(dá)到了一半就開始擴(kuò)容。雖然時(shí)間效率提升了，但是空間利用率降低了。 誠然，填充的元素少了，Hash沖突也會減少，那么底層的鏈表長度或者是紅黑樹的高度就會降低。查詢效率就會增加。但是，這時(shí)候空間利用率就會大大的降低，原本存儲 1M 的數(shù)據(jù)，現(xiàn)在就意味著需要 2M 的空間。

對于開散列結(jié)構(gòu)

因?yàn)楣Ｍ笆情_散列的鏈?zhǔn)浇Y(jié)構(gòu)，發(fā)生了哈希沖突是直接在對應(yīng)位置位置進(jìn)行頭插，而桶的個(gè)數(shù)是固定的，而插入的數(shù)據(jù)會不斷增多，隨著數(shù)據(jù)的增多，就可能會導(dǎo)致某一個(gè)桶過重，使得效率過低。

所以最理想的情況，就是每個(gè)桶都有一個(gè)數(shù)據(jù)。這種情況下，如果往任何一個(gè)地方插入，都會產(chǎn)生哈希沖突，所以當(dāng)數(shù)據(jù)個(gè)數(shù)與桶的個(gè)數(shù)相同時(shí)，也就是負(fù)載因子為 1 時(shí)就需要進(jìn)行擴(kuò)容。

---

具體實(shí)現(xiàn)

哈希表（閉散列）

創(chuàng)建

對于閉散列，我們需要通過狀態(tài)來記錄一個(gè)數(shù)據(jù)是否在表中，所以這里會使用枚舉來實(shí)現(xiàn)。

enum State {EMPTY,//空EXITS,//存在DELETE,//已經(jīng)刪除 };template<class T> struct HashData {HashData(const T& data = T(), const State& state = EMPTY): _data(data), _state(state){}T _data;State _state; };

插入

插入的思路很簡單，計(jì)算出映射的地址后，開始遍歷判斷下面幾種狀態(tài)：

• 如果映射位置已存在數(shù)據(jù)，并且值與當(dāng)前數(shù)據(jù)不同，則說明產(chǎn)生沖突，繼續(xù)往后查找
• 如果映射位置的數(shù)據(jù)與插入的數(shù)據(jù)相同，則說明此時(shí)數(shù)據(jù)已經(jīng)插入過，此時(shí)就不需要再次插入
• 如果映射位置的狀態(tài)為刪除或者空，則代表著此時(shí)表中沒有這個(gè)數(shù)據(jù)，在這個(gè)位置插入即可

bool Insert(const T& data) {KeyOfT koft;//判斷此時(shí)是否需要增容//當(dāng)裝填因子大于0.7時(shí)增容if (_size * 10 / _table.size() >= 7){//增容的大小按照別人算好的近似兩倍的素?cái)?shù)來增，這樣效率更高，也可以直接2倍或者1.5倍。std::vector<HashData> newTable(getNextPrime(_size));for (size_t i = 0; i < _table.size(); i++){//將舊表中的數(shù)據(jù)全部重新映射到新表中if (_table[i]._state == EXITS){//如果產(chǎn)生沖突，則找到一個(gè)合適的位置size_t index = HashFunc(koft(_table[i]._data));while (newTable[i]._state == EXITS){i++;if (i == _table.size()){i = 0;}}newTable[i] = _table[i];}}//最后直接將數(shù)據(jù)進(jìn)行交換即可，原來的數(shù)據(jù)會隨著函數(shù)棧幀一起銷毀_table.swap(newTable);}//用哈希函數(shù)計(jì)算出映射的位置size_t index = HashFunc(koft(data));//從那個(gè)位置開始探測, 如果該位置已經(jīng)存在時(shí)，有兩種情況，一種是已經(jīng)存在，一種是沖突，這里使用的是線性探測while (_table[index]._state == EXITS){//如果已經(jīng)存在了，則說明不用插入if (koft(_table[index]._data) == koft(data)){return false;}else{index++;index = HashFunc(index);}}//如果走到這里，說明這個(gè)位置是空的或者已經(jīng)被刪除的位置，可以在這里插入_table[index]._data = data;_table[index]._state = EXITS;_size++;return true; }

---

查找

查找也分幾種情況

• 如果映射的位置為空，則說明查找失敗。
• 如果映射的位置的數(shù)據(jù)不同，則說明產(chǎn)生沖突，繼續(xù)向后查找
• 如果映射的位置的數(shù)據(jù)相同，如果狀態(tài)為刪除，則說明數(shù)據(jù)已經(jīng)刪除，查找失敗；而如果數(shù)據(jù)為存在，則說明查找成功。

HashData* Find(const K& key) {KeyOfT koft;size_t index = HashFunc(key);//遍歷，如果查找的位置為空，則說明查找失敗while (_table[index]._state != EMPTY){//此時(shí)判斷這個(gè)位置的數(shù)據(jù)是否相同，如果不同則說明出現(xiàn)哈希沖突，繼續(xù)往后查找if (koft(_table[index]._data) == key){//此時(shí)有兩個(gè)狀態(tài)，一種是數(shù)據(jù)已經(jīng)被刪除，一種是數(shù)據(jù)存在。if (_table[index]._state == EXITS){return &_table[index];}else if (_table[index]._state == DELETE){return nullptr;}}index++;//如果index越界，則歸零if (index == _table.size()){index = 0;}}return nullptr; }

---

刪除

直接遍歷查找數(shù)據(jù)，如果找不到則說明已經(jīng)被刪除，如果找到了則直接將狀態(tài)改為刪除即可。

bool Erase(const K& key) {HashData* del = Find(key);//如果找不到則說明已經(jīng)被刪除if (del == nullptr){return false;}else{//找到了則直接更改狀態(tài)即可del->_state = DELETE;_size--;return true;} }

---

完整代碼

#pragma once #include<vector>namespace lee {//算法科學(xué)家總結(jié)出的一個(gè)增容質(zhì)數(shù)表，按照這樣增容的效率更高const int PRIMECOUNT = 28;const size_t primeList[PRIMECOUNT] = {53ul, 97ul, 193ul, 389ul, 769ul,1543ul, 3079ul, 6151ul, 12289ul, 24593ul,49157ul, 98317ul, 196613ul, 393241ul, 786433ul,1572869ul, 3145739ul, 6291469ul, 12582917ul, 25165843ul,50331653ul, 100663319ul, 201326611ul, 402653189ul, 805306457ul,1610612741ul, 3221225473ul, 4294967291ul};enum State{EMPTY,EXITS,DELETE,};template<class T>struct HashData{HashData(const T& data = T(), const State& state = EMPTY): _data(data), _state(state){}T _data;State _state;};template<class K, class T, class KeyOfT>class HashTable{public:typedef HashData<T> HashData;HashTable(size_t capacity = 10): _table(capacity), _size(0){}size_t getNextPrime(size_t num){size_t i = 0;for (i = 0; i < PRIMECOUNT; i++){//返回比那個(gè)數(shù)大的下一個(gè)質(zhì)數(shù) if (primeList[i] > num){return primeList[i];}}//如果比所有都大，還是返回最后一個(gè)，因?yàn)樽詈笠粋€(gè)已經(jīng)是32位最大容量return primeList[PRIMECOUNT - 1];}//除留余數(shù)法size_t HashFunc(const K& key){return key % _table.size();}bool Insert(const T& data){KeyOfT koft;//判斷此時(shí)是否需要增容//當(dāng)裝填因子大于0.7時(shí)增容if (_size * 10 / _table.size() >= 7){//增容的大小按照別人算好的近似兩倍的素?cái)?shù)來增，這樣效率更高，也可以直接2倍或者1.5倍。std::vector<HashData> newTable(getNextPrime(_size));for (size_t i = 0; i < _table.size(); i++){//將舊表中的數(shù)據(jù)全部重新映射到新表中if (_table[i]._state == EXITS){//如果產(chǎn)生沖突，則找到一個(gè)合適的位置size_t index = HashFunc(koft(_table[i]._data));while (newTable[i]._state == EXITS){i++;if (i == _table.size()){i = 0;}}newTable[i] = _table[i];}}//最后直接將數(shù)據(jù)進(jìn)行交換即可，原來的數(shù)據(jù)會隨著函數(shù)棧幀一起銷毀_table.swap(newTable);}//用哈希函數(shù)計(jì)算出映射的位置size_t index = HashFunc(koft(data));//從那個(gè)位置開始探測, 如果該位置已經(jīng)存在時(shí)，有兩種情況，一種是已經(jīng)存在，一種是沖突，這里使用的是線性探測while (_table[index]._state == EXITS){//如果已經(jīng)存在了，則說明不用插入if (koft(_table[index]._data) == koft(data)){return false;}else{index++;index = HashFunc(index);}}//如果走到這里，說明這個(gè)位置是空的或者已經(jīng)被刪除的位置，可以在這里插入_table[index]._data = data;_table[index]._state = EXITS;_size++;return true;}HashData* Find(const K& key){KeyOfT koft;size_t index = HashFunc(key);//遍歷，如果查找的位置為空，則說明查找失敗while (_table[index]._state != EMPTY){//此時(shí)判斷這個(gè)位置的數(shù)據(jù)是否相同，如果不同則說明出現(xiàn)哈希沖突，繼續(xù)往后查找if (koft(_table[index]._data) == key){//此時(shí)有兩個(gè)狀態(tài)，一種是數(shù)據(jù)已經(jīng)被刪除，一種是數(shù)據(jù)存在。if (_table[index]._state == EXITS){return &_table[index];}else if (_table[index]._state == DELETE){return nullptr;}}index++;//如果index越界，則歸零if (index == _table.size()){index = 0;}}return nullptr;}bool Erase(const K& key){HashData* del = Find(key);//如果找不到則說明已經(jīng)被刪除if (del == nullptr){return false;}else{//找到了則直接更改狀態(tài)即可del->_state = DELETE;_size--;return true;}}private:std::vector<HashData> _table;size_t _size;}; };

---

哈希桶（開散列）

開散列也叫哈希桶，桶為每一個(gè)映射的位置，桶一般用鏈表或者紅黑樹實(shí)現(xiàn)（這里我用的是鏈表）。當(dāng)我們通過映射的地址，找到存放數(shù)據(jù)的桶，再對桶進(jìn)行插入或者刪除操作即可。

插入

通過計(jì)算映射位置找到對應(yīng)的桶，再判斷數(shù)據(jù)是否存在后將數(shù)據(jù)頭插進(jìn)去即可（也可以尾插）

bool Insert(const T& data) {KeyofT koft;/*因?yàn)楣Ｍ笆情_散列的鏈?zhǔn)浇Y(jié)構(gòu)，發(fā)生了哈希沖突是直接在對應(yīng)位置位置進(jìn)行頭插，而桶的個(gè)數(shù)是固定的，而插入的數(shù)據(jù)會不斷增多，隨著數(shù)據(jù)的增多，就可能會導(dǎo)致某一個(gè)桶過重，使得效率過低。所以最理想的情況，就是每個(gè)桶都有一個(gè)數(shù)據(jù)。這種情況下，如果往任何一個(gè)地方插入，都會產(chǎn)生哈希沖突，所以當(dāng)數(shù)據(jù)個(gè)數(shù)與桶的個(gè)數(shù)相同時(shí)，也就是負(fù)載因子為1時(shí)就需要進(jìn)行擴(kuò)容。*/if (_size == _table.size()){//按照素?cái)?shù)表來增容size_t newSize = getNextPrime(_table.size());size_t oldSize = _table.size();std::vector<Node*> newTable(newSize);_table.resize(newSize);//接著將數(shù)據(jù)重新映射過去for (size_t i = 0; i < oldSize; i++){Node* cur = _table[i];while (cur){//重新計(jì)算映射的位置size_t pos = HashFunc(koft(cur->_data));//找到位置后頭插進(jìn)對應(yīng)位置Node* next = cur->_next;cur->_next = newTable[pos];newTable[pos] = cur;cur = next;}//原數(shù)據(jù)置空_table[i] == nullptr;}//直接和新表交換，交換過去的舊表會和函數(shù)棧幀一塊銷毀。_table.swap(newTable);}size_t pos = HashFunc(koft(data));Node* cur = _table[pos];//因?yàn)楣Ｍ発ey值唯一，如果已經(jīng)在桶中則返回falsewhile (cur){if (koft(cur->_data) == koft(data)){return false;}else{cur = cur->_next;}}//檢查完成，此時(shí)開始插入，這里選擇的是頭插，這樣就可以減少數(shù)據(jù)遍歷的次數(shù)。Node* newNode = new Node(data);newNode->_next = _table[pos];_table[pos] = newNode;++_size;return true; }

---

查找

直接根據(jù)映射的位置到桶中查找數(shù)據(jù)即可

Node* Find(const K& key) {KeyofT koft;size_t pos = HashFunc(key);Node* cur = _table[pos];while (cur){if (koft(cur->_data) == key){return cur;}else{cur = cur->_next;}}return nullptr; }

---

刪除

bool Erase(const K& key) {KeyofT koft;size_t pos = HashFunc(key);Node* cur = _table[pos];Node* prev = nullptr;while (cur){if (koft(cur->_data) == key){//如果要刪除的是第一個(gè)節(jié)點(diǎn)，就讓下一個(gè)節(jié)點(diǎn)成為新的頭節(jié)點(diǎn)，否則直接刪除。if (prev == nullptr){_table[pos] = cur->_next;}else{prev->_next = cur->_next;}delete cur;--_size;return true;}else{prev = cur;cur = cur->_next;}}return false; }

---

完整代碼

#pragma once #include<vector> #include<string>namespace lee {//算法科學(xué)家總結(jié)出的一個(gè)增容質(zhì)數(shù)表，按照這樣增容的效率更高const int PRIMECOUNT = 28;const size_t primeList[PRIMECOUNT] = {53ul, 97ul, 193ul, 389ul, 769ul,1543ul, 3079ul, 6151ul, 12289ul, 24593ul,49157ul, 98317ul, 196613ul, 393241ul, 786433ul,1572869ul, 3145739ul, 6291469ul, 12582917ul, 25165843ul,50331653ul, 100663319ul, 201326611ul, 402653189ul, 805306457ul,1610612741ul, 3221225473ul, 4294967291ul};/*因?yàn)楣：瘮?shù)的常用方法如直接定地、除留余數(shù)、平方取中等方法需要用的key值為整型，而大部分時(shí)候我們的key都是string，或者某些自定義類型，這個(gè)時(shí)候就可以提供一個(gè)仿函數(shù)的接口給外部，讓他自己處理如何將key轉(zhuǎn)換成我們需要的整型*/template<class K>struct Hash{const K& operator()(const K& key){return key;}};template<>struct Hash<std::string>{const size_t & operator()(const std::string& key){//BKDR字符串哈希函數(shù)size_t hash = 0;for (size_t i = 0; i < key.size(); i++){hash *= 131;hash += key[i];}return hash;}};template<class T>struct HashNode{HashNode(const T& data = T()): _data(data), _next(nullptr){}T _data;HashNode<T>* _next;};template<class K, class T, class KeyofT, class Hash = Hash<K>>class HashBucket{public:typedef HashNode<T> Node;HashBucket(size_t capacity = 10): _table(capacity), _size(0){}~HashBucket(){Clear();}size_t getNextPrime(size_t num){size_t i = 0;for (i = 0; i < PRIMECOUNT; i++){//返回比那個(gè)數(shù)大的下一個(gè)質(zhì)數(shù) if (primeList[i] > num){return primeList[i];}}//如果比所有都大，還是返回最后一個(gè)，因?yàn)樽詈笠粋€(gè)已經(jīng)是32位最大容量return primeList[PRIMECOUNT - 1];}size_t HashFunc(const K& key){Hash hash;return hash(key) % _table.size();}bool Insert(const T& data){KeyofT koft;/*因?yàn)楣Ｍ笆情_散列的鏈?zhǔn)浇Y(jié)構(gòu)，發(fā)生了哈希沖突是直接在對應(yīng)位置位置進(jìn)行頭插，而桶的個(gè)數(shù)是固定的，而插入的數(shù)據(jù)會不斷增多，隨著數(shù)據(jù)的增多，就可能會導(dǎo)致某一個(gè)桶過重，使得效率過低。所以最理想的情況，就是每個(gè)桶都有一個(gè)數(shù)據(jù)。這種情況下，如果往任何一個(gè)地方插入，都會產(chǎn)生哈希沖突，所以當(dāng)數(shù)據(jù)個(gè)數(shù)與桶的個(gè)數(shù)相同時(shí)，也就是負(fù)載因子為1時(shí)就需要進(jìn)行擴(kuò)容。*/if (_size == _table.size()){//按照素?cái)?shù)表來增容size_t newSize = getNextPrime(_table.size());size_t oldSize = _table.size();std::vector<Node*> newTable(newSize);_table.resize(newSize);//接著將數(shù)據(jù)重新映射過去for (size_t i = 0; i < oldSize; i++){Node* cur = _table[i];while (cur){//重新計(jì)算映射的位置size_t pos = HashFunc(koft(cur->_data));//找到位置后頭插進(jìn)對應(yīng)位置Node* next = cur->_next;cur->_next = newTable[pos];newTable[pos] = cur;cur = next;}//原數(shù)據(jù)置空_table[i] == nullptr;}//直接和新表交換，交換過去的舊表會和函數(shù)棧幀一塊銷毀。_table.swap(newTable);}size_t pos = HashFunc(koft(data));Node* cur = _table[pos];//因?yàn)楣Ｍ発ey值唯一，如果已經(jīng)在桶中則返回falsewhile (cur){if (koft(cur->_data) == koft(data)){return false;}else{cur = cur->_next;}}//檢查完成，此時(shí)開始插入，這里選擇的是頭插，這樣就可以減少數(shù)據(jù)遍歷的次數(shù)。Node* newNode = new Node(data);newNode->_next = _table[pos];_table[pos] = newNode;++_size;return true;}bool Erase(const K& key){KeyofT koft;size_t pos = HashFunc(key);Node* cur = _table[pos];Node* prev = nullptr;while (cur){if (koft(cur->_data) == key){//如果要刪除的是第一個(gè)節(jié)點(diǎn)，就讓下一個(gè)節(jié)點(diǎn)成為新的頭節(jié)點(diǎn)，否則直接刪除。if (prev == nullptr){_table[pos] = cur->_next;}else{prev->_next = cur->_next;}delete cur;--_size;return true;}else{prev = cur;cur = cur->_next;}}return false;}Node* Find(const K& key){KeyofT koft;size_t pos = HashFunc(key);Node* cur = _table[pos];while (cur){if (koft(cur->_data) == key){return cur;}else{cur = cur->_next;}}return nullptr;}void Clear(){//刪除所有節(jié)點(diǎn)for (size_t i = 0; i < _table.size(); i++){Node* cur = _table[i];while (cur){Node* next = cur->_next;delete cur;cur = next;}_table[i] = nullptr;}}private:std::vector<Node*> _table;size_t _size;}; };

總結(jié)

以上是生活随笔為你收集整理的哈希 ：哈希冲突、负载因子、哈希函数、哈希表、哈希桶的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。