一文詳細(xì)講解C++精妙的哈希算法
一、哈希結(jié)構(gòu)
1、哈希概念
AVL樹、紅黑樹等平衡樹搜索效率取決于搜索過程中的比較次數(shù)，一般時(shí)間復(fù)雜度為O(logN)，雖然平衡樹的搜索效率已經(jīng)很快，但如果可以不經(jīng)過任何比較或者常數(shù)次的比較后就能搜索到我們要找的元素，會(huì)極大的提高效率。
哈希結(jié)構(gòu)，是一種通過特定函數(shù)（哈希函數(shù)）將關(guān)鍵碼映射到表中的一個(gè)位置，那么在查找時(shí)通過該函數(shù)就可以很快的找到該元素。
但是上述的映射方法存在一個(gè)問題，就是不同的元素可能會(huì)映射到同一個(gè)位置，這時(shí)就發(fā)生了哈希沖突（也叫哈希碰撞），解決哈希沖突，是實(shí)現(xiàn)哈希結(jié)構(gòu)的關(guān)鍵。
2、哈希函數(shù)
引起哈希沖突的一個(gè)原因可能是：哈希函數(shù)設(shè)計(jì)不合理。哈希函數(shù)的設(shè)計(jì)要保證高效性和可靠性：
- 一致性：確保相同的輸入總是產(chǎn)生相同的輸出哈希值
- 均勻分布：哈希值應(yīng)在哈希表的地址空間中盡可能均勻分布，以減少哈希沖突
- 計(jì)算效率：哈希函數(shù)應(yīng)簡(jiǎn)單且計(jì)算快速，以便在實(shí)際應(yīng)用中能夠快速執(zhí)行
- 沖突最小化：設(shè)計(jì)哈希函數(shù)時(shí)應(yīng)盡量減少哈希沖突的發(fā)生，以提高哈希表的性能
| 常見哈希函數(shù)：哈希函數(shù)是哈希表的核心，它決定了如何將關(guān)鍵字映射到哈希地址。
- 直接定制法：取關(guān)鍵字的某個(gè)線性函數(shù)為散列地址，Hash(Key)=A*Key+B。這種方法簡(jiǎn)單、均勻，但需要事先知道關(guān)鍵字的分布情況
- 除留余數(shù)法：取一個(gè)不大于哈希表地址數(shù)m的質(zhì)數(shù)p，按照哈希函數(shù)Hash(key)=key%p將關(guān)鍵碼轉(zhuǎn)換成哈希地址。這種方法實(shí)現(xiàn)簡(jiǎn)單，且當(dāng)p選擇合理時(shí)，哈希沖突的概率較低
- 平方取中法：對(duì)關(guān)鍵字進(jìn)行平方運(yùn)算，然后抽取中間的幾位作為哈希地址。這種方法適用于不知道關(guān)鍵字分布情況，且位數(shù)不是很大的場(chǎng)景
- 折疊法：將關(guān)鍵字從左到右分割成位數(shù)相等的幾部分（最后一部分位數(shù)可以短些），然后將這幾部分疊加求和，并按哈希表表長(zhǎng)取后幾位作為哈希地址。這種方法適用于關(guān)鍵字位數(shù)較多的情況
此外，還有隨機(jī)數(shù)法、數(shù)學(xué)分析法等哈希函數(shù)設(shè)計(jì)方法，可以根據(jù)具體應(yīng)用場(chǎng)景選擇合適的哈希函數(shù)。
哈希函數(shù)設(shè)計(jì)的越好，產(chǎn)生哈希沖突的可能性就越低，但是哈希沖突還是無(wú)可避免。
3、哈希沖突
解決哈希沖突的兩種常見方法是：閉散列（開放定址法）和開散列（鏈地址法）。
3.1 閉散列
當(dāng)發(fā)生哈希沖突時(shí)，如果哈希表中還有空位置，就把key存放到?jīng)_突位置的“下一個(gè)”空位置去。找下一個(gè)空位置，常見的探測(cè)方法有線性探測(cè)、二次探測(cè)和雙重散列等。
| 線性探測(cè)： 從發(fā)生沖突的位置開始，依次向后探測(cè)，直到找到下一個(gè)空位置為止。
- 插入上圖中在插入15前，通過哈希函數(shù)得到映射位置為5，但是5位置被占了，就依次向后找，在7位置找到了一個(gè)空位置將15插入。
- 刪除閉散列解決哈希沖突時(shí)，不好隨便物理刪除某個(gè)元素，可以考慮標(biāo)記的方法來(lái)偽刪除一個(gè)元素。
//每個(gè)位置都給標(biāo)記
enum State
{
EXIST,//存在
DELETE,//刪除
EMPTY//空
}
| 線性探測(cè)實(shí)現(xiàn)：
enum State
{
EXIST,
EMPTY,
DELETE
};
template<class K, class V>
struct HashData
{
pair<K, V> _kv;
State _state = EMPTY;
};
template<class K, class V>
class HashTable
{
public:
HashTable()
{
_tables.resize(10);//提前開10個(gè)位置
}
private:
vector<HashData<K, V>> _tables;
size_t _n = 0;//存儲(chǔ)元素個(gè)數(shù)
};
- 插入
關(guān)鍵碼對(duì)表的size()取模，不能對(duì)capacity()取模，因?yàn)楣１碇С?code>[]訪問，只能訪問下標(biāo)小于size()的元素。
散列表的載荷因子 = 表中的元素個(gè)數(shù) / 表的大小
當(dāng)載荷因子達(dá)到某個(gè)臨界值，就需要擴(kuò)容。載荷因子越大，產(chǎn)生沖突的可能性就越大，相反產(chǎn)生沖突的可能性就越小。通常載荷因子應(yīng)限制在0.7-0.8一下。
不能直接對(duì)原表進(jìn)行擴(kuò)容，無(wú)論是原地?cái)U(kuò)還是異地?cái)U(kuò)，都會(huì)把原數(shù)據(jù)拷貝過來(lái)。但是擴(kuò)完容后元素的相對(duì)位置可能會(huì)發(fā)生改變，原本沖突的元素?cái)U(kuò)完容后就不沖突了，所以直接對(duì)原表進(jìn)行擴(kuò)容是不行的。
擴(kuò)容有兩種方法：
- 方法一：新建原表兩倍大小的
vector，遍歷原表的元素重新映射到vector中，再將新建的vector和原表的vector交換。 - 方法二：因?yàn)榉椒ㄒ贿€需要重寫一遍映射過程，所以可以直接新建一個(gè)哈希表，遍歷原表的元素插入到新建的哈希表中，最后交換兩個(gè)哈希表的
vector，這個(gè)方法的好處是新建的哈希表復(fù)用了原哈希表的Insert。
方法一我們就不實(shí)現(xiàn)了，直接用更好一點(diǎn)的方法二：
bool Insert(const pair<K, V>& kv)
{
if (_n * 10 / _tables.size() >= 7)//載荷因子達(dá)到一定的值進(jìn)行擴(kuò)容
{
HashTable<K, V> newHT;
newHT._tables.resize(2 * _tables.size());
for (int i = 0; i < _tables.size(); i++)
{
if (_tables[i]._state == EXIST)
{
newHT.Insert(_tables[i]._kv);
}
}
_tables.swap(newHT._tables);
}
size_t hashi = kv.first % _tables.size();//確定映射位置
while (_tables[hashi]._state == EXIST)
{
++hashi;
hashi %= _tables.size();//防止越界
}
_tables[hashi]._kv = kv;
_tables[hashi]._state = EXIST;
++_n;
return true;
}
但是現(xiàn)在還有個(gè)問題，在上面的代碼中要求我們的key可以取模，也就是key只能是無(wú)符號(hào)整數(shù)，如果是浮點(diǎn)數(shù)、字符串等上面的代碼就行不通，所以還需要想辦法將可能出現(xiàn)的浮點(diǎn)數(shù)、字符串等類型的key轉(zhuǎn)換為無(wú)符號(hào)的整型再做映射。
像浮點(diǎn)數(shù)等可以直接強(qiáng)轉(zhuǎn)為無(wú)符號(hào)整型，可以考慮用仿函數(shù)解決。字符串一般不能直接強(qiáng)轉(zhuǎn)為無(wú)符號(hào)整型，我們可以對(duì)字符串特殊處理，也就是模版特化，將字符串中字符的ASCII碼值加起來(lái)作為映射值。
但是這里還有個(gè)問題，將字符串中字符的ASCII碼值加起來(lái)也可能沖突，比如相同的字符按不同的順序組合起來(lái)的字符串。不過好在有專門的字符串哈希函數(shù)（字符串哈希函數(shù)有好多種，這里使用其中一種：BKDR Hash函數(shù)），這里就不做過多介紹了，有興趣的同學(xué)請(qǐng)百度了解。他給出的解決辦法是字符每次相加之前+31（31、131、1313、13131…都行）來(lái)盡可能減少?zèng)_突。
template<class K>
struct HashFunc //key強(qiáng)轉(zhuǎn)為整型
{
size_t operator()(const K& key)
{
return (size_t)key;
}
};
//對(duì)string類型特殊處理
template<>
struct HashFunc<string>
{
size_t operator()(const string& s)
{
size_t hash = 0;
for (auto e : s)
{
hash = hash * 31 + e;
}
return hash;
}
};
- 刪除
刪除指定的元素，只需要找到該元素的位置，將該位置的狀態(tài)標(biāo)記為DELETE即可。
bool Erase(const K& key)
{
HashData<K, V>* ret = Find(key);
if (ret == nullptr)
{
return false;
}
else
{
ret->_state = DELETE;
return true;
}
}
- 查找
查找過程需要注意的是，當(dāng)在表中找到被查找的元素時(shí)還要判斷此位置是否被標(biāo)記為已刪除，因?yàn)閯h除操作我們并沒有實(shí)際物理上的刪除某個(gè)元素。
HashData<K, V>* Find(const K& key)
{
Hash hs;
size_t hashi = hs(key) % _tables.size();
while (_tables[hashi]._state != EMPTY)
{
if (_tables[hashi]._state != DELETE
&& _tables[hashi]._kv.first == key)
{
return &_tables[hashi];
}
++hashi;
hashi %= _tables.size();
}
return nullptr;
}
線性探測(cè)的優(yōu)點(diǎn)是簡(jiǎn)單好理解，缺點(diǎn)是數(shù)據(jù)容易堆積，查找時(shí)可能需要多次比較。
閉散列 / 開放定址法我們就先實(shí)現(xiàn)到這里，它是一種零和博弈，和下面將要介紹的開散列 / 鏈地址法對(duì)比還是稍遜一籌。
3.2 開散列
通過哈希函數(shù)計(jì)算散列地址，具有相同映射地址的元素歸于同一子集合，每一個(gè)子集合稱為一個(gè)哈希桶，各個(gè)桶中的元素通過一個(gè)單鏈表鏈接起來(lái)，哈希表中存各鏈表的頭節(jié)點(diǎn)。開散列每個(gè)桶中存放的都是產(chǎn)生哈希沖突的元素。
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 hash = 0;
for (auto e : s)
{
hash = hash * 31 + e;
}
return hash;
}
};
template<class K, class V>
struct HashNode
{
HashNode(const pair<K, V>& kv)
:_kv(kv)
,_next(nullptr)
{}
pair<K, V> _kv;
HashNode<K, V>* _next;
};
template<class K, class V, class Hash = HashFunc<K>>
class HashTable
{
typedef HashNode<K, V> Node;
public:
HashTable()
{
_tables.resize(10, nullptr);
}
~HashTable()
{
for (int i = 0; i < _tables.size(); i++)
{
Node* pcur = _tables[i];
while (pcur)
{
Node* next = pcur->_next;
delete pcur;
pcur = next;
}
_tables[i] = nullptr;
}
}
private:
vector<Node*> _tables;
size_t _n = 0;
};
- 插入
bool Insert(const pair<K, V>& kv)
{
size_t hashi = kv.first % _tables.size();
//負(fù)載因子==1就擴(kuò)容
if (_n == _tables.size())
{
HashTable<K, V> newHT;
newHT._tables.resize(2 * _tables.size(), nullptr);
for (int i = 0; i < _tables.size(); i++)
{
Node* pcur = _tables[i];
while (pcur)
{
newHT.Insert(pcur->_kv);
pcur = pcur->_next;
}
}
_tables.swap(newHT._tables);
}
Node* newnode = new Node(kv);
//頭插
newnode->_next = _tables[hashi];
_tables[hashi] = newnode;
++_n;
return true;
}
上面的擴(kuò)容過程雖然可行，但是不夠好。假如原表中有很多個(gè)節(jié)點(diǎn)，新建新表擴(kuò)容后復(fù)用Insert就要new很多個(gè)節(jié)點(diǎn)再插入，這實(shí)際上是很有消耗的。因?yàn)樵?jié)點(diǎn)和新new的節(jié)點(diǎn)并無(wú)差別，所以可以直接將原表中的節(jié)點(diǎn)拿下來(lái)頭插到新表中，這樣就不用再new新節(jié)點(diǎn)。
| 優(yōu)化：
bool Insert(const pair<K, V>& kv)
{
size_t hashi = hs(kv.first) % _tables.size();
//負(fù)載因子==1就擴(kuò)容
if (_n == _tables.size())
{
vector<Node*> newtables(2 * _tables.size(), nullptr);
for (int i = 0; i < _tables.size(); i++)
{
Node* pcur = _tables[i];
while (pcur)
{
Node* next = pcur->_next;
size_t hashi = pcur->_kv.first % newtables.size();
pcur->_next = newtables[hashi];
newtables[hashi] = pcur;
pcur = next;
}
_tables[i] = nullptr;
}
_tables.swap(newtables);
}
Node* newnode = new Node(kv);
//頭插
newnode->_next = _tables[hashi];
_tables[hashi] = newnode;
++_n;
return true;
}
- 刪除
學(xué)習(xí)過鏈表我們知道，單鏈表的頭刪和其他位置的刪除需要分開處理，因?yàn)槠渌恢脛h除節(jié)點(diǎn)后要將前后節(jié)點(diǎn)鏈接起來(lái)，而單鏈表的頭節(jié)點(diǎn)沒有前一個(gè)節(jié)點(diǎn)。
bool Erase(const K& key)
{
Hash hs;
size_t hashi = hs(key) % _tables.size();
Node* pcur = _tables[hashi];
Node* prev = nullptr;
while (pcur)
{
if (pcur->_kv.first == key)
{
if (prev == nullptr)
{
_tables[hashi] = pcur->_next;
}
else
{
prev->_next = pcur->_next;
}
delete pcur;
--_n;
return true;
}
prev = pcur;
pcur = pcur->_next;
}
return false;
}
4、完整代碼
namespace open_address
{
enum State
{
EXIST,
EMPTY,
DELETE
};
template<class K, class V>
struct HashData
{
pair<K, V> _kv;
State _state = EMPTY;
};
template<class K>
struct HashFunc //key強(qiáng)轉(zhuǎn)為整型
{
size_t operator()(const K& key)
{
return (size_t)key;
}
};
//對(duì)string類型特殊處理
template<>
struct HashFunc<string>
{
size_t operator()(const string& s)
{
size_t hash = 0;
for (auto e : s)
{
hash = hash * 31 + e;
}
return hash;
}
};
template<class K, class V, class Hash = HashFunc<K>>
class HashTable
{
public:
HashTable()
{
_tables.resize(10);//提前開10個(gè)位置
}
bool Insert(const pair<K, V>& kv)
{
//去冗余
if (Find(kv.first))
{
return false;
}
if (_n * 10 / _tables.size() >= 7)//載荷因子達(dá)到一定的值進(jìn)行擴(kuò)容
{
HashTable<K, V, Hash> newHT;
newHT._tables.resize(2 * _tables.size());
for (int i = 0; i < _tables.size(); i++)
{
if (_tables[i]._state == EXIST)
{
newHT.Insert(_tables[i]._kv);
}
}
_tables.swap(newHT._tables);
}
Hash hs;
size_t hashi = hs(kv.first) % _tables.size();//確定映射位置
while (_tables[hashi]._state == EXIST)
{
++hashi;
hashi %= _tables.size();//防止越界
}
_tables[hashi]._kv = kv;
_tables[hashi]._state = EXIST;
++_n;
return true;
}
HashData<K, V>* Find(const K& key)
{
Hash hs;
size_t hashi = hs(key) % _tables.size();
while (_tables[hashi]._state != EMPTY)
{
if (_tables[hashi]._state != DELETE && _tables[hashi]._kv.first == key)
{
return &_tables[hashi];
}
++hashi;
hashi %= _tables.size();
}
return nullptr;
}
bool Erase(const K& key)
{
HashData<K, V>* ret = Find(key);
if (ret == nullptr)
{
return false;
}
else
{
ret->_state = DELETE;
return true;
}
}
private:
vector<HashData<K, V>> _tables;
size_t _n = 0;//存儲(chǔ)元素個(gè)數(shù)
};
}
namespace close_address
{
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 hash = 0;
for (auto e : s)
{
hash = hash * 31 + e;
}
return hash;
}
};
template<class K, class V>
struct HashNode
{
HashNode(const pair<K, V>& kv)
:_kv(kv)
, _next(nullptr)
{}
pair<K, V> _kv;
HashNode<K, V>* _next;
};
template<class K, class V, class Hash = HashFunc<K>>
class HashTable
{
typedef HashNode<K, V> Node;
public:
HashTable()
{
_tables.resize(10, nullptr);
}
~HashTable()
{
for (int i = 0; i < _tables.size(); i++)
{
Node* pcur = _tables[i];
while (pcur)
{
Node* next = pcur->_next;
delete pcur;
pcur = next;
}
_tables[i] = nullptr;
}
}
bool Insert(const pair<K, V>& kv)
{
Hash hs;
size_t hashi = hs(kv.first) % _tables.size();
負(fù)載因子==1就擴(kuò)容
//if (_n == _tables.size())
//{
// HashTable<K, V> newHT;
// newHT._tables.resize(2 * _tables.size(), nullptr);
// for (int i = 0; i < _tables.size(); i++)
// {
// Node* pcur = _tables[i];
// while (pcur)
// {
// newHT.Insert(pcur->_kv);
// pcur = pcur->_next;
// }
// }
// _tables.swap(newHT._tables);
//}
//負(fù)載因子==1就擴(kuò)容
if (_n == _tables.size())
{
vector<Node*> newtables(2 * _tables.size(), nullptr);
for (int i = 0; i < _tables.size(); i++)
{
Node* pcur = _tables[i];
while (pcur)
{
Node* next = pcur->_next;//記錄下一個(gè)節(jié)點(diǎn)
size_t hashi = hs(pcur->_kv.first) % newtables.size();//映射新表的相對(duì)位置
pcur->_next = newtables[hashi];//頭插
newtables[hashi] = pcur;
pcur = next;
}
_tables[i] = nullptr;
}
_tables.swap(newtables);
}
Node* newnode = new Node(kv);
//頭插
newnode->_next = _tables[hashi];
_tables[hashi] = newnode;
++_n;
return true;
}
Node* Find(const K& key)
{
Hash hs;
size_t hashi = hs(key) % _tables.size();
Node* pcur = _tables[hashi];
while (pcur)
{
if (key == pcur->_kv.first)
{
return pcur;
}
pcur = pcur->_next;
}
return nullptr;
}
bool Erase(const K& key)
{
Hash hs;
size_t hashi = hs(key) % _tables.size();
Node* pcur = _tables[hashi];
Node* prev = nullptr;
while (pcur)
{
if (pcur->_kv.first == key)
{
if (prev == nullptr)
{
_tables[hashi] = pcur->_next;
}
else
{
prev->_next = pcur->_next;
}
delete pcur;
--_n;
return true;
}
prev = pcur;
pcur = pcur->_next;
}
return false;
}
private:
vector<Node*> _tables;
size_t _n = 0;
};
}總結(jié)
到此這篇關(guān)于C++哈希算法的文章就介紹到這了,更多相關(guān)C++哈希算法內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
在C++中，并不提倡使用#define定義一個(gè)常量。#define本質(zhì)上是一個(gè)預(yù)處理器指令，它僅僅表示使用一個(gè)串代替別一個(gè)串而已。也就是說(shuō)，#define定義的常量從未被編譯器看到——它們?cè)诰幾g器開始處理源碼之前就被移走了2015-08-08
一文搞懂C++中的四種強(qiáng)制類型轉(zhuǎn)換
很多朋友向小編了解C語(yǔ)言中怎么進(jìn)行強(qiáng)制類型轉(zhuǎn)換呢？在這小編告訴大家強(qiáng)制類型轉(zhuǎn)換可以分為兩種，一種是隱式類型轉(zhuǎn)換一種是顯示類型轉(zhuǎn)換，下面通過示例代碼給大家介紹下，需要的朋友參考下吧2021-07-07
這篇文章主要介紹了C++ 匈牙利算法案例分析詳解,本篇文章通過簡(jiǎn)要的案例,講解了該項(xiàng)技術(shù)的了解與使用,以下就是詳細(xì)內(nèi)容,需要的朋友可以參考下2021-08-08
本文主要介紹了c++實(shí)現(xiàn)堆排序的示例代碼，文中通過示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧2023-02-02
這篇文章主要介紹了MFC實(shí)現(xiàn)全屏功能的代碼,對(duì)于學(xué)習(xí)MFC有一定的借鑒價(jià)值,需要的朋友可以參考下2014-07-07
函數(shù)的返回值是指函數(shù)被調(diào)用之后,執(zhí)行函數(shù)體中的程序段所取得的并返回給主調(diào)函數(shù)的值,下面這篇文章主要給大家介紹了關(guān)于C語(yǔ)言函數(shù)返回值的相關(guān)資料,需要的朋友可以參考下2022-01-01
Qt帶參數(shù)的信號(hào)和槽函數(shù)舉例詳解
信號(hào)槽的設(shè)計(jì)旨在實(shí)現(xiàn)控件和處理邏輯的解耦合,但在實(shí)際開發(fā)中,一對(duì)一的關(guān)系更為常見,這篇文章主要介紹了Qt帶參數(shù)的信號(hào)和槽函數(shù)的相關(guān)資料,需要的朋友可以參考下2025-03-03
這篇文章主要為大家詳細(xì)介紹了C語(yǔ)言實(shí)現(xiàn)單詞小助手，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2019-10-10
C語(yǔ)言深入分析數(shù)組指針和指針數(shù)組的應(yīng)用
在C語(yǔ)言和C++等語(yǔ)言中，數(shù)組元素全為指針變量的數(shù)組稱為指針數(shù)組，指針數(shù)組中的元素都必須具有相同的存儲(chǔ)類型、指向相同數(shù)據(jù)類型的指針變量。指針數(shù)組比較適合用來(lái)指向若干個(gè)字符串，使字符串處理更加方便、靈活2022-04-04
Linux?C/C++實(shí)現(xiàn)網(wǎng)絡(luò)流量分析工具
網(wǎng)絡(luò)流量分析的原理基于對(duì)數(shù)據(jù)包的捕獲、解析和統(tǒng)計(jì)分析,通過對(duì)網(wǎng)絡(luò)流量的細(xì)致觀察和分析,幫助管理員了解和優(yōu)化網(wǎng)絡(luò)的性能,本文將通過C++實(shí)現(xiàn)網(wǎng)絡(luò)流量分析工具,有需要的可以參考下2023-10-10