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