文章目錄

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

哈希

在之前介紹的數(shù)據(jù)結(jié)構(gòu)中，元素與其所存儲(chǔ)的位置之間沒有對(duì)應(yīng)的關(guān)系，所以在查找的時(shí)候就需要經(jīng)過多次的比較，才能找到具體的位置。對(duì)于順序結(jié)構(gòu)來說，這樣查找的時(shí)間復(fù)雜度一般都是O（N）,而對(duì)于樹形結(jié)構(gòu)的如搜索樹等則也需要O（logN）。
但是，還存在著這樣一種數(shù)據(jù)結(jié)構(gòu)，他通過某種方法的處理，使得元素存儲(chǔ)的位置與元素本身建立起了映射關(guān)系，此時(shí)如果要查找改數(shù)據(jù)，就可以直接到對(duì)應(yīng)的位置去，使得時(shí)間復(fù)雜度達(dá)到了O（1），這就是哈希（散列）。

---

哈希函數(shù)

哈希函數(shù)就是建立起元素與其存儲(chǔ)位置的映射關(guān)系。
對(duì)于哈希函數(shù)來說，必須具有以下特點(diǎn);

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

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

常見的哈希函數(shù)

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

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

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

折疊法
折疊法是將關(guān)鍵字從左到右分割成位數(shù)相等的幾部分(最后一部分位數(shù)可以短些)，然后將這幾部分疊加
求和，并按散列表表長，取后幾位作為散列地址。
折疊法適合事先不需要知道關(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è)有n個(gè)d位數(shù)，每一位可能有r種不同的符號(hào)，這r種不同的符號(hào)在各位上出現(xiàn)的頻率不一定相同，可能
在某些位上分布比較均勻，每種符號(hào)出現(xiàn)的機(jī)會(huì)均等，在某些位上分布不均勻只有某幾種符號(hào)經(jīng)常出
現(xiàn)。可根據(jù)散列表的大小，選擇其中各種符號(hào)分布均勻的若干位作為散列地址

---

字符串哈希函數(shù)

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

常見的字符串哈希算法有BKD,SDB,RS等，這些算法大多通過一些公式來對(duì)字符串每一個(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;} };

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

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

---

哈希沖突

哈希沖突就是兩個(gè)不同的數(shù)據(jù)通過同一個(gè)哈希函數(shù)計(jì)算出了相同的位置，這種現(xiàn)象就是哈希沖突。

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

對(duì)于哈希沖突的解決方法，一般根據(jù)不同的結(jié)構(gòu)，分為以下幾種

---

閉散列的解決方法

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

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

二次探測(cè)
線性探測(cè)即為從發(fā)生沖突的位置開始，每次往后探測(cè)i^2個(gè)位置，如1， 2， 4， 8等，這樣的話就將每次探測(cè)的效率從O（N）提升到了O（logN）,即使有著大量的沖突堆積，也不會(huì)導(dǎo)致效率過低。

---

開散列的解決方法

因?yàn)殚_散列本身就是一種鏈?zhǔn)降慕Y(jié)構(gòu)，所以其本身就是一種解決方法，這種方法也叫做鏈地址法
鏈地址法

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

---

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

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

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

對(duì)于閉散列

對(duì)于閉散列來說，因?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)對(duì)一個(gè)質(zhì)數(shù)取模時(shí)，沖突的幾率會(huì)大大的降低，并且因?yàn)樵鋈莸膮^(qū)間一般是1.5-2倍，所以算法科學(xué)家列出了一個(gè)增容質(zhì)數(shù)表，按照這樣的規(guī)律增容，沖突的幾率會(huì)大大的降低。

這也是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};

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

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

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

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

哈希表（閉散列）

對(duì)于閉散列，我們需要通過狀態(tài)來記錄一個(gè)數(shù)據(jù)是否在表中，所以這里會(huì)使用枚舉來實(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; };

插入

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

如果映射位置已存在數(shù)據(jù)，并且狀態(tài)為存在，則說明產(chǎn)生沖突，繼續(xù)往后查找

如果映射位置的數(shù)據(jù)與插入的數(shù)據(jù)相同，并且狀態(tài)為存在，則說明此時(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ù)會(huì)隨著函數(shù)棧幀一起銷毀_table.swap(newTable);}//用哈希函數(shù)計(jì)算出映射的位置size_t index = HashFunc(koft(data));//從那個(gè)位置開始探測(cè), 如果該位置已經(jīng)存在時(shí)，有兩種情況，一種是已經(jīng)存在，一種是沖突，這里使用的是線性探測(cè)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ù)不同，并且狀態(tài)為存在，則說明產(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;} }

完整代碼實(shí)現(xiàn)

#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ù)會(huì)隨著函數(shù)棧幀一起銷毀_table.swap(newTable);}//用哈希函數(shù)計(jì)算出映射的位置size_t index = HashFunc(koft(data));//從那個(gè)位置開始探測(cè), 如果該位置已經(jīng)存在時(shí)，有兩種情況，一種是已經(jīng)存在，一種是沖突，這里使用的是線性探測(cè)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ù)的桶，再對(duì)桶進(jìn)行插入或者刪除操作即可。

插入

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

bool Insert(const T& data) {KeyofT koft;/*因?yàn)楣Ｍ笆情_散列的鏈?zhǔn)浇Y(jié)構(gòu)，發(fā)生了哈希沖突是直接在對(duì)應(yīng)位置位置進(jìn)行頭插，而桶的個(gè)數(shù)是固定的，而插入的數(shù)據(jù)會(huì)不斷增多，隨著數(shù)據(jù)的增多，就可能會(huì)導(dǎo)致某一個(gè)桶過重，使得效率過低。所以最理想的情況，就是每個(gè)桶都有一個(gè)數(shù)據(jù)。這種情況下，如果往任何一個(gè)地方插入，都會(huì)產(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)對(duì)應(yīng)位置Node* next = cur->_next;cur->_next = newTable[pos];newTable[pos] = cur;cur = next;}//原數(shù)據(jù)置空_table[i] == nullptr;}//直接和新表交換，交換過去的舊表會(huì)和函數(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){//如果要?jiǎng)h除的是第一個(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; }

完整代碼實(shí)現(xiàn)

#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ā)生了哈希沖突是直接在對(duì)應(yīng)位置位置進(jìn)行頭插，而桶的個(gè)數(shù)是固定的，而插入的數(shù)據(jù)會(huì)不斷增多，隨著數(shù)據(jù)的增多，就可能會(huì)導(dǎo)致某一個(gè)桶過重，使得效率過低。所以最理想的情況，就是每個(gè)桶都有一個(gè)數(shù)據(jù)。這種情況下，如果往任何一個(gè)地方插入，都會(huì)產(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)對(duì)應(yīng)位置Node* next = cur->_next;cur->_next = newTable[pos];newTable[pos] = cur;cur = next;}//原數(shù)據(jù)置空_table[i] == nullptr;}//直接和新表交換，交換過去的舊表會(huì)和函數(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){//如果要?jiǎng)h除的是第一個(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é)

以上是生活随笔為你收集整理的高级数据结构与算法 | 哈希 ：哈希冲突、负载因子、哈希函数、哈希表、哈希桶的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

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