C語言哈希表概念超詳細講解
1. 哈希概念
哈希其實在學排序時已經用過了，就是計數排序。計數排序也是用的一種映射關系。
比如對此數組進行 計數排序 ：1 1 9 9 9 3 3 8 8
我用的是絕對映射 ，所以開辟的數組空間 它的大小 必須 能映射到 最大的元素。
但是 對于哈希來講，可以用決定映射嘛？當然不可以，如果是絕對映射會造成很大的空間浪費。所以 哈希 用的是 取模的方式來存 數據。
比如 ： 哈希表 的空間 我給定 只能存放 10個元素
存進來的數 對10進行取模 ，那么必定可以存方到 這個哈希表中。
比如：存 100 ，它對10取模得 0，那它就存在第一個位置；存 52 ，它對10進行取模得 2，那它就存到 下標為 2的位置。
也就是說 無論多大的數據，都可以存到哈希表中。但是 有兩個 問題：
- 數據都能進行取模嗎？假如我要求哈希表中存的是一個字符串，字符串不能進行取模運算，該怎么辦？這就是數據可否哈希的問題，我們要把存進哈希表的數據，變?yōu)榭晒祿?/li>
- 如果我存的是 4，下一次我要存的是 14。由于 4的位置已經被占了，我存的 14 該存放到何處？要是直接存，就意味著前面存的 4 會被覆蓋，造成數據丟失。這就是哈希沖突問題。
2. 哈希沖突
造成了哈希沖突，得解決哈希沖突問題。
這里給出兩種解決手段：
閉散列：也叫開放定址法，當發(fā)生哈希沖突時，如果哈希表未被裝滿，說明在哈希表中必然還有空位置，那么可以把key存放到沖突位置中的“下一個” 空位置中去。
它相當于 如果我本來要存的位置，已經被占了，那么我就要在哈希表中找一個空位置存放。開散列：開散列法又叫鏈地址法(開鏈法)，首先對關鍵碼集合用散列函數計算散列地址，具有相同地址的關鍵碼歸于同一子集合，每一個子集合稱為一個桶，各個桶中的元素通過一個單鏈表鏈接起來，各鏈表的頭結點存儲在哈希表中。
這種辦法是常用的，它相當于 哈希表 每個位置 都存的是一個哈希桶，如果發(fā)送哈希沖突，直接就放在哈希桶里就行了。
3. 哈希實現
哈希表其實就是一個數組，數組中存的是節(jié)點數據，發(fā)生哈希沖突后，采用的是往后找空位置的方法。
圖解：
(1) 10 % 6 == 4,所以插入到下標為4的位置
(2) 20%6==2,插入到下標為2的位置
(3)12%6 == 0,插入到下標為0的位置。
(4)22%6 == 4，插入到下標為4的位置，發(fā)現已經有數據了，所以向后找空位置。
(5)44%6 == 2，插入到下標為2的位置，發(fā)現已經有數據了，所以向后找空位置。
哈希桶其實就是一個數組，數組中存的是節(jié)點鏈表，發(fā)生哈希沖突后，是直接插入到節(jié)點鏈表中。
如果是哈希桶，存放上面的數據，是什么樣的呢？
圖解：
它相當于把發(fā)生沖突的數據 掛在了 沖突位置的下面。
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) 用枚舉常量來 標記 哈希表中 每個位置的狀態(tài)，狀態(tài)有 空，不為空，被刪除。
大家可能會對 被刪除這個狀態(tài)產生疑問，一個位置 不就是 有數據和沒數據嗎？主要是大家想 如果 直接物理上刪除，把位置 狀態(tài)設置為 空，那么 就會影響后面的數據。
比如：刪除 5 這個數據、
直接將 5 的位置 設置為空，那么 15 這個數據 會受到影響。因為 對 哈希表大小取模后，等于 5 的 不一定只有 5，還有 15，25，35。如果 將 5位置直接設置 為 空，就相當于 后面的數據中 已經沒有 15，25，35 了。具體我們往下看查找的實現。
enum status
{
Empty,
Exist,
Delete
};
(2) 哈希表中的數據類型，以及哈希表的底層結構
哈希表中的數據類型，是一個結構體 ，包括了 一個鍵值對和狀態(tài)：
template<class K,class V>
struct hashdate
{
pair<K, V> _kv;
// 默認狀態(tài)為空
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循環(huán)中，它的條件是 _tables[index]._status != Empty 說明 即使當下位置狀態(tài)是 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時，就說明需要擴容了。這是大佬們搞出來的，我們還需要知道，載荷因子 越大就說明 填入哈希表的元素越多，越可能發(fā)送哈希沖突。
擴容的操作，我是 創(chuàng)建了一個新的哈希表，然后把原表中的數據插入到新表中。這里還有一個坑，就是，可不可以 直接將舊表的數據拷貝到新表中，答案是 不行。
舉個例子：
原表是 ：
新表是：
直接拷貝的話是這樣的：
看圖也懂了哈，擴容后的表 是需要重新插入數據，因為 位置 可能會發(fā)送改變。
擴容完了，就是插入了，如果當下的位置是 Delete 或者 Eempty 那么就可以直接插入；否則就需要向后面查找空的位置，進行插入。
(5) 哈希表的刪除
bool erase(const K& key)
{
Node* ret = find(key);
if (ret == nullptr)
return false;
ret->_status = Delete;
_n -= 1;
return true;
}
刪除很簡單，就是將那個位置的狀態(tài)改為 Delete，然后有效數據個數 減一 就行了。
3.1.1 閉散列的細節(jié)
首先，上面的哈希表其實還有問題。
比如： 不是所有的數據都可以取模，這個問題，并沒有解決，上面實現是 直接取模。
所以還需要實現一個 將數據轉為可哈希數據的仿函數。為什么是仿函數呢？因為 數據類型較多，情況不一，這里還用到了模板特化的知識，大家坐穩(wěn)扶好。
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 ，這也是大佬的手法，因為多次測試后發(fā)現，乘以 31 會使 哈希沖突少一些。
默認情況下，就是直接返回 key，也就是默認情況下都是可哈希的。
如果 你要哈希一個自定義對象，那么還得是用模板的特化，自己處理。
所以有了仿函數之后，我們就不必擔心，傳過去的數據是否能夠 被哈希了，靠仿函數去處理。具體怎么用，后面會給出完整代碼。
其次，還有一個問題，就是 線性探索和二次探索：
大家可能對這倆詞不陌生，也就是哈希表中，發(fā)生哈希沖突后，查找空位置時，是連續(xù)的查找空位置還是 平方次的跳躍的查找。
當然是二次查找更優(yōu)秀一些，上面的程序用的是線性探索，也就是 那個 i++，它就是連續(xù)的往后查找。為什么呢？因為 如果是線性探索，它會比較擁擠，連續(xù)位置太多，從而引發(fā)踩踏效應，也就導致，每次來的數據，都需要去找空位置。
二次探索很簡單，把 i++ 變成 i =i *i。
3.1.2 優(yōu)化后的閉散列
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) 哈希桶的節(jié)點以及底層結構
哈希桶的節(jié)點是一個單向鏈表，它得有數據，是一個鍵值對，還得有 下一個節(jié)點的指針。
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)
{
}
};
哈希桶的底層，是一個數組，數組中存的是節(jié)點的指針，當然還得有一個有效數據的個數，它是用于判斷是否需要擴容的。
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();
// 前一個節(jié)點
Node* pre = nullptr;
//桶的第一個節(jié)點
Node* cur = _tables[index];
while (cur)
{
// 桶的下一個節(jié)點
Node* next = cur->_next;
// 找到要刪除的節(jié)點
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();
再就是 在這個桶中 刪除，我們需要考慮幾件事:
- 桶中是單向鏈表，刪除的話我需要維護鏈表的關系，所以需要記錄刪除數據的前一個數據
- 要刪除的節(jié)點如果是頭節(jié)點，就不需要維護和前一個數據的關系，因為它就是第一個
- 要刪除的節(jié)點在中間或者最后，那就需要維護和前一個的關系
3.2.1 擴散列的細節(jié)
擴散列是有極端情況的，比如 我開辟的數組大小是 10 ，插入的數據是 10，20，30，40，50，60 …… 10000000000，這些數據都插入到了一個桶里面。
會導致哈希桶變成這樣：
會發(fā)現，效率退化了，哈希的查找一般情況是O(1) ，但是這種情況下，退化成O(n)了。所以應該怎么辦？大佬其實是給出解決方案的，就是一個桶中的元素超過了某一個量，那么就會將這個桶中的數據用紅黑樹組織起來，對于這個量jave和C++還不一樣。
這就是所謂的桶中種樹。
但是上面的哈希桶，我沒有支持這種高級操作，我覺得只要了解這個事情就行了，至于實現，也是可以的，但是對于我們要學習哈希，沒太大幫助。
4. 哈希表和哈希桶的比較
哈希桶處理溢出，需要增設鏈接指針，似乎增加了存儲開銷。
事實上： 由于哈希表必須保持大量的空閑空間以確保搜索效率，如二次探查法要求裝載因子a <= 0.7，而表項所占空間又比指針大的多，所以使用鏈地址法反而比開地址法節(jié)省存儲空間。
哈希表處理哈希沖突用的是搶占別的位置，可能會導致數據比較阻塞，也就是每進來一個數據都需要去搶占別人的位置。
哈希桶處理哈希沖突用的是在沖突位置，增加鏈節(jié)點的方法，但是有可能造成，單向鏈表太長從而影響效率，所以需要將單向鏈表變?yōu)榧t黑樹管理起來。
5. 結尾語
學完哈希，能干什么？說實話哈希很重要，學數據結構，你說你不會哈希，那么就相當于你白學數據結構了，就是這么夸張哈，以后工作也會大量用到哈希的。所以大家加油。在我的下一篇文章中，會利用哈希桶去實現unordered_map和unordered_set，也算是用上了哈希。當然位圖呀，布隆過濾器呀，海量處理數據等 都會用到哈希。
到此這篇關于C語言哈希表概念超詳細講解的文章就介紹到這了,更多相關C語言哈希表內容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家！
相關文章
本文介紹了在C++中使用FFmpeg庫進行自定義編碼器適配的實現方法。文章通過具體的代碼示例，介紹了FFmpeg的基本使用方法和自定義編碼器的實現過程，幫助讀者了解如何在C++中進行音視頻編碼和解碼的開發(fā)工作，并能夠實現自定義的編碼器適配2023-04-04
C語言的sleep、usleep、nanosleep等休眠函數的使用
本文主要介紹了C語言的sleep、usleep、nanosleep等休眠函數的使用，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧2023-03-03
C++標準庫沒有提供所謂的日期類型,C++繼承了C語言用于日期和時間操作的結構和函數,這篇文章主要給大家介紹了關于C++日期類實現的完整操作,文中通過代碼介紹的非常詳細,需要的朋友可以參考下2024-06-06
樹形DP是什么？跟其他DP有什么區(qū)別？相信很多初學者在剛剛接觸一種新思想的時候都會有這種問題。沒錯，樹形DP準確的說是一種DP的思想，將DP建立在樹狀結構的基礎上。所以我們結合具體題目進行講解，希望大家可以在題目中領悟這種思想。2021-05-05
這篇文章主要介紹了c++類構造函數示例,需要的朋友可以參考下2014-05-05
C++11中std::move、std::forward、左右值引用、移動構造函數的測試問題
這篇文章主要介紹了C++11中std::move、std::forward、左右值引用、移動構造函數的測試,本文通過實例代碼給大家介紹的非常詳細，對大家的學習或工作具有一定的參考借鑒價值，需要的朋友可以參考下2020-09-09
這篇文章主要為大家詳細介紹了如何基于C++編寫一個簡單的密碼系統(tǒng),文中的示例代碼講解詳細,具有一定的借鑒價值,感興趣的小伙伴可以跟隨小編一起學習一下2023-11-11
AVL樹是高度平衡的而二叉樹,它的特點是AVL樹中任何節(jié)點的兩個子樹的高度最大差別為1,本文主要給大家介紹了C++如何實現AVL樹,需要的朋友可以參考下2022-06-06
這篇文章主要介紹了C++11線程、互斥量以及條件變量,C++11增加了線程以及線程相關的類，很方便地支持了并發(fā)編程，使得編寫多線程程序的可移植性得到了很大的提高，本文通過實例代碼給大家詳細講解，需要的朋友可以參考下2023-03-03
這篇文章主要介紹了C++類型轉換歸納總結,通過本文可以加深讀者對于C++變量類型及其相互轉換方法的理解,需要的朋友可以參考下2014-07-07