C++哈希表之閉散列方法的模擬實現(xiàn)詳解
哈希
概念
可以不經(jīng)過任何比較，直接從表中得到要搜索的元素。 關鍵在于通過某種函數(shù)，使元素的存儲位置與它的關鍵碼之間能夠建立 一一映射的關系。這樣就可以通過o(1)的時間復雜度來尋找到元素。
例如數(shù)據(jù)集合{1,7,4,5,9,6}，哈希函數(shù)hash(key)=key&capacity
沖突
hash(7)=7 hash(17)=7,兩個不同的數(shù)通過哈希函數(shù)映射到了一個位置，產(chǎn)生了沖突。哈希函數(shù)設計的越精妙，產(chǎn)生沖突的可能性就越低，但無法避免。
解決方法：
- 閉散列（開放定址法）
- 開散列（拉鏈法）
閉散列
閉散列，（開放定址法）發(fā)生沖突時，如果哈希表沒有被填滿，則表內一定還有其他空閑位置，可以把沖突值放到下一個沒有被占用的空余位置上。
如何找到下一個沒有被占用的空位？答：采用線性探測方法。從發(fā)生沖突的位置開始，依次向后探測，直到尋找到下一個空位置為止。
線性探測
線性探測的插入
如：在上述的哈希表中插入元素44，由于下標為4的位置放入了元素4，于是從該位置往后++，找到第一個不為空的位置，將44放入。
線性探測的刪除
在尋找要刪除的元素時，依然會根據(jù)存放在哈希表的下標開始尋找，比如在上述哈希表中尋找4，在4下標位置直接就可以找到該元素。但如果直接將其刪除，那后續(xù)尋找元素44時，就會因為4下標沒有元素，而認為元素44不存在于這張哈希表。所以我們需要設置一個狀態(tài)來表示刪除。
哈希表閉散列的模擬實現(xiàn)
我們寫在一個自定義類域 Closehash 里面
準備工作
哈希表中元素狀態(tài)
namespace Closehash
{
//哈希表中元素的狀態(tài)
enum State
{
EMPTY,
EXIT,
DELETE
};
}
存儲類型用pair即可，但是數(shù)據(jù)中要包含狀態(tài)，我們進行一次封裝
//由于數(shù)據(jù)需要一個狀態(tài)，所以需要將pair<K,V>封裝一層
template<class K,class V>
struct HashDate
{
pair<K, V>_kv;
State _state;
};
開始（畫餅）構建哈希表的內容
template<class K,class V>
class HashTable
{
public:
bool Insert(const pair<K,V>& kv);
HashDate<K, V>* find(const K& key);
bool Erase(const K& key);
private:
vector<HashDate<K,V>> _tables;
size_t _size = 0;
};
閉散列的插入
bool Insert(const pair<K, V>& kv)
{
//if (Find(kv.first)) return false;
//Find實現(xiàn)了再去掉注釋
if (_tables.size() == 0
|| 10 * _size / _tables.size() >= 7)//相當于存了70%
{
//開始擴容
size_t newsize = _tables.size()== 0 ? 10 : _tables.size() * 2;
HashTable<K, V> newHash;
newHash._tables.resize(newsize);
for (auto e: _tables)//注意_tables是HashDate類型 里面有_kv 和_state
{
if (e._state == EXIST)
{
newHash.Insert(e._kv);
}
}
//資本家拷貝方法
_tables.swap(newHash._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;
_size++;
return true;
}測試用例
void TestHT1()
{
int a[] = { 1, 11, 4, 15, 26, 7, 44 };
HashTable<int, int> ht;
for (auto e : a)
{
ht.Insert(make_pair(e, e));
}
ht.Print();
}
添加個99以驗證擴容功能
閉散列的查找
HashDate<K, V>* Find(const K& key)
{
if (_tables.size() == 0) return nullptr;
size_t hashi = 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;
}測試用例
cout << ht.Find(4)->_kv.first << endl;
閉散列的刪除
bool Erase(const K& key)
{
HashDate<K,V>* ret = Find(key);
if (ret)
{
ret->_state = DELETE;
--_size;
return true;
}
else
{
return false;
}
}
模擬實現(xiàn)的閉散列中的問題與改進
上述測試用例中使用的是pair<int,int>那我要是用pair<string,int>呢？我的key還可以直接對數(shù)組長度取模嗎？
文檔中對這一問題采用了仿函數(shù)的解決方法，我們這里也按照該方法模擬一個。
template<class K>
struct HashFunc
{
size_t operator()(const K& key)
{
return (size_t)key;
}
};
// 特化
template<>
struct HashFunc<string>
{
// BKDR
size_t operator()(const string& key)
{
size_t val = 0;
for (auto ch : key)
{
val *= 131;
val += ch;
}
return val;
}
};
template<class K,class V,class Hash=HashFunc<K>>
class HashTable
{
public:
bool Insert(const pair<K,V>& kv);
HashDate<K, V>* find(const K& key);
bool Erase(const K& key);
private:
vector<HashDate<K,V>> _tables;
size_t _size = 0;
};在每次求 在哈希表中位置的前面添加
Hash hash;
size_t hashi = hash(kv.first) % _tables.size()
測試用例
void TestHT2()
{
string arr[] = { "蘋果", "西瓜", "蘋果", "西瓜", "蘋果", "蘋果", "西瓜", "蘋果", "香蕉", "蘋果", "香蕉" };
//HashTable<string, int, HashFuncString> countHT;
HashTable<string, int> countHT;
for (auto& str : arr)
{
auto ptr = countHT.Find(str);
if (ptr)
{
ptr->_kv.second++;
}
else
{
countHT.Insert(make_pair(str, 1));
}
}
}
測試用例沒加打印...讓我來回看了好幾遍代碼...蠢到無語
到此這篇關于C++哈希表之閉散列方法的模擬實現(xiàn)詳解的文章就介紹到這了,更多相關C++哈希表實現(xiàn)閉散列內容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家！
相關文章
這篇文章主要介紹了C++中typedef 及其與struct的結合使用,需要的朋友可以參考下2014-02-02
STL priority_queue（優(yōu)先隊列）詳解
這篇文章主要介紹了 STL priority_queue（優(yōu)先隊列）詳解的相關資料,需要的朋友可以參考下2016-10-10
這篇文章主要為大家詳細介紹了C語言實現(xiàn)超市計價收款系統(tǒng)，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2022-03-03
這篇文章主要為大家詳細介紹了C++順序表的基本操作，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2020-04-04
這篇文章主要介紹了C/C++ 凸多邊形求對角線交點的示例代碼,代碼簡單易懂，對大家的學習或工作具有一定的參考借鑒價值，需要的朋友可以參考下2020-11-11
這篇文章主要為大家詳細介紹了OpenCV實現(xiàn)多圖像拼接成一張大圖，具有一定的參考價值，感興趣的小伙伴們可以參考一下2019-01-01
C語言使用單鏈表實現(xiàn)學生信息管理系統(tǒng)
這篇文章主要為大家詳細介紹了C語言使用單鏈表實現(xiàn)學生信息管理系統(tǒng)，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2021-11-11
C++中求旋轉數(shù)組中的最小數(shù)字（經(jīng)典面試題）
這篇文章主要介紹了C++中求旋轉數(shù)組中的最小數(shù)字（經(jīng)典面試題）的相關資料,需要的朋友可以參考下2017-03-03
這篇文章主要介紹了C語言入門之基礎知識詳解,文中有非常詳細的C語言使用教程及相關基礎知識,對正在學習c語言的小伙伴們有非常好的幫助,需要的朋友可以參考下2021-08-08
這篇文章主要介紹了C++ const修飾變量和修飾函數(shù)介紹,本文直接用實例來講解各自的作用,并總結了各自的使用技巧,需要的朋友可以參考下2015-03-03