19、HashTable（哈希）、位圖的實現和布隆過濾器的介紹

一、了解哈希【散列表】

1、哈希的結構

在這里插入圖片描述

在STL中，HashTable是一個重要的底層數據結構, 無序關聯容器包括unordered_set, unordered_map內部都是基于哈希表實現
- 哈希表又稱散列表，一種以「key-value」形式存儲數據的數據結構。
- 哈希函數：負責將任意大小的輸入映射到固定大小的輸出，即哈希值。
  - 這個哈希值作用：是放在在數組中存儲鍵值對的索引。
- 哈希沖突：由于哈希函數的映射不是一對一的，可能會出現兩個不同的鍵映射到相同的索引，即沖突。

解決沖突的方法：
鏈地址法
開發尋址法
雙重哈希

2、哈希函數

定義：將鍵（任意類型）映射為固定大小的整數（哈希值），決定數據在哈希桶中的存儲位置。

可能出現的情況
沖突情況 ：將兩個或兩個以上的不同key映射到同一地址。

3、hash操作

插入
查找

4、哈希的負載因子【重點】

負載因子 = 存儲的元素個數/數組長度
用來形容散列表的存儲密度
負載因子越小，沖突越小，負載因子越大，沖突越大。
描述沖突的程度。

5、哈希沖突的解決方法

5.1、鏈地址法

在這里插入圖片描述
方法一：拉鏈法（鏈表法）將具有相同的addr的key，可以用鏈表連接。但是負載因子要在合理范圍內。

5.2、開發尋址法

方法二：開發尋址法

將所有的數據直接存儲在哈希數組中。如果沖突就采用某種算法來改變位置。
- 算法有多種思路：
- 比如 i+1，i+2，i+3等等或者 i^1, i ^ 2 , i ^3等等。但是他們會出現hash聚集，也就是近似值的hash值很接近，那么位置也接近。聚集的話，就會在一片區域內，查找，這片區域數據太多了，時間復雜從O（1）變O（n）。所以可以使用雙重哈希解決。 但是負載因子要在合理范圍內。

6、分布式一致性哈希

6.1、了解

一致性哈希通過環形哈希空間（Hash Ring）和 虛擬節點（Virtual Nodes）優化數據分布。

解決傳統哈希表在節點數量變化時導致的全局數據遷移問題（例如模運算哈希的 hash(key) % N，當 N 變化時所有數據需重新分布）。
一致性哈希，當節點增刪時，僅影響環上相鄰節點的數據，避免全局數據遷移。

6.2、哈希環

將節點和數據通過哈希函數映射到一個環形空間（通常范圍為 0 ~ 2^32 - 1）
節點和數據的位置由哈希值決定。

每個數據項沿環順時針查找最近的節點作為存儲位置。

6.3、基本原理

在這里插入圖片描述

第一步：
- 創建哈希環。
- 將節點和數據通過哈希函數映射到一個環形空間
第二步：
- 將數據 a 、b 、c 通過哈希函數確定環上的位置，放上去。

在這里插入圖片描述

第三步
- 確定a、b、c映射到哪一個節點上。
- 按順時針順序，將a、b、c映射到離它們最近的節點。

在這里插入圖片描述

第四步
- 新增節點4，放在 1和2之間：僅需將環上相鄰節點的部分數據遷移到新節點。

在這里插入圖片描述

第五步
- 刪除節點 4 ，把節點4上的數據 a 遷移到節點2上
- - 移除節點：該節點的數據順時針遷移到下一個相鄰節點。

6.4、虛擬節點

在這里插入圖片描述

問題：
- 若物理節點較少，數據可能分布不均【哈希偏移】, 如上圖。
- 哈希偏移:
  - 在一致性哈希中，如果節點數量較少，可能會導致數據分布不均勻，某些節點負載過高，而其他節點負載較低。
解決：
- 每個物理節點映射多個虛擬節點 。
- 數據最終存儲在虛擬節點對應的物理節點。

虛擬節點的優點

數據分布均勻
虛擬節點將物理節點的負載分散到哈希環的多個位置，避免數據傾斜。

動態擴容
增加物理節點時，只需為其分配虛擬節點，數據遷移量較少。

容錯性
刪除物理節點時，其虛擬節點對應的數據會遷移到其他物理節點，系統仍然保持平衡。

7、哈希的代碼

#include<cstddef>
#include<cstdio>
#include<cstdlib>
#include<sstream>
#include<vector>
#include<functional>
#include<utility>
#include<list>
#include<string>
#include<iostream>
#include<algorithm>
using namespace std;
template<class Key,class Value,class Hash=hash<Key>>
class HashTable{class HashNode{public:Key key;Value value;//從key構造節點，Value使用默認構造explicit HashNode(const Key& key):key(key),value(){}//從key和value構造節點HashNode(const Key&key,const Value& value):key(key),value(value){}//比較運算符，只按key來比較bool operator==(const HashNode& other)const{return key==other.key;}bool operator!=(const HashNode& other)const{return key!=other.key;}bool operator<(const HashNode& other)const{return key<other.key;}bool operator>(const HashNode& other)const{return key>other.key;}bool operator==(const Key& key)const{return this->key==key;}//打印void print ()const{cout<<key<<" "<<value<<" ";}};private:using Bucket = list<HashNode>;//定義桶的類型為存儲鍵的鏈表vector<Bucket> buckets;       //存儲所有桶的動態數組size_t tableSize;             //哈希表的大小，即桶的數量size_t numElements;           //哈希中的元素的數量float maxLoadFator = 0.75;    //默認最大負載因子Hash hashFunction;            //哈希函數對象//計算哈希值，并將其映射到桶的索引size_t hash(const Key& key)const{return hashFunction(key) % tableSize;}//當元素數量超過最大負載因子定義的容量時，增加桶的數量并重新分配所有鍵void rehash(size_t newSize){vector<Bucket> newBucket(newSize);//創建新的桶組for(Bucket& bucket:buckets){//遍歷舊桶//遍歷桶中的每一個鍵for(HashNode& hashNode:bucket){//因為這里是新的newSize計算，所以不能用hash(key)來求size_t newIndex=hashFunction(hashNode.key)%newSize;newBucket[newIndex].push_back(hashNode);//將鍵重新放入桶中}}buckets = move(newBucket);//使用移動語義更新桶數組tableSize = newSize;}
public://構造函數初始化哈希表HashTable(size_t size = 10,const Hash& hashFunc = Hash()):buckets(size),hashFunction(hashFunc),tableSize(size),numElements(0){}//插入鍵到哈希表中void insert(const Key&key,const Value& value){if((numElements+1)>maxLoadFator*tableSize){//檢查是否需要重哈希//處理clear后再次插入元素時，tableSize = 0 的情況if(tableSize==0)tableSize = 1;rehash(tableSize*2);// 重哈希，桶數量翻倍}size_t index = hash(key);    //計算鍵的索引list<HashNode>& bucket = buckets[index];//獲取對應的桶//如果不在桶中，則添加到桶中if(find(bucket.begin(),bucket.end(),key)==bucket.end()){bucket.push_back(HashNode(key,value));++numElements;}}void insertKey(const Key&key){insert(key,Value{});}//從哈希表中移除鍵void erase(const Key& key){size_t index = hash(key);//計算鍵的索引auto & bucket = buckets[index];//獲取對應的桶auto it = find(bucket.begin(),bucket.end(),key);//查找鍵if(it!=bucket.end()){bucket.erase(it);//刪除鍵numElements--;//減少元素的數量}}//查找鍵是否在哈希表中Value* findKey(const Key& key){size_t index = hash(key);//計算鍵的索引auto & bucket = buckets[index];//獲取對應的桶auto it = find(bucket.begin(),bucket.end(),key);//查找鍵if(it!=bucket.end()){return &it->value;}return nullptr;}//獲取哈希表中的元素數量size_t size()const {return numElements;}//打印哈希表中的所有元素void print()const{for(size_t i = 0;i<buckets.size();++i){for(const HashNode& element:buckets[i]){element.print();}}cout<<endl;}void clear(){this->buckets.clear();this->numElements=0;this->tableSize = 0;}
};
int main(int argc, char const *argv[])
{//創建一個哈希表實例HashTable<int, int> hashTable;int n;cin>>n;getchar();string line;for(int i = 0;i<n;i++){getline(cin,line);istringstream iss(line);string command;iss>>command;int key;int value;if(command=="insert"){iss>>key>>value;hashTable.insert(key,value);}if(command == "erase"){if(hashTable.size()==0){continue;}iss>>key;hashTable.erase(key);}if(command=="find"){if(hashTable.size()==0){cout<<"not exist"<<endl;continue;}iss>>key;int* res = hashTable.findKey(key);if(res!=nullptr){cout<<*res<<endl;}else{cout<<"not exist"<<endl;}}if(command=="print"){if(hashTable.size()==0){cout<<"empty"<<endl;}else{hashTable.print();}}if(command=="size"){cout<<hashTable.size()<<endl;}if(command=="clear"){hashTable.clear();}}return 0;
}

二、位圖

1、問題一

騰訊問題：給40億個不重復的無符號整數，沒排過序。給一個無符號整數，如何快速判斷一個數是否在40億個數中。【哈希表：每個無符號整數占4字節。40億占的是16G】

1 B是 8 bit 。
1GB = 1024MB。
1MB = 1024 KB 。
1KB = 1024B 。
40 億個無符號整數是每個數 4字節。就有 160 億字節
160億字節/1024/1024/1024 ≈ 14.9 GB

2、介紹

創建一段數組空間，用比特 1 和 0 來表示存在和不存在（1是存在，0是不能存在）。

3、實現位圖的計算

void set(size_t x) {size_t index = x / 32;  // 定位到哪個 intsize_t pos = x % 32;    // 定位到 int 的哪一位bits[index] |= (1 << pos);//更新pos位置的 1
}

例如 x = 37：
- index = 37 / 32 = 1（第 2 個 int）
  - 假設 bit[index]= 0000 0100
- pos = 37 % 32 = 5（第 5 位）
  - 得pos = 0001 0000
- bits[1] |= (1 << 5) 將第 37 位設為 1
- 0000 0100 | 0001 000 = 0001 0100 。保持了原來的位的1，并更新了現在要改的位為 1

3、操作

3.1、了解運算符

在這里插入圖片描述

3.2、位圖操作

在這里插入圖片描述

4、位圖的優缺點

查找很快
但是只能用于整型

5、代碼實現

#include <cstddef>
#include<vector>
#include<iostream>
using namespace std;
namespace bit{class bitset{public:explicit bitset(size_t N){bits.resize(N/32+1,0);//如果是32的倍數，會多分配一個int}//設置位圖void set(size_t x){size_t index = x/32;//算出x映射的位在第幾個整型size_t pos = x%32;//算出x在這個整型的第幾個位置bits[index]|= (1<<pos);//保留原來的1 ，設置現在需要 位 的1++num;}第pos個位置設置為0void reset(size_t x){size_t index = x/32;//算出x映射的位在第幾個整型size_t pos = x%32;//算出x在這個整型的第幾個位置bits[index] &= ~(1<<pos);//第pos個位置設置為0}//判斷x在不在bool test(size_t x){size_t index = x/32;size_t pos = x%32;return bits[index]&(1<<pos);}private:vector<int> bits;size_t num;//個數};
};
void test_bitset(){using namespace bit;bitset bs(100);bs.set(99);bs.set(98);bs.set(97);for(size_t i =0;i<100;++i){cout<<"[%d]:%d\n"<<i<<static_cast<int>(bs.test(i))<<endl;}
}
int main(int argc, char const *argv[])
{test_bitset();return 0;
}