C++數(shù)據(jù)結(jié)構(gòu)之哈希表的實現(xiàn)
哈希表概念
二叉搜索樹具有對數(shù)時間的表現(xiàn)，但這樣的表現(xiàn)建立在一個假設(shè)上：輸入的數(shù)據(jù)有足夠的隨機性。哈希表又名散列表，在插入、刪除、搜索等操作上具有「常數(shù)平均時間」的表現(xiàn)，而且這種表現(xiàn)是以統(tǒng)計為基礎(chǔ)，不需依賴輸入元素的隨機性。
聽起來似乎不可能，倒也不是，例如：
假設(shè)所有元素都是 8-bits 的正整數(shù)，范圍 0~255，那么簡單得使用一個數(shù)組就可以滿足上述要求。首先配置一個數(shù)組 Q，擁有 256 個元素，索引號碼 0~255，初始值全部為 0。每一個元素值代表相應(yīng)的元素的出現(xiàn)次數(shù)。如果插入元素 i，就執(zhí)行 Q[i]++，如果刪除元素 i，就執(zhí)行 Q[i]--，如果查找元素 i，就看 Q[i] 是否為 0。
這個方法有兩個很嚴(yán)重的問題。
- 如果元素是 32-bits，數(shù)組的大小就是232=4GB，這就太大了，更不用說 64-bits 的數(shù)了
- 如果元素類型是字符串而非整數(shù)，就需要某種方法，使其可用作數(shù)組的索引
散列函數(shù)
如何避免使用一個太大的數(shù)組，以及如何將字符串轉(zhuǎn)化為數(shù)組的索引呢？一種常見的方法就是使用某種映射函數(shù)，將某一元素映射為一個「大小可接受的索引」，這樣的函數(shù)稱為散列函數(shù)。
散列函數(shù)應(yīng)有以下特性：
- 函數(shù)的定義域必須包含需要存儲的全部關(guān)鍵字，當(dāng)散列表有 m 個地址時，其值域在 0 到 m - 1 之間
- 函數(shù)計算出來的地址能均勻分布在整個空間
直接定址法
取關(guān)鍵字的某個線性函數(shù)為散列地址：Hash(Key)=A∗Key+B
優(yōu)點：簡單、均勻
缺點：需要事先知道關(guān)鍵字的分布情況
使用場景：數(shù)據(jù)范圍比較集中的情況
除留余數(shù)法
設(shè)散列表的索引個數(shù)為 m，取一個不大于 m，但最接近 m 的質(zhì)數(shù) p 最為除數(shù)，按照散列函數(shù)：Hash(Key)=key，將關(guān)鍵字轉(zhuǎn)化為哈希地址
平方取中法
假設(shè)關(guān)鍵字為 1230，它的平方是 1512900，取中間的 3 位 129 作為哈希地址；
再比如關(guān)鍵字為 321，它的平方是 103041，取中間的 3 位 304（或 30）作為哈希地址。
哈希沖突
使用散列函數(shù)會帶來一個問題：可能有不同的元素被映射到相同的位置。這無法避免，因為元素個數(shù)大于數(shù)組的容量，這便是「哈希沖突」。解決沖突問題的方法有很有，包括線性探測、二次探測、開散列等。
線性探測
當(dāng)散列函數(shù)計算出某個元素的插入位置，而該位置上已有其他元素了。最簡單的方法就是向下一一尋找（到達尾端，就從頭開始找），直到找到一個可用位置。
進行元素搜索時同理，如果散列函數(shù)計算出來的位置上的元素值與目標(biāo)不符，就向下一一尋找，直到找到目標(biāo)值或遇到空。
至于元素的刪除，必須采用偽刪除，即只標(biāo)記刪除記號，實際刪除操作在哈希表重新整理時再進行。這是因為哈希表中的每一個元素不僅表示它自己，也影響到其他元素的位置。
從上述插入過程我們可以看出，當(dāng)哈希表中元素變多時，發(fā)生沖突的概率也變大了。由此，我們引出哈希表一個重要概念：負(fù)載因子。
負(fù)載因子定義為：Q = 表中元素個數(shù) / 哈希表的長度
- 負(fù)載因子越大，剩余可用空間越少，發(fā)生沖突可能越大
- 負(fù)載因子越小，剩余可用空間越多，發(fā)生沖突可能越小，同時空間浪費更多
因此，控制負(fù)載因子是個非常重要的事。對于開放定址法（發(fā)生了沖突，就找下一個可用位置），負(fù)載因子應(yīng)控制在 0.7~0.8 以下。超過 0.8，查找時的 CPU 緩存不命中按照指數(shù)曲線上升。
二次探測
線性探測的缺陷是產(chǎn)生沖突的數(shù)據(jù)會堆在一起，這與其找下一個空位置的方式有關(guān)，它找空位置的方式是挨著往后逐個去找。二次探測主要用來解決數(shù)據(jù)堆積的問題，其命名由來是因為解決碰撞問題的方程式F(i)=i2是個二次方程式。
更具體地說，如果散列函數(shù)計算出新元素的位置為 H，而該位置實際已被使用，那么將嘗試H+12,H+22,H+32,...,H+i2，而不是像線性探測那樣依次嘗試H+1,H+2,H+3,...,H+i。
大量實驗表明：當(dāng)表格大小為質(zhì)數(shù)，而且保持負(fù)載因子在 0.5 以下（超過 0.5 就重新配置），那么就可以確定每插入一個新元素所需要的探測次數(shù)不超過 2。
鏈地址法
這種方法是在每一個表格元素中維護一個鏈表，在呢個鏈表上執(zhí)行元素的插入、查詢、刪除等操作。這時表格內(nèi)的每個單元不再只有一個節(jié)點，而可能有多個節(jié)點。
節(jié)點的定義：
template <class Value>
struct __hashtable_node {
__hashtable_node* next;
Value val;
};
哈希表的實現(xiàn)
閉散列
接口總覽
template <class K, class V>
class HashTable {
struct Elem {
pair<K, V> _kv;
State _state = EMPTY;
};
public:
Elem* Find(const K& key);
bool Insert(const pair<K, V>& kv);
bool Erase(const K& key);
private:
vector<Elem> _table;
size_t _n = 0;
};
節(jié)點的結(jié)構(gòu)
因為在閉散列的哈希表中的每一個元素不僅表示它自己，也影響到其他元素的位置。所以要使用偽刪除，我們使用一個變量來表示。
/// @brief 標(biāo)記每個位置狀態(tài)
enum State {
EMPTY, // 空
EXIST, // 有數(shù)據(jù)
DELETE // 有數(shù)據(jù)，但已被刪除
};
哈希表的節(jié)點結(jié)構(gòu)，不僅存儲數(shù)據(jù)，還存儲狀態(tài)。
/// @brief 哈希表的節(jié)點
struct Elem {
pair<K, V> _kv; // 存儲數(shù)據(jù)
State _state; // 存儲狀態(tài)
};
查找
查找的思路比較簡單：
- 利用散列函數(shù)獲取映射后的索引
- 遍歷數(shù)組看是否存在，直到遇到空表示查找失敗
/// @brief 查找指定 key
/// @param key 待查找節(jié)點的 key 值
/// @return 找到返回節(jié)點的指針，沒找到返回空指針
Elem* Find(const K& key) {
if (_table.empty()) {
return nullptr;
}
// 使用除留余數(shù)法的簡化版本，并沒有尋找質(zhì)數(shù)
// 同時，該版本只能用于正整數(shù)，對于字符串等需使用其他散列函數(shù)
size_t start = key % _table.size();
size_t index = start;
size_t i = 1;
// 直到找到空位置停止
while (_table[index]._state != EMPTY) {
if (_table[index]._state == EXIST && _table[index]._kv.first == key) {
return &_table[index];
}
index = start + i;
index %= _table.size();
++i;
// 判斷是否重復(fù)查找
if (index == start) {
return nullptr;
}
}
return nullptr;
}
在上面代碼的查找過程中，加了句用于判斷是否重復(fù)查找的代碼。理論上上述代碼不會出現(xiàn)所有的位置都有數(shù)據(jù)，查找不存在的數(shù)據(jù)陷入死循環(huán)的情況，因為哈希表會擴容，閉散列下負(fù)載因子不會到 1。
但假如，我們插入了 5 個數(shù)據(jù)，又刪除了它們，之后又插入了 5 個數(shù)據(jù)，將 10 個初始位置都變?yōu)榉?EMPTY。此時我們查找的值不存在的話，是會陷入死循環(huán)的。
插入
插入的過程稍微復(fù)雜一些：
1.首先檢查待插入的 key 值是否存在
2.其次需要檢查是否需要擴容
3.使用線性探測方式將節(jié)點插入
/// @brief 插入節(jié)點
/// @param kv 待插入的節(jié)點
/// @return 插入成功返回 true，失敗返回 false
bool Insert(const pair<K, V>& kv) {
// 檢查是否已經(jīng)存在
Elem* res = Find(kv.first);
if (res != nullptr) {
return false;
}
// 看是否需要擴容
if (_table.empty()) {
_table.resize(10);
} else if (_n > 0.7 * _table.size()) { // 變化一下負(fù)載因子計算，可以避免使用除法
HashTable backUp;
backUp._table.resize(2 * _table.size());
for (auto& [k, s] : _table) {
// C++ 17 的結(jié)構(gòu)化綁定
// k 綁定 _kv，s 綁定 _state
if (s == EXIST) {
backUp.Insert(k);
}
}
// 交換這兩個哈希表，現(xiàn)代寫法
_table.swap(backUp._table);
}
// 將數(shù)據(jù)插入
size_t start = kv.first % _table.size();
size_t index = start;
size_t i = 1;
// 找一個可以插入的位置
while (_table[index]._state == EXIST) {
index = start + i;
index %= _table.size();
++i;
}
_table[index]._kv = kv;
_table[index]._state = EXIST;
++_n;
return true;
}
刪除
刪除的過程非常簡單：
1.查找指定 key
2.找到了就將其狀態(tài)設(shè)為 DELETE，并減少表中元素個數(shù)
/// @brief 刪除指定 key 值
/// @param key 待刪除節(jié)點的 key
/// @return 刪除成功返回 true，失敗返回 false
bool Erase(const K& key) {
Elem* res = Find(key);
if (res != nullptr) {
res->_state = DELETE;
--_n;
return true;
}
return false;
}
開散列
接口總覽
template <class K, class V>
class HashTable {
struct Elem {
Elem(const pair<K, V>& kv)
: _kv(kv)
, _next(nullptr)
{}
pair<K, V> _kv;
Elem* _next;
};
public:
Elem* Find(const K& key);
bool Insert(const pair<K, V>& kv);
bool Erase(const K& key);
private:
vector<Elem*> _table;
size_t _n = 0;
};
節(jié)點的結(jié)構(gòu)
使用鏈地址法解決哈希沖突就不再需要偽刪除了，但需要一個指針，指向相同索引的下一個節(jié)點。
/// @brief 哈希表的節(jié)點
struct Elem {
Elem(const pair<K, V>& kv)
: _kv(kv)
, _next(nullptr)
{}
??????? pair<K, V> _kv; // 存儲數(shù)據(jù)
Elem* _next; // 存在下一節(jié)點地址
};
查找
查找的實現(xiàn)比較簡單：
1.利用散列函數(shù)獲取映射后的索引
2.遍歷該索引位置的鏈表
/// @brief 查找指定 key
/// @param key 待查找節(jié)點的 key 值
/// @return 找到返回節(jié)點的指針，沒找到返回空指針
Elem* Find(const K& key) {
if (_table.empty()) {
return nullptr;
}
size_t index = key % _table.size();
Elem* cur = _table[index];
// 遍歷該位置鏈表
while (cur != nullptr) {
if (cur->_kv.first == key) {
return cur;
}
cur = cur->_next;
}
return nullptr;
}
插入
開散列下的插入比閉散列簡單：
1.首先檢查待插入的 key 值是否存在
2.其次需要檢查是否需要擴容
3.將新節(jié)點以頭插方式插入
/// @brief 插入節(jié)點
/// @param kv 待插入的節(jié)點
/// @return 插入成功返回 true，失敗返回 false
bool Insert(const pair<K, V>& kv) {
// 檢查是否已經(jīng)存在
Elem* res = Find(kv.first);
if (res != nullptr) {
return false;
}
// 檢查是否需要擴容
if (_table.size() == _n) {
vector<Elem*> backUp;
size_t newSize = _table.size() == 0 ? 10 : 2 * _table.size();
backUp.resize(newSize);
// 遍歷原哈希表，將所有節(jié)點插入新表
for (int i = 0; i < _table.size(); ++i) {
Elem* cur = _table[i];
while (cur != nullptr) {
// 取原哈希表的節(jié)點放在新表上，不用重新申請節(jié)點
Elem* tmp = cur->_next;
size_t index = cur->_kv.first % backUp.size();
cur->_next = backUp[index];
backUp[index] = cur;
cur = tmp;
}
_table[i] = nullptr;
}
_table.swap(backUp);
}
// 將新節(jié)點以頭插的方式插入
size_t index = kv.first % _table.size();
Elem* newElem = new Elem(kv);
newElem->_next = _table[index];
_table[index] = newElem;
++_n;
return true;
}
刪除
開散列的刪除與閉散列有些許不同：
1.獲取 key 對應(yīng)的索引
2.遍歷該位置鏈表，找到就刪除
/// @brief 刪除指定 key 值
/// @param key 待刪除節(jié)點的 key
/// @return 刪除成功返回 true，失敗返回 false
bool Erase(const K& key) {
size_t index = key % _table.size();
Elem* prev = nullptr;
Elem* cur = _table[index];
while (cur != nullptr) {
if (cur->_kv.first == key) {
if (prev == nullptr) {
// 是該位置第一個節(jié)點
_table[index] = cur->_next;
} else {
prev->_next = cur->_next;
}
delete cur; // 釋放該節(jié)點
--_n;
return true;
}
prev = cur;
cur = cur->_next;
}
return false;
}
到此這篇關(guān)于C++數(shù)據(jù)結(jié)構(gòu)之哈希表的實現(xiàn)的文章就介紹到這了,更多相關(guān)C++哈希表內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
詳解C語言中printf輸出的相關(guān)函數(shù)
這篇文章主要介紹了C語言中printf輸出的相關(guān)函數(shù)總結(jié),是C語言入門學(xué)習(xí)中的基礎(chǔ)知識,需要的朋友可以參考下2015-08-08
這篇文章主要介紹了C++中std::vector的6種初始化方式,具有很好的參考價值,希望對大家有所幫助,如有錯誤或未考慮完全的地方,望不吝賜教2023-08-08
這篇文章主要介紹了C++中異常處理的基本思想及throw類拋出異常的使用,也深入談到了異常被拋出后的棧解旋unwinding過程,需要的朋友可以參考下2016-03-03
C++11中隱式類型轉(zhuǎn)換的實現(xiàn)示例
C++類型轉(zhuǎn)換分為:隱式類型轉(zhuǎn)換和顯式類型轉(zhuǎn)換,本文主要介紹了C++11中隱式類型轉(zhuǎn)換的實現(xiàn)示例,具有一定的參考價值,感興趣的可以了解一下2024-06-06
本文主要介紹了C++/C關(guān)于#define的一些妙用，文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2023-02-02
這篇文章主要介紹了如何用C語言畫一個“圣誕樹”，感興趣的小伙伴們可以參考一下2015-12-12
這篇文章主要為大家詳細(xì)介紹了C\C++實現(xiàn)讀寫二進制文件的方法，文中的示例代碼講解詳細(xì)，具有一定的借鑒價值，感興趣的小伙伴可以了解一下2023-03-03
這篇文章主要為大家詳細(xì)介紹了C語言實現(xiàn)掃雷游戲簡易版，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價值，感興趣的小伙伴們可以參考一下2020-11-11
隊列先進先出,即只能在容器的末尾添加新元素,只能從頭部移除元素,下面這篇文章主要給大家介紹了關(guān)于C++中隊列queue用法的相關(guān)資料,文中通過示例代碼介紹的非常詳細(xì),需要的朋友可以參考下2022-04-04
set set是一種關(guān)聯(lián)式容器,下面這篇文章主要給大家介紹了關(guān)于C++中map和set使用的相關(guān)資料,文中通過實例代碼介紹的非常詳細(xì),對大家學(xué)習(xí)或者使用C++具有一定的參考學(xué)習(xí)價值,需要的朋友可以參考下2023-03-03