<em>Mac</em>Book项目 2009年学校开始实施<em>Mac</em>Book项目,所有师生配备一本<em>Mac</em>Book,并同步更新了校园无线网络。学校每周进行电脑技术更新,每月发送技术支持资料,极大改变了教学及学习方式。因此2011
2021-06-01 09:32:01
C語言雜湊表概念超詳細講解
2023-02-10 06:01:56
1. 雜湊概念
雜湊其實在學排序時已經用過了，就是計數排序。計數排序也是用的一種對映關係。
比如對此陣列進行 計數排序 ：1 1 9 9 9 3 3 8 8
我用的是絕對對映 ，所以開闢的陣列空間 它的大小 必須 能對映到 最大的元素。
但是 對於雜湊來講，可以用決定對映嘛？當然不可以，如果是絕對對映會造成很大的空間浪費。所以 雜湊 用的是 取模的方式來存 資料。
比如 ： 雜湊表 的空間 我給定 只能存放 10個元素
存進來的數 對10進行取模 ，那麼必定可以存方到 這個雜湊表中。
比如：存 100 ，它對10取模得 0，那它就存在第一個位置；存 52 ，它對10進行取模得 2，那它就存到 下標為 2的位置。
也就是說 無論多大的資料，都可以存到雜湊表中。但是 有兩個 問題：
- 資料都能進行取模嗎？假如我要求雜湊表中存的是一個字串，字串不能進行取模運算，該怎麼辦？這就是資料可否雜湊的問題，我們要把存進雜湊表的資料，變為可雜湊資料。
- 如果我存的是 4，下一次我要存的是 14。由於 4的位置已經被佔了，我存的 14 該存放到何處？要是直接存，就意味著前面存的 4 會被覆蓋，造成資料丟失。這就是雜湊衝突問題。
2. 雜湊衝突
造成了雜湊衝突，得解決雜湊衝突問題。
這裡給出兩種解決手段：
閉雜湊：也叫開放定址法，當發生雜湊衝突時，如果雜湊表未被裝滿，說明在雜湊表中必然還有空位置，那麼可以把key存放到衝突位置中的“下一個” 空位置中去。
它相當於 如果我本來要存的位置，已經被佔了，那麼我就要在雜湊表中找一個空位置存放。開雜湊：開雜湊法又叫鏈地址法(開鏈法)，首先對關鍵碼集合用雜湊函數計算雜湊地址，具有相同地址的關鍵碼歸於同一子集合，每一個子集合稱為一個桶，各個桶中的元素通過一個單連結串列連結起來，各連結串列的頭結點儲存在雜湊表中。
這種辦法是常用的，它相當於 雜湊表 每個位置 都存的是一個雜湊桶，如果傳送雜湊衝突，直接就放在雜湊桶裡就行了。
3. 雜湊實現
雜湊表其實就是一個陣列，陣列中存的是節點資料，發生雜湊衝突後，採用的是往後找空位置的方法。
圖解：
(1) 10 % 6 == 4,所以插入到下標為4的位置
(2) 20%6==2,插入到下標為2的位置
(3)12%6 == 0,插入到下標為0的位置。
(4)22%6 == 4，插入到下標為4的位置，發現已經有資料了，所以向後找空位置。
(5)44%6 == 2，插入到下標為2的位置，發現已經有資料了，所以向後找空位置。
雜湊桶其實就是一個陣列，陣列中存的是節點連結串列，發生雜湊衝突後，是直接插入到節點連結串列中。
如果是雜湊桶，存放上面的資料，是什麼樣的呢？
圖解：
它相當於把發生衝突的資料 掛在了 衝突位置的下面。
3.1 閉雜湊(雜湊表)
#include<vector>
#include<iostream>
using namespace std;
namespace hash_table
{
enum status
{
Empty,
Exist,
Delete
};
template<class K,class V>
struct hashdate
{
pair<K, V> _kv;
status _status = Empty;
};
template<class K,class V>
class close_hashtable
{
typedef hashdate<K, V> Node;
private:
vector<Node> _tables;
size_t _n = 0;
public:
Node* find(const K& key)
{
if (_tables.size() == 0)
return nullptr;
size_t start = key % _tables.size();
size_t i = 0;
size_t index = start + i;
while (_tables[index]._status != Empty)
{
if (_tables[index]._kv.first == key && _tables[index]._status == Exist)
return &_tables[index];
i++;
index = start + i;
index %= _tables.size();
}
return nullptr;
}
bool erase(const K& key)
{
Node* ret = find(key);
if (ret == nullptr)
return false;
ret->_status = Delete;
_n -= 1;
return true;
}
bool insert(const pair<K,V>& kv)
{
Node* ret = find(kv.first);
if (ret)
{
return false;
}
if (_tables.size() == 0 || _n * 10 / _tables.size() >= 7)
{
size_t newsize = _tables.size() == 0 ? 10 : _tables.size() * 2;
close_hashtable<K, V> tmp;
tmp._tables.resize(newsize);
for (size_t i = 0; i < _tables.size(); i++)
{
tmp.insert(_tables[i]._kv);
}
_tables.swap(tmp._tables);
}
size_t start = kv.first % _tables.size();
size_t i = 0;
size_t index = start + i;
while (_tables[index]._status == Exist)
{
i++;
index = start + i;
index %= _tables.size();
}
_tables[index]._kv = kv;
_tables[index]._status = Exist;
_n += 1;
return true;
}
};
}以上就是閉雜湊的實現。我們來一步一步的解析以上程式碼。
(1) 用列舉常數來 標記 雜湊表中 每個位置的狀態，狀態有 空，不為空，被刪除。
大家可能會對 被刪除這個狀態產生疑問，一個位置 不就是 有資料和沒資料嗎？主要是大家想 如果 直接物理上刪除，把位置 狀態設定為 空，那麼 就會影響後面的資料。
比如：刪除 5 這個資料、
直接將 5 的位置 設定為空，那麼 15 這個資料 會受到影響。因為 對 雜湊表大小取模後，等於 5 的 不一定只有 5，還有 15，25，35。如果 將 5位置直接設定 為 空，就相當於 後面的資料中 已經沒有 15，25，35 了。具體我們往下看查詢的實現。
enum status
{
Empty,
Exist,
Delete
};
(2) 雜湊表中的資料型別，以及雜湊表的底層結構
雜湊表中的資料型別，是一個結構體 ，包括了 一個鍵值對和狀態：
template<class K,class V>
struct hashdate
{
pair<K, V> _kv;
// 預設狀態為空
status _status = Empty;
};
雜湊表的底層結構，可以是一個陣列，還得有一個 無符號整數用來處理 雜湊表中資料的個數：
typedef hashdate<K, V> Node; private: vector<Node> _tables; size_t _n = 0;
(3) 雜湊表的查詢
Node* find(const K& key)
{
if (_tables.size() == 0)
return nullptr;
size_t start = key % _tables.size();
size_t i = 0;
size_t index = start + i;
while (_tables[index]._status != Empty)
{
if (_tables[index]._kv.first == key && _tables[index]._status == Exist)
return &_tables[index];
i++;
index = start + i;
index %= _tables.size();
}
return nullptr;
}
注意： while迴圈中，它的條件是 _tables[index]._status != Empty 說明 即使當下位置狀態是 Delete 也會往後找 要查詢的資料。這也解釋了上文中所述。
找到了的條件是 (_tables[index]._kv.first == key && _tables[index]._status == Exist)
找到了返回 資料的地址，找不到 返回 空。
(4) 雜湊表的插入
bool insert(const pair<K,V>& kv)
{
// 去重
Node* ret = find(kv.first);
if (ret)
{
return false;
}
// 擴容，後面講，大家可能對這個條件有疑問
if (_tables.size() == 0 || _n * 10 / _tables.size() >= 7)
{
size_t newsize = _tables.size() == 0 ? 10 : _tables.size() * 2;
close_hashtable<K, V> tmp;
tmp._tables.resize(newsize);
for (size_t i = 0; i < _tables.size(); i++)
{
tmp.insert(_tables[i]._kv);
}
_tables.swap(tmp._tables);
}
size_t start = kv.first % _tables.size();
size_t i = 0;
size_t index = start + i;
// 找空的位置
while (_tables[index]._status == Exist)
{
i++;
index = start + i;
index %= _tables.size();
}
// 插入操作
_tables[index]._kv = kv;
_tables[index]._status = Exist;
_n += 1;
return true;
}
擴容是有說法的，首先我們要知道什麼時候需要擴容？
- 如果為空，必然需要擴容，預設給 10 個大小即可。
- 當有效資料個數 除以 陣列大小 大於等於 0.7 時，需要擴容
其實 有效資料個數 除以 陣列大小 被稱為 載荷因子，當載荷因子 大於 0.7時，就說明需要擴容了。這是大佬們搞出來的，我們還需要知道，載荷因子 越大就說明 填入雜湊表的元素越多，越可能傳送雜湊衝突。
擴容的操作，我是 建立了一個新的雜湊表，然後把原表中的資料插入到新表中。這裡還有一個坑，就是，可不可以 直接將舊錶的資料拷貝到新表中，答案是 不行。
舉個例子：
原表是 ：
新表是：
直接拷貝的話是這樣的：
看圖也懂了哈，擴容後的表 是需要重新插入資料，因為 位置 可能會傳送改變。
擴容完了，就是插入了，如果當下的位置是 Delete 或者 Eempty 那麼就可以直接插入；否則就需要向後面查詢空的位置，進行插入。
(5) 雜湊表的刪除
bool erase(const K& key)
{
Node* ret = find(key);
if (ret == nullptr)
return false;
ret->_status = Delete;
_n -= 1;
return true;
}
刪除很簡單，就是將那個位置的狀態改為 Delete，然後有效資料個數 減一 就行了。
3.1.1 閉雜湊的細節
首先，上面的雜湊表其實還有問題。
比如： 不是所有的資料都可以取模，這個問題，並沒有解決，上面實現是 直接取模。
所以還需要實現一個 將資料轉為可雜湊資料的仿函數。為什麼是仿函數呢？因為 資料型別較多，情況不一，這裡還用到了模板特化的知識，大家坐穩扶好。
template<class K>
struct Hash
{
size_t operator()(const K& key)
{
return key;
}
};
template<>
struct Hash<string>
{
size_t operator()(const string& key)
{
size_t value = 0;
for (auto ch : key)
{
value *= 31;
value += ch;
}
return value;
}
};
第二個就是模板的特化， 它的作用就是 將string物件 可以轉換 成 整型(可雜湊)。至於為什麼每次都乘以 31 ，這也是大佬的手法，因為多次測試後發現，乘以 31 會使 雜湊衝突少一些。
預設情況下，就是直接返回 key，也就是預設情況下都是可雜湊的。
如果 你要雜湊一個自定義物件，那麼還得是用模板的特化，自己處理。
所以有了仿函數之後，我們就不必擔心，傳過去的資料是否能夠 被雜湊了，靠仿函數去處理。具體怎麼用，後面會給出完整程式碼。
其次，還有一個問題，就是 線性探索和二次探索：
大家可能對這倆詞不陌生，也就是雜湊表中，發生雜湊衝突後，查詢空位置時，是連續的查詢空位置還是 平方次的跳躍的查詢。
當然是二次查詢更優秀一些，上面的程式用的是線性探索，也就是 那個 i++，它就是連續的往後查詢。為什麼呢？因為 如果是線性探索，它會比較擁擠，連續位置太多，從而引發踩踏效應，也就導致，每次來的資料，都需要去找空位置。
二次探索很簡單，把 i++ 變成 i =i *i。
3.1.2 優化後的閉雜湊
enum status
{
Empty,
Exist,
Delete
};
template<class K>
struct Hash
{
size_t operator()(const K& key)
{
return key;
}
};
template<>
struct Hash<string>
{
size_t operator()(const string& key)
{
size_t value = 0;
for (auto ch : key)
{
value *= 31;
value += ch;
}
return value;
}
};
template<class K,class V>
struct hashdate
{
pair<K, V> _kv;
status _status = Empty;
};
template<class K,class V,class Hashfunc = hash<K>>
class close_hashtable
{
typedef hashdate<K, V> Node;
private:
vector<Node> _tables;
size_t _n = 0;
public:
Node* find(const K& key)
{
if (_tables.size() == 0)
return nullptr;
Hashfunc hf;
size_t start = hf(key)% _tables.size();
size_t i = 0;
size_t index = start + i;
while (_tables[index]._status != Empty)
{
if (_tables[index]._kv.first == key && _tables[index]._status == Exist)
return &_tables[index];
i = i*i;
index = start + i;
index %= _tables.size();
}
return nullptr;
}
bool erase(const K& key)
{
Node* ret = find(key);
if (ret == nullptr)
return false;
ret->_status = Delete;
_n -= 1;
return true;
}
bool insert(const pair<K,V>& kv)
{
Node* ret = find(kv.first);
if (ret)
{
return false;
}
if (_tables.size() == 0 || _n * 10 / _tables.size() >= 7)
{
size_t newsize = _tables.size() == 0 ? 10 : _tables.size() * 2;
close_hashtable<K, V> tmp;
tmp._tables.resize(newsize);
for (size_t i = 0; i < _tables.size(); i++)
{
tmp.insert(_tables[i]._kv);
}
_tables.swap(tmp._tables);
}
Hashfunc hf;
size_t start = hf(kv.first) % _tables.size();
size_t i = 0;
size_t index = start + i;
while (_tables[index]._status == Exist)
{
i = i*i;
index = start + i;
index %= _tables.size();
}
_tables[index]._kv = kv;
_tables[index]._status = Exist;
_n += 1;
return true;
}
};3.2 擴雜湊(雜湊桶)
template<class K,class V>
struct HashNode
{
pair<K, V> _kv;
HashNode<K,V>* _next;
HashNode(const pair<K, V>& kv)
:_kv(kv),
_next(nullptr)
{
}
};
template<class K,class V,class Hashfunc = Hash<K>>
class link_hashtable
{
typedef HashNode<K, V> Node;
private:
vector<Node*> _tables;
size_t _n = 0;
public:
Node* find(const K& key)
{
if (_tables.size() == 0)
return nullptr;
Hashfunc hf;
size_t index = hf(key) % _tables.size();
Node* cur = _tables[index];
while (cur)
{
if (cur->_kv.first == key)
return cur;
else
cur = cur->_next;
}
return nullptr;
}
bool erase(const K& key)
{
Node* ret = find(key);
if (ret == nullptr)
{
return false;
}
Hashfunc hf;
size_t index = hf(key) % _tables.size();
Node* pre = nullptr;
Node* cur = _tables[index];
while (cur)
{
Node* next = cur->_next;
if (cur->_kv.first == key)
{
if (pre == nullptr)
{
_tables[index] = next;
}
else
{
pre->_next = next;
}
delete cur;
_n -= 1;
return true;
}
else
{
pre = cur;
cur = next;
}
}
return false;
}
bool insert(const pair<K,V>& kv)
{
Node* ret = find(kv.first);
if (ret)
{
return false;
}
Hashfunc hf;
if (_n == _tables.size())
{
size_t newSize = _tables.size() == 0 ? 10 : _tables.size() * 2;
vector<Node*> newTables;
newTables.resize(newSize);
for (size_t i = 0; i < _tables.size(); ++i)
{
Node* cur = _tables[i];
while (cur)
{
Node* next = cur->_next;
size_t index = hf(cur->_kv.first) % newTables.size();
// 頭插
cur->_next = newTables[index];
newTables[index] = cur;
cur = next;
}
_tables[i] = nullptr;
}
_tables.swap(newTables);
}
size_t index = hf(kv.first) % _tables.size();
Node* newnode = new Node(kv);
newnode->_next = _tables[index];
_tables[index] = newnode;
}
};
}(1) 雜湊桶的節點以及底層結構
雜湊桶的節點是一個單向連結串列，它得有資料，是一個鍵值對，還得有 下一個節點的指標。
template<class K,class V>
struct HashNode
{
pair<K, V> _kv;
HashNode<K,V>* _next;
HashNode(const pair<K, V>& kv)
:_kv(kv),
_next(nullptr)
{
}
};
雜湊桶的底層，是一個陣列，陣列中存的是節點的指標，當然還得有一個有效資料的個數，它是用於判斷是否需要擴容的。
template<class K,class V,class Hashfunc = Hash<K>>
class link_hashtable
{
typedef HashNode<K, V> Node;
private:
vector<Node*> _tables;
size_t _n = 0;
public:
}
(2) 雜湊桶的查詢
查詢也簡單呢，就是迭代往下查詢，如果找到就返回，位置的指標，找不到就返回空。
Node* find(const K& key)
{
if (_tables.size() == 0)
return nullptr;
Hashfunc hf;
size_t index = hf(key) % _tables.size();
Node* cur = _tables[index];
while (cur)
{
if (cur->_kv.first == key)
return cur;
else
cur = cur->_next;
}
return nullptr;
}
(3) 雜湊桶的插入
bool insert(const pair<K,V>& kv)
{
Node* ret = find(kv.first);
if (ret)
{
return false;
}
Hashfunc hf;
if (_n == _tables.size())
{
size_t newSize = _tables.size() == 0 ? 10 : _tables.size() * 2;
vector<Node*> newTables;
newTables.resize(newSize);
for (size_t i = 0; i < _tables.size(); ++i)
{
Node* cur = _tables[i];
while (cur)
{
Node* next = cur->_next;
size_t index = hf(cur->_kv.first) % newTables.size();
// 頭插
cur->_next = newTables[index];
newTables[index] = cur;
cur = next;
}
// 將舊桶置空
_tables[i] = nullptr;
}
_tables.swap(newTables);
}
size_t index = hf(kv.first) % _tables.size();
Node* newnode = new Node(kv);
newnode->_next = _tables[index];
_tables[index] = newnode;
}
先考慮插入的資料的key有沒有重複，如果重複了那就直接返回。其實就是個頭插，中間程式碼很多是擴容，我們先不考慮擴容，其實 插入的程式碼就是：
size_t index = hf(kv.first) % _tables.size(); Node* newnode = new Node(kv); newnode->_next = _tables[index]; _tables[index] = newnode;
擴容的話，和雜湊表同理，擴完容之後，雜湊桶的位置可能會變化，所以要自己完成重新插入工作，不過擴容的條件不再是 載荷因子 >=0.7，而是 載荷因子等於 1時才擴容。
(4) 雜湊桶的刪除
bool erase(const K& key)
{
Node* ret = find(key);
if (ret == nullptr)
{
return false;
}
Hashfunc hf;
size_t index = hf(key) % _tables.size();
// 前一個節點
Node* pre = nullptr;
//桶的第一個節點
Node* cur = _tables[index];
while (cur)
{
// 桶的下一個節點
Node* next = cur->_next;
// 找到要刪除的節點
if (cur->_kv.first == key)
{
// 頭刪
if (pre == nullptr)
{
_tables[index] = next;
}
// 中間刪或者尾刪
else
{
pre->_next = next;
}
delete cur;
_n -= 1;
return true;
}
else
{
// 往桶下面迭代
pre = cur;
cur = next;
}
}
}
一上來 先檢查要刪除的資料是否存在，存在就往下走，不存在直接返回。
然後就是 找要刪除的資料在那個桶中：
Hashfunc hf; size_t index = hf(key) % _tables.size();
再就是 在這個桶中 刪除，我們需要考慮幾件事:
- 桶中是單向連結串列，刪除的話我需要維護連結串列的關係，所以需要記錄刪除資料的前一個資料
- 要刪除的節點如果是頭節點，就不需要維護和前一個資料的關係，因為它就是第一個
- 要刪除的節點在中間或者最後，那就需要維護和前一個的關係
3.2.1 擴雜湊的細節
擴雜湊是有極端情況的，比如 我開闢的陣列大小是 10 ，插入的資料是 10，20，30，40，50，60 …… 10000000000，這些資料都插入到了一個桶裡面。
會導致雜湊桶變成這樣：
會發現，效率退化了，雜湊的查詢一般情況是O(1) ，但是這種情況下，退化成O(n)了。所以應該怎麼辦？大佬其實是給出解決方案的，就是一個桶中的元素超過了某一個量，那麼就會將這個桶中的資料用紅黑樹組織起來，對於這個量jave和C++還不一樣。
這就是所謂的桶中種樹。
但是上面的雜湊桶，我沒有支援這種高階操作，我覺得只要瞭解這個事情就行了，至於實現，也是可以的，但是對於我們要學習雜湊，沒太大幫助。
4. 雜湊表和雜湊桶的比較
雜湊桶處理溢位，需要增設連結指標，似乎增加了儲存開銷。
事實上： 由於雜湊表必須保持大量的空閒空間以確保搜尋效率，如二次探查法要求裝載因子a <= 0.7，而表項所佔空間又比指標大的多，所以使用鏈地址法反而比開地址法節省儲存空間。
雜湊表處理雜湊衝突用的是搶佔別的位置，可能會導致資料比較阻塞，也就是每進來一個資料都需要去搶佔別人的位置。
雜湊桶處理雜湊衝突用的是在衝突位置，增加鏈節點的方法，但是有可能造成，單向連結串列太長從而影響效率，所以需要將單向連結串列變為紅黑樹管理起來。
5. 結尾語
學完雜湊，能幹什麼？說實話雜湊很重要，學資料結構，你說你不會雜湊，那麼就相當於你白學資料結構了，就是這麼誇張哈，以後工作也會大量用到雜湊的。所以大家加油。在我的下一篇文章中，會利用雜湊桶去實現unordered_map和unordered_set，也算是用上了雜湊。當然點陣圖呀，布隆過濾器呀，海量處理資料等 都會用到雜湊。
到此這篇關於C語言雜湊表概念超詳細講解的文章就介紹到這了,更多相關C語言雜湊表內容請搜尋it145.com以前的文章或繼續瀏覽下面的相關文章希望大家以後多多支援it145.com！
相關文章
-
黑科技的輕簡出行，告別「電量焦慮症」：Anker氮化鎵超能充系列
综合看Anker超能充系列的性价比很高，并且与不仅和iPhone12/苹果<em>Mac</em>Book很配，而且适合多设备充电需求的日常使用或差旅场景，不管是安卓还是Switch同样也能用得上它，希望这次分享能给准备购入充电器的小伙伴们有所
2021-06-01 09:31:42
-
吳亦凡廠牌首秀，L4WUDU居然忘詞了，Rapper和明星比還是有差距！
除了L4WUDU与吴亦凡已经多次共事，成为了明面上的厂牌成员，吴亦凡还曾带领20XXCLUB全队参加2020年的一场音乐节，这也是20XXCLUB首次全员合照，王嗣尧Turbo、陈彦希Regi、<em>Mac</em> Ova Seas、林渝植等人全部出场。然而让
2021-06-01 09:31:34
-
IPFS、Chia、Bzz和ICP挖礦該怎麼選？哪一個更有優勢？
目前应用IPFS的机构：1 谷歌<em>浏览器</em>支持IPFS分布式协议 2 万维网 (历史档案博物馆)数据库 3 火狐<em>浏览器</em>支持 IPFS分布式协议 4 EOS 等数字货币数据存储 5 美国国会图书馆，历史资料永久保存在 IPFS 6 加
2021-06-01 09:31:24
-
有哪些事是買了雪佛蘭後才知道的？美事偷著樂，開拓者車主隨聊
开拓者的车机是兼容苹果和<em>安卓</em>，虽然我不怎么用，但确实兼顾了我家人的很多需求：副驾的门板还配有解锁开关，有的时候老婆开车，下车的时候偶尔会忘记解锁，我在副驾驶可以自己开门：第二排设计很好，不仅配置了一个很大的
2021-06-01 09:30:48
-
iPhone12在618最新定價，跌價幅度超過1400元，還等iPhone13嗎？
不仅是<em>安卓</em>手机，苹果手机的降价力度也是前所未有了，iPhone12也“跳水价”了，发布价是6799元，如今已经跌至5308元，降价幅度超过1400元，最新定价确认了。iPhone12是苹果首款5G手机，同时也是全球首款5nm芯片的智能机，它
2021-06-01 09:30:45