網站首頁 編程語言 正文
1.哈希映射
1.1哈希的概念
在順序結構以及平衡樹中，元素關鍵碼與其存儲位置之間沒有對應的關系，因此在查找一個元素時，必須要經過關鍵碼的多次比較。順序查找時間復雜度為O(N)，平衡樹中為樹的高度，即O(logN)，搜索的效率決于搜索過程中元素的比較次數。
理想的搜索方法：可以不經過任何比較，一次直接從表中得到要搜索的元素。 如果構造一種存儲結構，通過某種函數(hashFunc)使元素的存儲位置與它的關鍵碼之間能夠建立一一映射的關系，那么在查找時通過該函數可以很快找到該元素。
當向該結構中：
- 插入元素：根據待插入元素的關鍵碼，以此函數計算出該元素的存儲位置并按此位置進行存放
- 搜索元素：對元素的關鍵碼進行同樣的計算，把求得的函數值當做元素的存儲位置，在結構中按此位置取元素比較，若關鍵碼相等，則搜索成功
該方式即為哈希(散列)方法，哈希方法中使用的轉換函數稱為哈希(散列)函數，構造出來的結構稱為哈希表(Hash Table)(或者稱散列表)。
unordered_map和unordered_set的底層就是哈希來實現的，它是無序的。
Hash（key）=key%capacity。
聰明的小伙伴已經找到矛盾了，如果說再添加一個數據5，那他存那？?
1.2哈希沖突
對于兩個數據元素的關鍵字Ki和Kj(i != j)，有?Ki!=Kj，但有：Hash(Ki) == Hash(Kj)，即：不同關鍵字通過相同哈希函數計算出相同的哈希地址，該種現象稱為哈希沖突或哈希碰撞。把具有不同關鍵碼而具有相同哈希地址的數據元素稱為“同義詞”
所以這種方式建立起來的映射就十分的不合理，所以我們要改進。
哈希設計的原則：
- 哈希函數的定義域必須包括需要存儲的全部關鍵碼，而如果散列表允許有m個地址時，其值域必須在0到m-1之間。
- 哈希函數計算出來的地址能均勻分布在整個空間中。
- 哈希函數應比較簡單。
1.3哈希函數
1.31直接定值法
取關鍵字的某個線性函數為散列地址：Hash(key)= A*key + B
優點：簡單，速度快，節省空間，查找key O(1)的時間復雜度
缺點：當數據范圍大時會浪費空間，不能處理浮點數，字符串數據
使用場景：適用于整數，數據范圍比較集中
例如計數排序，統計字符串中出現的用26個英文字符統計，給數組分配26個空間，遍歷到的字符是誰，就把相應的元素值++
1.32除留余數法?
把數據映射到有限的空間里面。設散列表中允許的地址數為m，取一個不大于m，但最接近或者等于m的質數p作為除數，按照哈希函數：Hash(key) = key% p(p<=m)，將key轉換成哈希地址。
哈希函數設計的越精妙，產生哈希沖突的可能性就越低，但是無法避免哈希沖突。
看1.1節的例子
解決哈希沖突最常用的方法是閉散列和開散列。
2.解決哈希沖突
2.1閉散列法
閉散列：也叫開放定址法，當發生哈希沖突時，如果哈希表未被裝滿，說明在哈希表中必然還有空位置，那么可以把key存放到沖突位置中的“下一個” 空位置中去。?
但是咋去找下一個空位置才是最關鍵的？
2.11線性探測
線性探測：從發生沖突的位置開始，依次向后探測，直到尋找到下一個空位置為止。
插入：通過哈希函數獲取待插入元素在哈希表中的位置。如果該位置中沒有元素則直接插入新元素，如果該位置中有元素發生哈希沖突，使用線性探測找到下一個空位置，插入新元素。
刪除：采用閉散列處理哈希沖突時，不能隨便物理刪除哈希表中已有的元素，否則會影響其他元素的搜索。比如刪除元素1，如果直接刪除掉，11查找起來可能會受影響。因此線性探測采用標記的偽刪除法來刪除一個元素。
給每個位置一個標記，用空、存在、刪除3種狀態來區分。
- 負載因子 = 存儲的有效數據個數/空間的大小 。
- 負載因子越大，沖突的概率越高，增刪查改效率越低。
- 負載因子越小，沖突的概率越低，增刪查改的效率越高，但是空間利用率低，浪費多。?
- 負載因子 <1，就能保證發生哈希沖突時一定能找到空位置。
線性探測的優缺點:
- 線性探測優點：實現非常簡單。
- 線性探測缺點：一旦發生哈希沖突，所有的沖突連在一起，容易產生數據“堆積”，即：不同關鍵碼占據了可利用的空位置，使得尋找某關鍵碼的位置需要許多次比較，導致搜索效率降低。
2.12二次探測?
二次探測改進了一些線性探測，但是也就那樣，這里我就不給太多畫面了。
所謂的二次探測我們可以理解為飛躍式，線性是一個一個找空位置，二次就是跳著找。
方法：hash(key) + i^2
hash(11)=11%10+0*2=1,但是1的位置被占了，所以變成hash(11)+1*2,如果這個位置是空的就放進去，不是的話，i繼續加。
3代碼實現
3.1狀態
狀態：這里需要三種狀態：空，已占用，已刪除
如果只用有/沒有來代表狀態，那刪除一個數據后，這個位置就是空的，那就不會再遍歷了，但是它后面還有數據的話就存在問題了，所以我們用已刪除這個狀態來表示的話，還可以遍歷后面的數據。
#pragma once
#include<vector>
#include<iostream>
using namespace std;
namespace CloseHash
{
enum State
{
EMPTY, //0 空
EXIST, //1 存在
DELETE, // 2 已刪除
};
}3.2創建哈希節點類
template<class K,class V>
struct HashData
{
pair<K, V> _kv;//數據
State _state = State::EMPTY;//狀態 --空
};
template<class K, class V>//添加仿函數便于把其他類型的數據轉換為整型數據
class HashTable
{
public:
//相關功能的實現……
private:
vector<HashData<K, V>> _table;//哈希表
size_t _n = 0;//存儲哈希表中有效數據的個數
};
查找：當數據是1時，直接映射到下標1處，此時該位置的狀態是EXIST，數據是11時，映射到下標1處，但是已經有1了所以++往后找空位置找到后狀態更新為EXIST。
刪除：刪除1，找11，當刪除1后，狀態更新為DELETE，查找11時下標發現狀態是DELETE時會繼續往后移動，然后找到11.
當插入的數據較多，而哈希表較短時，就要考慮到擴容，但是哈希的擴容不簡單，因為一擴容，下標就變了，那很多數據的映射后的位置就變了。
現在的11在下標11處，就不在2處了。?
所以我們在上面提到了負載因子：?填入表中的元素個數 / 散列表的長度
由于散列表的長度一定，所以負載因子和表中的元素個數成正比。元素個數越多，哈希沖突越大，所以我們一般將負載因子定在0.7~0.8，在代碼中我們就定在0.7。
插入時我們再介紹。
3.3數據插入
插入的詳細步驟：
去除重復：
- 插入的值可能 已經存在，所以用用Find先進行查找
- 找到就返回false,沒找到在插入。
空間擴容：
- 如果表是空的就給10個空間，否則擴大2倍。
- 建立一個新哈希表，把舊表的值插入到新表
探測找位
- 如果位置的狀態是EXIST,繼續往后移
- 找到空位置后，插入，狀態變為存在，_n++。
//查找
bool Insert(const pair<K, V>& kv)
{
size_t hashi = kv.first % _tables.size(); //1.遇到空就停止了
//線性探測
while (_tables[hashi]._state == EXIST)
{
hashi++;
hashi %= _tables.size(); //2. 可能出表
}
_tables[hashi]._kv = kv;
_tables[hashi]._state = EXIST;
++_n;
return true;
}在1.0版本中我注意兩個細節：
hashi為啥要模size而不是capacity?
計算機開辟了20個空間，只存儲10個數據，但是只能讓計算機在前十個空間存，要不一旦用空的空間，遍歷時遇到后就不在往后進行了。所以開的空間一般和數據個數一致。
while循環中為啥要加一步hashi%=_table.size()?
比如我們開了20個空間，下標16以后都存滿了但是前面還有位置，但是我們存一個37，那他就一直找位置，直到找到19，然后就出這個哈希表了，所以要讓他返回到表上再到下標靠前的位置去找。
接下來就要開辟空間了。但是這個可不簡單。
當插入的數據較多，而哈希表較短時，就要考慮到擴容，但是哈希的擴容不簡單，因為一擴容，下標就變了，那很多數據的映射后的位置就變了。
現在的11在下標11處，就不在2處了。?
所以我們在上面提到了負載因子：?填入表中的元素個數 / 散列表的長度
由于散列表的長度一定，所以負載因子和表中的元素個數成正比。元素個數越多，哈希沖突越大，所以我們一般將負載因子定在0.7~0.8，在代碼中我們就定在0.7。
在這里我們就要重新建一個哈希表。
//查找
bool Insert(const pair<K, V>& kv)
{
if (Find(kv.first)) //插入的值已經存在
{
return false;
}
//擴容
if (_tables.size() == 0 || 10 * _n / _tables.size() >= 7) //負載因子
{
size_t newSize = _tables.size() == 0 ? 10 : _tables.size() * 2; //擴容
HashTable<K, V> newHT;
newHT._tables.resize(newSize); //擴容后用一個新表
//遍歷舊表，把舊表每個存在的元素插入newHT
for (auto& e : _tables)
{
if (e._state == EXIST)
{
newHT.Insert(e._kv);
}
}
newHT._tables.swap(_tables);//建立映射關系后交換
}
size_t hashi = kv.first % _tables.size(); //1.遇到空就停止了
//線性探測
while (_tables[hashi]._state == EXIST)
{
hashi++;
hashi %= _tables.size(); //2. 可能出表
}
_tables[hashi]._kv = kv;
_tables[hashi]._state = EXIST;
++_n;
return true;
}如果哈希表中已經有插入的值時，我們就要去除冗雜，用find函數。
3.4查找與刪除
查找的大致思路和插入的很接近，這里就不在重復了。
//查找
HashData<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]._kv.first == key)
{
return &_tables[hashi]; //返回的是地址
}
hashi++;
hashi %= _tables.size();
}
return nullptr;
}
//刪除
bool Erase(const K& key)
{
HashData<K, V>* ret=Find(key);
if (ret)
{
ret->_state = DELETE;
--_n;
}
else
{
return false;
}
}刪除時，我們直接把要刪除的數據狀態改成DELETE就行了，甚至內部的數據都不用刪除。
3.5仿函數?
這里的取模用的都是整數，那如果數據是浮點型？更甚至是字符串怎么搞？所依我們就要用到仿函數來進行類型轉換。
//利用仿函數將數據類型轉換為整型
template<class K>
struct HashFunc
{
size_t operator()(const K& key)
{
return (size_t)key;
}
};
//模板的特化
template<>
struct HashFunc<string> //如果是字符串，直接調用特化模板
{
size_t operator()(const string& key)
{
size_t hash = 0;
for (auto ch : key)
{
hash = hash * 131 + ch;//把所有字符的ascii碼值累計加起來
}
return hash;
}
};完整cpp表
#pragma once
#include<vector>
#include<iostream>
using namespace std;
enum State
{
EMPTY, //0 空
EXIST, //1 存在
DELETE, // 2 已刪除
};
template<class K, class V>
struct HashData
{
pair<K, V> _kv;//數據
State _state = State::EMPTY;//狀態 --空
};
//利用仿函數將數據類型轉換為整型
template<class K>
struct HashFunc
{
size_t operator()(const K& key)
{
return (size_t)key;
}
};
//模板的特化
template<>
struct HashFunc<string>
{
size_t operator()(const string& key) //字符串直接使用
{
size_t hash = 0;
for (auto ch : key)
{
hash = hash * 131 + ch;//把所有字符的ascii碼值累計加起來
}
return hash;
}
};
template<class K, class V,class Hash = HashFunc<K>>
class HashTable
{
public:
//插入
bool Insert(const pair<K, V>& kv)
{
if (Find(kv.first)) //插入的值已經存在
{
return false;
}
//擴容
if (_tables.size() == 0 || 10 * _n / _tables.size() >= 7) //負載因子
{
size_t newSize = _tables.size() == 0 ? 10 : _tables.size() * 2; //擴容
HashTable<K, V> newHT;
newHT._tables.resize(newSize); //擴容后用一個新表
//遍歷舊表，把舊表每個存在的元素插入newHT
for (auto& e : _tables)
{
if (e._state == EXIST)
{
newHT.Insert(e._kv);
}
}
newHT._tables.swap(_tables);//建立映射關系后交換
}
Hash hf;
size_t start = hf(kv.first);//取出鍵值對的key，并且避免了負數的情況，借用仿函數確保是整型數據
start %= _tables.size();
size_t hashi = start;
size_t i = 1;
//1.遇到空就停止了
//線性探測
while (_tables[hashi]._state == EXIST)
{
hashi++;
hashi %= _tables.size(); //2. 可能出表
}
_tables[hashi]._kv = kv;
_tables[hashi]._state = EXIST;
++_n;
return true;
}
//查找
HashData<K, V>* Find(const K& key)
{
if (_tables.size() == 0)
{
return nullptr;
}
Hash hf;
size_t start = hf(key);//通過仿函數把其它類型數據轉為整型數據
start %= _tables.size();
size_t hashi = start;
size_t i = 1;
while (_tables[hashi]._state != EMPTY)
{
if (_tables[hashi]._kv.first == key)
{
return &_tables[hashi]; //返回的是地址
}
hashi++;
hashi %= _tables.size();
}
return nullptr;
}
//刪除
bool Erase(const K& key)
{
HashData<K, V>* ret=Find(key);
if (ret)
{
ret->_state = DELETE;
--_n;
}
else
{
return false;
}
}
private:
vector<HashData<K, V>> _tables;//哈希表
size_t _n = 0;//存儲哈希表中有效數據的個數
};
void testHash1()
{
int a[] = { 1,11,4,15,26,7 };
HashTable<int, int> ht;
for (auto e : a)
{
ht.Insert(make_pair(e, e));
}
}4.開散列哈希桶
4.1概念
開散列也叫拉鏈法：先對所有key用散列函數計算散列地址，把有相同地址的key每個key都作為一個桶，通過單鏈表鏈接在哈希表中。
此時的表里面存儲一個鏈表指針，就是把沖突的數據通過鏈表的形式掛起來。
它的算法公式：hash(key)=key%capacity
這里的插入可以是頭插也可以是尾插，插入時是無序的。
也就是說哈希桶的根本是一個指針數組，哈希桶的每一個位置存的都是一個鏈表指針。
這個指針數組里的每一個元素都是結點指針，并且頭插的效率比較高。
4.2仿函數?
這次我們先弄模板來將其他類型轉換為size_t。
namespace OpenHash
{
template<class K>
struct Hash
{
size_t operator()(const K& key)
{
return key;
}
};
// 特化
template<>
struct Hash < string >
{
size_t operator()(const string& s)
{
// BKDR Hash
size_t value = 0;
for (auto ch : s)
{
value += ch;
value *= 131;
}
return value;
}
};
}4.3哈希桶結點構建?
因為是指針數組，所以結點中的成員變量多了一個指向下一個桶的指針。
//結點類
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 Hash = HashFunc<K>>
class HashTable
{
typedef HashNode<K, V> Node;
public:
//相關功能的實現……
private:
//指針數組
vector<Node*> _tables;
size_t _n = 0;//記錄有效數據的個數
};4.4哈希桶的查找和刪除
這里的查找\刪除操作和上面的如出一轍，但是哈希桶的存儲是鏈表的形式，所以會和鏈表的相關操作很接近。
//查找
Node* Find(const K& key)
{
//防止后續除0錯誤
if (_tables.size() == 0)
{
return nullptr;
}
//構建仿函數
HashFunc hf;
//找到對應的映射下標位置
size_t hashi = hf(key);
hashi %= _tables.size();
Node* cur = _tables[hashi];
//在此位置的鏈表中進行遍歷查找
while (cur)
{
if (cur->_kv.first == key)
{
//找到了
return cur;
}
cur = cur->_next;
}
//遍歷結束，沒有找到，返回nullptr
return nullptr;
}
//刪除
bool Erase(const K& key)
{
if (_tables.size() == 0)
{
return nullptr;
}
size_t hashi = key % _tables.size();
Node* cur = _tables[hashi];
Node* prev = nullptr;
while (cur)
{
if (cur->_kv.first == key)
{
//1.頭刪
if (prev == nullptr)
{
_tables[hashi] = cur->_next;
}
else //中間位置刪除
{
prev->_next = cur->_next;
}
delete cur;
return true;
}
prev = cur;
cur = cur->_next;
}
return false;
}4.5哈希桶的插入?
去除重復：
- 插入的值可能 已經存在，所以用用Find先進行查找
- 找到就返回false,沒找到再進行插入。
空間擴容
- 如果負載因子==1就進行擴容。
- 建立一個新哈希表，把舊表的值插入到新表。
- 再把新表交換到舊表那里。
但是在把舊表映射到新表時要釋放掉舊表，vector類型會自動調用析構函數，然而存儲的數據是Node*類型的，是內置類型，不會自動釋放，結果就是哈希表釋放了但是表中存的數據沒釋放，所以我們要手寫一個析構函數。
頭插操作
- 根仿函數找到合適映射位置
- 進行頭插操作并更新桶內數據個數。
所以我們首先寫一個析構函數：
//析構函數
~HashTable()
{
for (size_t i = 0; i < _tables.size(); i++)
{
Node* cur = _tables[i];
while (cur)
{
Node* next = cur->_next;
delete cur;
cur = next;
}
_tables[i] = nullptr;//釋放后置空
}
}整體代碼：
//插入
bool Insert(const pair<K, V>& kv)
{
//1、去除重復
if (Find(kv.first))
{
return false;
}
//2、負載因子 == 1就擴容
if (_tables.size() == _n)
{
size_t newSize = _tables.size() == 0 ? 10 : _tables.size() * 2;
vector<Node*> newTable;
newTable.resize(newSize, nullptr);
for (size_t i = 0; i < _tables.size(); i++)//遍歷舊表
{
Node* cur = _tables[i];
while (cur)
{
Node* next = cur->_next;
size_t hashi = hf(cur->_kv.first) % newSize;//確認映射到新表的位置
//頭插
cur->_next = newTable[hashi];
newTable[hashi] = cur;
cur = next;
}
_tables[i] = nullptr;
}
newTable.swap(_tables);
}
//3、頭插
//構建仿函數，把數據類型轉為整型，便于后續建立映射關系
HashFunc hf;
size_t hashi = hf(kv.first);
hashi %= _tables.size();
//頭插到對應的桶即可
Node* newnode = new Node(kv);
newnode->_next = _tables[hashi];
_tables[hashi] = newnode;
++_n;
return true;
}原文鏈接：https://blog.csdn.net/bit_jie/article/details/127957284
相關推薦
- 2022-07-01 python神經網絡Keras實現GRU及其參數量_python
- 2022-01-23 SpringBoot時區問題解決，徹底解決時差問題
- 2022-03-26 C語言二叉樹的遍歷示例介紹_C 語言
- 2023-06-19 CentOS7使用yum安裝Golang的超詳細步驟_Golang
- 2023-07-27 使用Echarts圖表時，頁面切換后并且改變頁面窗口大小，再切回原來頁面Echarts圖表顯示有問題
- 2023-04-12 你真的理解C語言qsort函數嗎?帶你深度剖析qsort函數_C 語言
- 2022-06-17 一文輕松了解ASP.NET與ASP.NET?Core多環境配置對比_實用技巧
- 2022-09-17 ASP.NET?Core項目中集成TypeScript_實用技巧
- 最近更新
-
- window11 系統安裝 yarn
- 超詳細win安裝深度學習環境2025年最新版（
- Linux 中運行的top命令 怎么退出？
- MySQL 中decimal 的用法？ 存儲小
- get 、set 、toString 方法的使
- @Resource和 @Autowired注解
- Java基礎操作-- 運算符，流程控制 Flo
- 1. Int 和Integer 的區別，Jav
- spring @retryable不生效的一種
- Spring Security之認證信息的處理
- Spring Security之認證過濾器
- Spring Security概述快速入門
- Spring Security之配置體系
- 【SpringBoot】SpringCache
- Spring Security之基于方法配置權
- redisson分布式鎖中waittime的設
- maven:解決release錯誤：Artif
- restTemplate使用總結
- Spring Security之安全異常處理
- MybatisPlus優雅實現加密？
- Spring ioc容器與Bean的生命周期。
- 【探索SpringCloud】服務發現-Nac
- Spring Security之基于HttpR
- Redis 底層數據結構-簡單動態字符串（SD
- arthas操作spring被代理目標對象命令
- Spring中的單例模式應用詳解
- 聊聊消息隊列，發送消息的4種方式
- bootspring第三方資源配置管理
- GIT同步修改后的遠程分支
提供CDN加速