c++實現(xiàn)哈希桶的步驟
閉散列的回顧
在前面的學習中我們知道了閉散列的運算規(guī)則，當兩個數據計算得到的位置發(fā)生沖突時，它會自動的往后尋找沒有發(fā)生沖突的位置，比如說當前數據的內容如下：
當插入的數據為33時計算的位置為3，可是位置3已經被占領了并且4也被占領了，但是位置5沒有被占領所以插入數據33就會占領位置5，那么這里的圖片就如下：
這就是閉散列的插入原則，并且每個節(jié)點都有一個變量用來表示狀態(tài)，這樣在查找就不會出現(xiàn)漏查的情況，但是這樣的實現(xiàn)會存在一個問題，擴容是根據有效數據的個數和vector容量來確定的，但是查找的時候是根據當前元素的狀態(tài)是否為空來判斷后面還有沒有要查找的數據，如果為空的話則說明當前元素的后面沒有我們要查找的元素，如果為存在或者被刪除的話就說明當前元素的后面還有我們要查找的數據，如果我們不停的插入數據并且刪除數據的話就會導致容器中的每個元素的狀態(tài)都變成了被刪除這樣在查找一個不存的數據時，就會陷入死循環(huán)的狀態(tài)那么這就是我們之前模擬實現(xiàn)的一個缺點，那么這里我們就來看看第二個解決數據不集中的方法：拉鏈法或者叫哈希桶法。
拉鏈法/哈希桶的原理
這個方法就是每個位置上都是一個鏈表，如果有多個位置發(fā)生沖突了，那么就掛在這個位置的鏈表上，這樣就不會導致占領別人的位置，當我們要查找的時候就是先找到插入數據的位置，然后再通過這個位置的鏈表來按照順序來進行查找，比如說下面的圖片
當我們想要插入一個數據13時就會先計算13對應在哈希表上的位置，根據之前的計算原則這里得到的位置就是3，所以圖片就變成了下面這樣：
如果再插入數據23的話這里計算的位置依然是3，但是此時3上已經有元素了，所以這時就會使用鏈表的頭插將數據23插入到13的前面，那么這里的圖片就是下面這樣：
如果再插入數據33的話計算的位置依然是3，所以就會把33放到3號位置對應的鏈表的頭部，那么這里的圖片就變成下面這樣：
那么這就是哈希桶的插入規(guī)則，找到對應位置的鏈表將數據插入到頭部即可，如果要查找的話也是相同的原理先找到數據對應的鏈表然后循環(huán)遍歷這個鏈表找到出現(xiàn)的數據即可，刪除也是相同的道理，先找到數據對應的下標然后根據下標找到對應的鏈表，最后遍歷鏈表找到要刪除的數據進行鏈表的刪除即可，那么這就是哈希桶的實現(xiàn)思路接下來我們就來看看這種方法的準備工作。
準備工作
哈希的底層是一個vector的數組，數組中的每個節(jié)點都有一個pair類型的數據，其次還有一個指針指向當前鏈表節(jié)點的下一個節(jié)點，所以每個節(jié)點中有個一個pair類型的數據和一個指向節(jié)點的指針，所以這里得創(chuàng)建一個類來描述每個節(jié)點，并且類中有一個構造函數來初始化節(jié)點，這里的構造函數就需要一個pair類型的參數，在構造函數里面就將指針初始化為nullptr將pair類型的參數賦值為傳遞過來的參數，有因為這里的節(jié)點可能要存儲各種各樣的數據，所以這里得創(chuàng)建個模板來接收各種各樣的參數，并且模板的參數得是兩個，那么這里的代碼就如下：
template<class K,class V>
struct HashNode
{
HashNode(const pair<K,V>& kv)
:_kv(kv)
,_next(nullptr)
{}
pair<K, V> _kv;
HashNode* _next;
};根據前面的學習我們知道要想計算數據對應在哈希表上的位置就得添加對應的仿函數，那么這里的代碼就如下
template<class K>
struct HashFunc
{
size_t operator()(const K& key)
{
return (size_t)key;
}
};
template<>
struct HashFunc<string>
{
size_t operator()(const string& s)
{
size_t res = 0;
for (auto& ch : s)
{
res *= 131;
res += ch;
}
return res;
}
};最后就是哈希bucket類的準備工作，首先這個類有一個模板，模板中有三個參數，前兩個表示存儲數據的類型，最后一個表示的是仿函數，因為哈希的地城是vector數組，所以這里得添加一個vector容器用來存儲數據和一個整型變量用來記錄容器中有效字符的個數即可，并且vector中的每個元素都是節(jié)點類型，那么該類的構造函數就將vector容器的resize到10個元素即可，那么這里的代碼就如下：
template<class K, class V, class Hash = HashFunc<K>>
class BucketTable
{
typedef HashNode<K, V> Node;
public:
typedef HashNode<K, V> Node;
BucketTable()
:_n(0)
{
_tables.resize(10);
}
private:
vector<Node*> _tables;
size_t _n;
};看到這里我們的準備工作就完成了接下來就要實現(xiàn)哈希的每個函數。
find函數
find函數就是先根據傳遞過來參數找到這個參數可能出現(xiàn)的位置，找到了位置就意味著找了一個鏈表的頭節(jié)點，所以這個時候就可以通過循環(huán)遍歷的方式來一一對比鏈表中是否含有想要查找的數據，如果存在的話就返回這個節(jié)點所在的地址，如果不存在的話就返回一個空指針，所以該函數的第一步就創(chuàng)建一個仿函數對象，并計算數據出現(xiàn)的位置：
Node* Find(const K& key)
{
Hash hf;
size_t pos = hf(key) % _tables.size();
Node* cur=_tables[pos]
}cur指向的是鏈表的第一個元素，所以接下來就可以使用while循環(huán)一個一個的遍歷每個元素，每次循環(huán)都會改變cur的指向讓其指向下一個元素，知道cur本身變?yōu)榭站屯Ｖ共檎?，在循環(huán)體的內部如果出現(xiàn)了跟查找變量一樣的值就直接返回這個節(jié)點的地址，如果循環(huán)結束了也沒有找到想要的值的話就返回一個空指針，那么這里的代碼就如下：
Node* Find(const K& key)
{
Hash hf;
size_t pos = hf(key) % _tables.size();
Node* cur = _tables[pos];
while (cur)
{
if (cur->_kv.first == key)
{
return cur;
}
else
{
cur = cur->_next;
}
}
return nullptr;
}插入函數
將數據插入的鏈表的時候得先判斷一下要插入的元素當前是否已經存在，所以這里可以使用find函數來進行查找，根據find函數的返回值來判斷是否存在，那么這里的代碼就如下：
bool insert(const pair<K, V>& kv)
{
if (Find(kv.first))
{
return false;
}
}如果當前的元素不存在的話就開始插入數據，這種實現(xiàn)方法也得根據傳遞過來的元素找到應該插入的位置，所以該函數的第一步就是創(chuàng)建一個仿函數對象然后根據傳遞過來的參數計算得出應該插入的位置，找到插入位置之后就使用頭插來插入對應的數據，這里的頭插就是先讓newnode的_next指向當前位置的鏈表，然后修改vector中當前位置的指向使其指向newnode，那么這里的代碼就如下：
bool insert(const pair<K, V>& kv)
{
if (Find(kv.first))
{
return false;
}
Hash hf;
size_t pos = hf(kv.first) % _tables.size();
Node* newnode = new HashNode<K,V>(kv);
newnode->_next = _tables[pos];
_tables[pos] = newnode;
++_n;
return true;
}這里依然得添加負載因子，官方庫中可以通過一些函數來得到當前容器的負載因子和最大的負載因子，如果負載因子等于1了我們就擴容，將其容量變?yōu)橹暗膬杀?，但是擴容不能直接把鏈表對應的移動到新的容器上去因為這里的映射關系已經改變了比如說當前容器的容量為10則數據18對應的位置就是8上面的鏈表，如果容器發(fā)生了擴容使得容量變成了20的話18就對應的不再是8而是18上面的鏈表，所以我們這里解決的方法就是創(chuàng)建一個新的哈希表，然后遍歷容器中的每個位置，如果當前位置不為空就往這個位置里面進行遍歷對每個元素都進行插入操作，如果當前位置為空的話就跳轉到下一個元素，那么這里的代碼就如下：
bool insert(const pair<K, V>& kv)
{
if (!Find(kv.first))
{
return false;
}
if (_n / _tables.size() == 1)//平衡因子為1就更新
{
vector<Node*> newBH;
newBH._tables.resize(_n * 2);
for (auto& cur : _tables)
{
while (cur)
{
newBH.insert(cur->_kv);
cur = cur->_next;
}
}
_tables.swap(newBH._tables);
}
Hash hf;
size_t pos = hf(kv.first) % _tables.size();
Node* newnode = new HashNode<K,V>(kv);
newnode->_next = _tables[pos];
_tables[pos] = newnode;
++_n;
return true;
}erase函數
erase函數也是分為三步來完成，首先找到節(jié)點對應的鏈表，然后再找鏈表中是否存在該元素，如果不存在的話就返回false，如果存在的話就對該鏈表的該節(jié)點進行刪除，因為這里刪除的時候得保證鏈表之間的上下鏈接，所以這里創(chuàng)建一個指向指向被刪除節(jié)點的前一個節(jié)點，以此來保證刪除前后的鏈接，這里大家要注意的一點就是當刪除的節(jié)點是頭節(jié)點時，得改變vector容器中的指針的指向，那么這里的代碼就如下：
bool erase(const K& key)
{
HashFunc<K> HF;
size_t pos = HF(key) % _tables.size();
Node* cur = _tables[pos];
Node* prev = cur;
while (cur)
{
if (cur->_kv.first == key)
{
if (cur == _tables[pos])
{
_tables[pos] = cur->_next;
}
else
{
prev->_next = cur->_next;
}
delete cur;
_n--;
return true;
}
else
{
prev = cur;
cur = cur->_next;
}
}
return false;
}析構函數
之前的寫法當中不需要添加析構函數是因為vector中本身就含有析構函數，所以編譯器自己生成的析構函數能夠自動的調用vector的析構函數來釋放空間，但是這里不一樣這里得寫析構函數，因為vector釋放之后不會釋放里面的節(jié)點所申請的空間，所以這里的析構函數要干的事情就是虛幻遍歷每個節(jié)點并且一個一個的釋放每個節(jié)點申請的空間，那么這里的代碼就如下：
~BucketTable()
{
for (int i = 0; i < _tables.size(); i++)
{
Node* cur = _tables[i];
while (cur)
{
Node* next = cur->_next;
delete cur;
cur = next;
}
_tables[i] = nullptr;
}
}代碼測試
可以通過下面的代碼來進行相應的測試看看我們上面寫的代碼是否是正確的：
void TestHT1()
{
BucketTable<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));
if (ht.Find(7)) { cout << "存在" << endl; }
else { cout << "不存在" << endl; }
ht.erase(7);
if (ht.Find(7)) { cout << "存在" << endl; }
else { cout << "不存在" << endl; }
}
int main()
{
TestHT1();
return 0;
}代碼的運行結果如下：
我們可以再用下面的代碼來進行一下測試：
void TestHT2()
{
string arr[] = { "蘋果", "西瓜", "香蕉", "草莓", "蘋果", "西瓜", "蘋果", "蘋果", "西瓜", "蘋果", "香蕉", "蘋果", "香蕉" };
//HashTable<string, int, HashFuncString> countHT;
BucketTable<string, int> countHT;
for (auto& e : arr)
{
HashNode<string, int>* ret = countHT.Find(e);
if (ret)
{
ret->_kv.second++;
}
else
{
countHT.insert(make_pair(e, 1));
}
}
}這段代碼的運行結果如下：
符合我們的預期說明我們上面的代碼實現(xiàn)的是正確的。
insert函數的改進
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
};然后我們就可以用這個數組封裝成為一個函數，這個函數的功能就是找到一個數據附件的素數，這里就可以通過循環(huán)遍歷的方式來進行查找，那么這里的代碼如下：
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];
}有了這個游戲之后就可以對insert函數進行改進，但是這里先不要急還有一個地方需要我們改進的就是插入數據的時候，上面擴容在插入數據的時候是創(chuàng)建一個哈希桶然后再調用哈希桶來插入原來哈希桶的每個數據，如果這么做的話，在新的哈希桶里面又會不斷地創(chuàng)建地節(jié)點，并且在函數結束地時候又會刪除節(jié)點，如果節(jié)點的個數非常多的話這就會導致效率低下，所以我們這里就有一個改進思路就是能不能用已有的節(jié)點來插入到新創(chuàng)建的哈希表呢？答案是可以的，我們依然是創(chuàng)建一個新的哈希表然后改變其內部的大小，然后遍歷之前的老哈希表找到里面的元素并計算他在新表上的位置，然后修改其節(jié)點內部指針的指向，那么這里的代碼如下：
if (_n / _tables.size() == 1)//平衡因子為1就更新
{
/*vector<Node*> newBH;;
newBH.resize(_n * 2);
for (auto& cur : _tables)
{
while (cur)
{
newBH.insert(cur->_kv);
cur = cur->_next;
}
}
_tables.swap(newBH._tables);*/
vector<Node*> newBH;
newBH._tables.resize(__stl_next_prime(_tables.size()));
for (int i = 0; i < _tables.size(); i++)
{
Node* cur = _tables[i];
while (cur)
{
Node* next = cur->_next;
size_t pos = Hash()(cur->_kv.first);
cur->_next = newBH[pos];
newBH[pos] = cur;
cur = next;
}
_tables[i] = nullptr;
}
}到此這篇關于c++實現(xiàn)哈希桶的步驟的文章就介紹到這了,更多相關c++ 哈希桶內容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家！
相關文章
文章介紹了C++中的vtordisp機制,用于在虛繼承和虛函數結合的場景下,確保構造函數和析構函數中對虛基類指針的正確調整,文章詳細解釋了vtordisp的基本概念、應用場景以及編譯器相關的考慮,感興趣的朋友一起看看吧2025-01-01
本文主要介紹了C++?高精度乘法運算的實現(xiàn)，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧2023-01-01
結構體用點，結構體指針用箭頭，簡單的說，就是一個快捷方式，一個語法糖，這篇文章主要介紹了C語言中.與-＞的區(qū)別及用法,需要的朋友可以參考下2023-05-05
這篇文章主要介紹了C語言中qsort函數的用法實例詳解的相關資料,希望通過本文能幫助到大家，讓大家理解掌握這部分內容，需要的朋友可以參考下2017-10-10
這篇文章主要給大家介紹了關于Qt學習教程之對話框消失動畫效果的相關資料，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧2018-07-07
類和對象是兩種以計算機為載體的計算機語言的合稱。對象是對客觀事物的抽象，類是對對象的抽象。類是一種抽象的數據類型；變量就是可以變化的量，存儲在內存中—個可以擁有在某個范圍內的可變存儲區(qū)域2023-02-02
這篇文章主要給大家介紹了關于Qt無邊框窗口拖拽和陰影的實現(xiàn)方法，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧2020-11-11
本篇文章是對C語言中高斯消元法的使用進行了詳細的分析介紹，需要的朋友參考下2013-05-05
這篇文章主要介紹了15種?C++?常見報錯,本文通過實例代碼給大家講解的非常詳細，對大家的學習或工作具有一定的參考借鑒價值，需要的朋友可以參考下2023-01-01
VC創(chuàng)建進程CreateProcess的方法
這篇文章主要介紹了VC創(chuàng)建進程CreateProcess的方法,涉及VC操作進程的基本技巧,需要的朋友可以參考下2015-05-05