柚子快報(bào)邀請(qǐng)碼778899分享：【C++】精妙的哈希算法

http://yzkb.51969.com/

?個(gè)人主頁(yè)：@小羊

?所屬專(zhuān)欄：C++

很榮幸您能閱讀我的文章，誠(chéng)請(qǐng)?jiān)u論指點(diǎn)，歡迎歡迎 ~

目錄

一、哈希結(jié)構(gòu)1、哈希概念2、哈希函數(shù)3、哈希沖突3.1 閉散列3.2 開(kāi)散列

4、完整代碼

一、哈希結(jié)構(gòu)

1、哈希概念

AVL樹(shù)、紅黑樹(shù)等平衡樹(shù)搜索效率取決于搜索過(guò)程中的比較次數(shù)，一般時(shí)間復(fù)雜度為O(logN)，雖然平衡樹(shù)的搜索效率已經(jīng)很快，但如果可以不經(jīng)過(guò)任何比較或者常數(shù)次的比較后就能搜索到我們要找的元素，會(huì)極大的提高效率。

哈希結(jié)構(gòu)，是一種通過(guò)特定函數(shù)（哈希函數(shù)）將關(guān)鍵碼映射到表中的一個(gè)位置，那么在查找時(shí)通過(guò)該函數(shù)就可以很快的找到該元素。

但是上述的映射方法存在一個(gè)問(wèn)題，就是不同的元素可能會(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ā)生，以提高哈希表的性能

| 常見(jiàn)哈希函數(shù)： 哈希函數(shù)是哈希表的核心，它決定了如何將關(guān)鍵字映射到哈希地址。

直接定制法：取關(guān)鍵字的某個(gè)線(xiàn)性函數(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、哈希沖突

解決哈希沖突的兩種常見(jiàn)方法是：閉散列（開(kāi)放定址法）和開(kāi)散列（鏈地址法）。

3.1 閉散列

當(dāng)發(fā)生哈希沖突時(shí)，如果哈希表中還有空位置，就把key存放到?jīng)_突位置的“下一個(gè)”空位置去。找下一個(gè)空位置，常見(jiàn)的探測(cè)方法有線(xiàn)性探測(cè)、二次探測(cè)和雙重散列等。

| 線(xiàn)性探測(cè)： 從發(fā)生沖突的位置開(kāi)始，依次向后探測(cè)，直到找到下一個(gè)空位置為止。

插入 上圖中在插入15前，通過(guò)哈希函數(shù)得到映射位置為5，但是5位置被占了，就依次向后找，在7位置找到了一個(gè)空位置將15插入。刪除 閉散列解決哈希沖突時(shí)，不好隨便物理刪除某個(gè)元素，可以考慮標(biāo)記的方法來(lái)偽刪除一個(gè)元素。

//每個(gè)位置都給標(biāo)記

enum State

{

EXIST,//存在

DELETE,//刪除

EMPTY//空

}

| 線(xiàn)性探測(cè)實(shí)現(xiàn)：

enum State

{

EXIST,

EMPTY,

DELETE

};

template

struct HashData

{

pair _kv;

State _state = EMPTY;

};

template

class HashTable

{

public:

HashTable()

{

_tables.resize(10);//提前開(kāi)10個(gè)位置

}

private:

vector> _tables;

size_t _n = 0;//存儲(chǔ)元素個(gè)數(shù)

};

插入

關(guān)鍵碼對(duì)表的size()取模，不能對(duì)capacity()取模，因?yàn)楣１碇С諿]訪(fǎng)問(wèn)，只能訪(fǎng)問(wèn)下標(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ù)拷貝過(guò)來(lái)。但是擴(kuò)完容后元素的相對(duì)位置可能會(huì)發(fā)生改變，原本沖突的元素?cái)U(kuò)完容后就不沖突了，所以直接對(duì)原表進(jìn)行擴(kuò)容是不行的。

擴(kuò)容有兩種方法：

方法一：新建原表兩倍大小的vector，遍歷原表的元素重新映射到vector中，再將新建的vector和原表的vector交換。方法二：因?yàn)榉椒ㄒ贿€需要重寫(xiě)一遍映射過(guò)程，所以可以直接新建一個(gè)哈希表，遍歷原表的元素插入到新建的哈希表中，最后交換兩個(gè)哈希表的vector，這個(gè)方法的好處是新建的哈希表復(fù)用了原哈希表的Insert。

方法一我們就不實(shí)現(xiàn)了，直接用更好一點(diǎn)的方法二：

bool Insert(const pair& kv)

{

if (_n * 10 / _tables.size() >= 7)//載荷因子達(dá)到一定的值進(jìn)行擴(kuò)容

{

HashTable 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è)問(wèn)題，在上面的代碼中要求我們的key可以取模，也就是key只能是無(wú)符號(hào)整數(shù)，如果是浮點(diǎn)數(shù)、字符串等上面的代碼就行不通，所以還需要想辦法將可能出現(xiàn)的浮點(diǎn)數(shù)、字符串等類(lèi)型的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è)問(wèn)題，將字符串中字符的ASCII碼值加起來(lái)也可能沖突，比如相同的字符按不同的順序組合起來(lái)的字符串。不過(guò)好在有專(zhuān)門(mén)的字符串哈希函數(shù)（字符串哈希函數(shù)有好多種，這里使用其中一種：BKDR Hash函數(shù)），這里就不做過(guò)多介紹了，有興趣的同學(xué)請(qǐng)百度了解。他給出的解決辦法是字符每次相加之前+31（31、131、1313、13131…都行）來(lái)盡可能減少?zèng)_突。

template

struct HashFunc //key強(qiáng)轉(zhuǎn)為整型

{

size_t operator()(const K& key)

{

return (size_t)key;

}

};

//對(duì)string類(lèi)型特殊處理

template<>

struct HashFunc

{

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* ret = Find(key);

if (ret == nullptr)

{

return false;

}

else

{

ret->_state = DELETE;

return true;

}

}

查找

查找過(guò)程需要注意的是，當(dāng)在表中找到被查找的元素時(shí)還要判斷此位置是否被標(biāo)記為已刪除，因?yàn)閯h除操作我們并沒(méi)有實(shí)際物理上的刪除某個(gè)元素。

HashData* 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;

}

線(xiàn)性探測(cè)的優(yōu)點(diǎn)是簡(jiǎn)單好理解，缺點(diǎn)是數(shù)據(jù)容易堆積，查找時(shí)可能需要多次比較。 閉散列 / 開(kāi)放定址法我們就先實(shí)現(xiàn)到這里，它是一種零和博弈，和下面將要介紹的開(kāi)散列 / 鏈地址法對(duì)比還是稍遜一籌。

3.2 開(kāi)散列

通過(guò)哈希函數(shù)計(jì)算散列地址，具有相同映射地址的元素歸于同一子集合，每一個(gè)子集合稱(chēng)為一個(gè)哈希桶，各個(gè)桶中的元素通過(guò)一個(gè)單鏈表鏈接起來(lái)，哈希表中存各鏈表的頭節(jié)點(diǎn)。開(kāi)散列每個(gè)桶中存放的都是產(chǎn)生哈希沖突的元素。

template

struct HashFunc

{

size_t operator()(const K& key)

{

return (size_t)key;

}

};

template<>

struct HashFunc

{

size_t operator()(const string& s)

{

size_t hash = 0;

for (auto e : s)

{

hash = hash * 31 + e;

}

return hash;

}

};

template

struct HashNode

{

HashNode(const pair& kv)

:_kv(kv)

,_next(nullptr)

{}

pair _kv;

HashNode* _next;

};

template>

class HashTable

{

typedef HashNode 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 _tables;

size_t _n = 0;

};

插入

bool Insert(const pair& kv)

{

size_t hashi = kv.first % _tables.size();

//負(fù)載因子==1就擴(kuò)容

if (_n == _tables.size())

{

HashTable 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ò)容過(guò)程雖然可行，但是不夠好。假如原表中有很多個(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& kv)

{

size_t hashi = hs(kv.first) % _tables.size();

//負(fù)載因子==1就擴(kuò)容

if (_n == _tables.size())

{

vector 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í)過(guò)鏈表我們知道，單鏈表的頭刪和其他位置的刪除需要分開(kāi)處理，因?yàn)槠渌恢脛h除節(jié)點(diǎn)后要將前后節(jié)點(diǎn)鏈接起來(lái)，而單鏈表的頭節(jié)點(diǎn)沒(méi)有前一個(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

struct HashData

{

pair _kv;

State _state = EMPTY;

};

template

struct HashFunc //key強(qiáng)轉(zhuǎn)為整型

{

size_t operator()(const K& key)

{

return (size_t)key;

}

};

//對(duì)string類(lèi)型特殊處理

template<>

struct HashFunc

{

size_t operator()(const string& s)

{

size_t hash = 0;

for (auto e : s)

{

hash = hash * 31 + e;

}

return hash;

}

};

template>

class HashTable

{

public:

HashTable()

{

_tables.resize(10);//提前開(kāi)10個(gè)位置

}

bool Insert(const pair& kv)

{

//去冗余

if (Find(kv.first))

{

return false;

}

if (_n * 10 / _tables.size() >= 7)//載荷因子達(dá)到一定的值進(jìn)行擴(kuò)容

{

HashTable 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* 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* ret = Find(key);

if (ret == nullptr)

{

return false;

}

else

{

ret->_state = DELETE;

return true;

}

}

private:

vector> _tables;

size_t _n = 0;//存儲(chǔ)元素個(gè)數(shù)

};

}

namespace close_address

{

template

struct HashFunc

{

size_t operator()(const K& key)

{

return (size_t)key;

}

};

template<>

struct HashFunc

{

size_t operator()(const string& s)

{

size_t hash = 0;

for (auto e : s)

{

hash = hash * 31 + e;

}

return hash;

}

};

template

struct HashNode

{

HashNode(const pair& kv)

:_kv(kv)

, _next(nullptr)

{}

pair _kv;

HashNode* _next;

};

template>

class HashTable

{

typedef HashNode 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& kv)

{

Hash hs;

size_t hashi = hs(kv.first) % _tables.size();

負(fù)載因子==1就擴(kuò)容

//if (_n == _tables.size())

//{

// HashTable 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 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 _tables;

size_t _n = 0;

};

}

本篇文章的分享就到這里了，如果您覺(jué)得在本文有所收獲，還請(qǐng)留下您的三連支持哦~

柚子快報(bào)邀請(qǐng)碼778899分享：【C++】精妙的哈希算法

http://yzkb.51969.com/

參考鏈接