目錄
unordered系列關聯式容器
哈希的簡介
哈希表閉散列實作
哈希表開散列實作
用哈希表來封裝map和set
位圖
布隆過濾器與哈希切割
全部代碼
unordered系列關聯式容器
unordered系列關聯式容器有四種，這裡主要對unordered_map和unordered_set這兩種容器進行介紹
unordered_map
unordered_map是存儲<key, value>鍵值對的關聯式容器，其允許通過keys快速的索引到與其對應的value
在内部,unordered_map沒有對<kye, value>按照任何特定的順序排序
unordered_map容器通過key通路單個元素要比map快，但它通常在周遊元素子集的範圍疊代方面效率較低
unordered_maps實作了直接通路操作符(operator[])，它允許使用key作為參數直接通路value
unordered_set
unordered_set和unordered_map在性質上差不多，因為底層結構是一緻的，都是哈希結構，差別在與，unordered_set不支援[]，因為它存儲的是key與value相同，是以無需支援[]
哈希的簡介
概念
如果構造一種存儲結構，通過某種函數(hashFunc)使元素的存儲位置與它的關鍵碼之間能夠建立一一映射的關系，那麼在查找時通過該函數可以很快找到該元素
哈希函數有多種，這裡采用除留餘數法
哈希沖突
比如14和4取模後都是4，而4對應的位置隻能存儲一個數字，那麼就出現了哈希沖突，而解決哈希沖突的常見兩種方法有閉散列和開散列
哈希表閉散列實作
閉散列：也叫開放定址法，當發生哈希沖突時，如果哈希表未被裝滿，說明在哈希表中必然還有空位置，那麼可以把key存放到沖突位置中的“下一個” 空位置中去
尋找下一空位置有線性探測和二次探測兩種
線性探測
從發生沖突的位置開始，依次向後探測，直到尋找到下一個空位置為止
二次探測
從發生沖突的位置開始，跨越探測，直到尋找到下一個空位置為止
index是哈希表的下标
首先因為有閉散列和開散列兩種，是以采用命名空間的形式來防止命名沖突
然後定義一個枚舉類型，用來判斷該下标的空間的狀态，是存在資料，還是删除過資料，或者沒有資料，便于插入，删除，及查找資料
封裝節點，開始必然為每個下标所在的空間必然為空狀态，是以初始化為空狀态
因為要是除留取餘法，必然要是整數，是以還需要借助仿函數來實作
内置類型
string類型
string類型轉整形，可以将字元串的每個字母的ASCII碼值加起來，但要是隻是順序不同，那總數也會相同，出現哈希沖突，為了盡量減少哈希沖突，就有了下圖的方法，其中31是累乘因子
string類型有下列兩種寫法，任選其一即可
對于其它自定義類型，比如日期，則按照特定方式取整即可
哈希表同樣采用模闆的形式實作，另外私有成員有中的_n是有效資料個數，便于後續插入資料擴容使用
查找資料
如果表為空，則直接傳回nullptr即可
首先用待查找的key模表的長度取模作為待查找的初始下标，然後一直往後查找，同時往後走時，最後别忘了再取模一次，因為可能會存在初始下标空間的前面空間，找不到時，則直接傳回nullptr
删除資料
首先先查找資料，找到資料了有效資料就減少一個，然後将那個節點的狀态置為删除狀态，删除成功傳回true即可，沒找到就表示删除失敗，傳回false
插入資料
首先先查找資料，如果存在，就表示待插入的資料已經有了，是以無需再插入，傳回false即可
根據有效資料個數，得到負載因子，如果負載因子大于等于0.7則表示需要擴容了，初始沒有空間時，也一樣需要擴容
負載因子越小，沖突機率越低，效率越高，空間浪費越多
負載因子越大，沖突機率越高，效率越低，空間浪費越少
如果是初始時則開10個空間，其它情況則直接開原來的2倍空間
建立一個新表，開辟新空間大小的空間，再将其資料拷貝到新表，然後将新表對象中的vector成員與this對象中的vector成員交換即可
如果不需要開辟新空間
則先将key取模，找到對應的下标，如果有空間，則直接插入資料，沒有，則繼續往後面找，與find()類似，最後有效資料+1，傳回true即可
閉散列最大的缺陷就是空間使用率比較低，這也是哈希的缺陷
哈希表開散列實作
概念
開散列法又叫鍊位址法(開鍊法)，首先對關鍵碼集合用散列函數計算散列位址，具有相同位址的關鍵碼歸于同一子集合，每一個子集合稱為一個桶，各個桶中的元素通過一個單連結清單連結起來，各連結清單的頭結點存儲在哈希表中，開散列中每個桶中放的都是發生哈希沖突的元素，如下圖
封裝節點，其實就是單連結清單的節點封裝
私有成員與閉散列一緻，同時，還是采用除留去餘法，是以會用到仿函數，與上面閉散列一緻
查找資料
如果哈希表為空，則直接傳回nullptr
找到待查找的資料節點的下标，以及聲明一個局部變量來儲存這條鍊的頭節點
從頭開始往後找，找到了傳回節點位址，沒找到傳回nullptr
删除資料
如果哈希表為空，傳回false，表示删除失敗
找到待删除資料節點的那條鍊的頭節點
如果找到了，則分為兩種情況，如果就是頭節點，那就直接頭删，否則就中間删除
如果沒找到，則繼續往後面找，找不到則傳回false，表示删除失敗
插入資料
首先先查找資料，如果存在，就表示待插入的資料已經有了，是以無需再插入，傳回false即可
如果負載因子等于1時，則需要擴容，初始開空間時開10個空間，其餘情況開原來的2倍空間
然後将原表的資料按頭插拷貝到新表，将原表每條鍊的表頭置空，最後再交換this對象的vector成員與新表的vector成員即可
如果不需要擴容，則直接頭插，然後将有效資料個數+1，再傳回true即可
為了減少哈希沖突，每次擴容後的空間大小都為素數
用哈希表來封裝map和set
改善哈希表
因為既要封裝map，又要封裝set，是以将資料類型從pair類型變為了T類型
疊代器
因為會用到哈希表，是以提前聲明一下
因為要封裝map和set，是以多加了一個模闆參數KeyOfT，采用了仿函數
因為map和set存儲的資料不同，一個是pair<key,value>，一個是key是以對*和對->都要重載
判斷相不相等，比較的是節點的位址相不相等
重載++運算符
如果這條鍊上還有節點，即沒有遇到nullptr，則直接往後走即可
如果為nullptr，則從哈希表的下一個元素開始找，比如下圖，走完11後，則繼續往後面走，下一個元素表頭為空，是以就走到了13，不為nullptr，則跳出循環
如果是循環自動結束的，即走完整個哈希表了，則直接置nullptr即可
如果是break出來的，則直接傳回到那個節點，比如上述所說的13
拷貝構造
别忘了寫一個預設構造函數，因為有了拷貝構造之後，編譯器不會預設生成了
這裡采用的是頭插法，是以順序會有變化
重載指派運算符
将實參傳給形參時會有一次拷貝構造，是以隻需将this對象的兩個成員與形參的交換即可
析構函數
從哈希表第一個元素開始銷毀節點，直到走完哈希表結束
初始節點
如果哈希表第一個元素的頭節點不為nullptr，則它就是初始節點，否則直接傳回nullptr的疊代器
結尾節點，即nullptr
重載[]運算符
[]可查找value，也可修改或插入
位圖
位圖的作用：資料是否在給定的整形資料中，結果是在或者不在，剛好是兩種狀态，那麼可以使用一個二進制比特位來代表資料是否存在的資訊，如果二進制比特位為1，代表存在，為0代表不存在，比如在一堆資料中找5在不在，資料很多時，可以開辟整形最大值那麼大的以bit為機關的空間，然後一個整數對應一個比特位，如果5對應的比特位是1，那就在這堆資料中，是0就不在
1byte=8bit，是以開空間數如下圖
将某個bit位置為1
将某個bit位置為0
檢查某個bit位是否為1
0為假，非0為真
位圖：節省空間，效率高，但隻能處理整數
布隆過濾器與哈希切割
概念
布隆過濾器是由布隆在1970年提出的 一種緊湊型的、比較巧妙的機率型資料結構，特點是高效地插入和查詢，可以用來告訴你 “某樣東西一定不存在或者可能存在”，它是用多個哈希函數，将一個資料映射到位圖結構中。既可以提升查詢效率，也可以節省大量的記憶體空間
作用：用來解決字元串，自定義類型對象在不在的問題
如果采用将字元串轉整數，即将字元串的各個字元加起來取模作為下标，那就可能會存在哈希沖突，比如下圖中eat和ate
這種方式，判斷不在是準确的，比如eat和ate那個位置的比特位為0，則eat肯定不在，隻是判斷在會存在誤判
解決方式
将一個元素用多個哈希函數映射到一個位圖中，比如ate，隻要三個種有一個bit位為0，則就表示ate不在，降低了誤判率
這裡以哈希函數中三個不同的哈希函數為例
模闆參數
//hashTable-副本
#pragma once
#include<vector>
template<class K>
struct Hash
{
size_t operator()(const K& key)
{
return key;
}
};
//特化
template<>
struct Hash< string >
{
size_t operator()(const string& s)
{
//BKDR
size_t value = 0;
for (auto ch : s)
{
value *= 31;
value += ch;
}
return value;
}
};
namespace CloseHash
{
enum Status
{
EXIST,
EMPTY,
DELETE
};
template<class K,class V>
struct HashData
{
pair<K, V> _kv;
Status _status = EMPTY;
};
struct HashStr
{
size_t operator()(const string& s)
{
//BKDR
size_t value = 0;
for (auto ch : s)
{
value *= 31;
value += ch;
}
return value;
}
};
template<class K,class V,class HashFunc = Hash<K>>
class HashTable
{
public:
bool Erase(const K& key)
{
HashData<K, V>* ret = Find(key);
if (ret == nullptr)
{
return false;
}
else
{
--_n;
ret->_status = DELETE;
return true;
}
}
HashData<K, V>* 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;
//線性探測 or 二次探測
while (_tables[index]._status != EMPTY)
{
if (_tables[index]._kv.first == key && _tables[index]._status == EXIST)
{
return &_tables[index];
}
++i;
//index = start + i*i;
index = start + i;
index %= _tables.size();
}
return nullptr;
}
bool Insert(const pair<K, V>& kv)
{
HashData<K, V>* ret = Find(kv.first);
if (ret)
{
return false;
}
//負載因子到0.7，就擴容
//負載因子越小，沖突機率越低，效率越高，空間浪費越多
//負載因子越大，沖突機率越高，效率越低，空間浪費越少
if (_tables.size() == 0 || _n * 10 / _tables.size() >= 7)
{
//擴容
size_t newSize = _tables.size() == 0 ? 10 : _tables.size() * 2;
//vector<HashData<K,V>> newTables;
//newTables.resize(newSize);
//周遊原表，把原表中的資料，重新按newSize映射到新表
//for(size_t i = 0;i < _tables.size();++i)
//{
//
//}
//_tables.swap(newTables);
HashTable<K, V, HashFunc> newHT;
newHT._tables.resize(newSize);
for (size_t i = 0; i < _tables.size(); ++i)
{
if (_tables[i]._status == EXIST)
{
newHT.Insert(_tables[i]._kv);
}
}
_tables.swap(newHT._tables);
}
HashFunc hf;
size_t start = hf(kv.first) % _tables.size();
size_t i = 0;
size_t index = start;
//線性探測 or 二次探測
while (_tables[index]._status == EXIST)
{
++i;
//index = start + i * i;
index = start + i;
index %= _tables.size();
}
_tables[index]._kv = kv;
_tables[index]._status = EXIST;
++_n;
return true;
}
private:
vector<HashData<K, V>> _tables;
size_t _n = 0;//有效資料個數
};
void TestHashTable1()
{
//HashTable<int,int,Hash<int>> ht;
HashTable<int, int> ht;
int a[] = { 2,12,22,32,42,52,62 };
for (auto e : a)
{
ht.Insert(make_pair(e, e));
}
ht.Insert(make_pair(72, 72));
ht.Insert(make_pair(72, 72));
ht.Insert(make_pair(-1, -1));
ht.Insert(make_pair(-999, -999));
Hash<int> hs;
cout << hs(9) << endl;
cout << hs(-9) << endl;
cout << ht.Find(12) << endl;
ht.Erase(12);
cout << ht.Find(12) << endl;
}
struct Date
{
};
struct HashDate
{
size_t operator()(const Date& d)
{
//...
}
};
void TestHashTable2()
{
HashStr hs;
cout << hs("sort") << endl;
cout << hs("insert") << endl;
cout << hs("eat") << endl;
cout << hs("ate") << endl;
cout << hs("abcd") << endl;
cout << hs("aadd") << endl;
HashTable<string, string> ht;
ht.Insert(make_pair("sort", "排序"));
ht.Insert(make_pair("string", "字元串"));
//當key是一個定義類型時，需要配置一個仿函數，将key轉成整形
HashTable<Date, string, HashDate> htds;
}
}
namespace LinkHash
{
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 HashTable
{
typedef HashNode<K, V> Node;
public:
bool Erase(const K& key)
{
if (_tables.empty())
{
return false;
}
HashFunc hf;
size_t index = hf(key) % _tables.size();
Node* prev = nullptr;
Node* cur = _tables[index];
while (cur)
{
if (cur->_kv.first == key)
{
if (prev == nullptr) //頭删
{
_tables[index] = cur->_next;
}
else //中間删除
{
prev->_next = cur->_next;
}
--_n;
delete cur;
return true;
}
else
{
prev = cur;
cur = cur->_next;
}
}
return false;
}
Node* Find(const K& key)
{
if (_tables.empty())
{
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 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;
++_n;
return true;
}
private:
/*struct Data
{
forward_list<T> _list;
set<T> _rbtree;
size_t len;
};
vector<Data> _table;*/
vector<Node*> _tables;
size_t _n = 0;//有效資料的個數
};
void TestHashTable()
{
int a[] = { 4,24,14,7,37,27,57,67,34,14,54 };
HashTable<int, int> ht;
for (auto e : a)
{
ht.Insert(make_pair(e, e));
}
ht.Insert(make_pair(84, 84));
}
};
//hashTable
#pragma once
#include<vector>
#include<string>
template<class K>
struct Hash
{
size_t operator()(const K& key)
{
return key;
}
};
//特化
template<>
struct Hash< string >
{
size_t operator()(const string& s)
{
//BKDR
size_t value = 0;
for (auto ch : s)
{
value *= 31;
value += ch;
}
return value;
}
};
namespace CloseHash
{
enum Status
{
EXIST,
EMPTY,
DELETE
};
template<class K, class V>
struct HashData
{
pair<K, V> _kv;
Status _status = EMPTY;
};
//struct HashStr
//{
// size_t operator()(const string& s)
// {
// //BKDR
// size_t value = 0;
// for (auto ch : s)
// {
// value *= 31;
// value += ch;
// }
// return value;
// }
//};
template<class K, class V, class HashFunc = Hash<K>>
class HashTable
{
public:
bool Erase(const K& key)
{
HashData<K, V>* ret = Find(key);
if (ret == nullptr)
{
return false;
}
else
{
--_n;
ret->_status = DELETE;
return true;
}
}
HashData<K, V>* 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;
//線性探測 or 二次探測
while (_tables[index]._status != EMPTY)
{
if (_tables[index]._kv.first == key && _tables[index]._status == EXIST)
{
return &_tables[index];
}
++i;
//index = start + i*i;
index = start + i;
index %= _tables.size();
}
return nullptr;
}
bool Insert(const pair<K, V>& kv)
{
HashData<K, V>* ret = Find(kv.first);
if (ret)
{
return false;
}
//負載因子到0.7，就擴容
//負載因子越小，沖突機率越低，效率越高，空間浪費越多
//負載因子越大，沖突機率越高，效率越低，空間浪費越少
if (_tables.size() == 0 || _n * 10 / _tables.size() >= 7)
{
//擴容
size_t newSize = _tables.size() == 0 ? 10 : _tables.size() * 2;
//vector<HashData<K,V>> newTables;
//newTables.resize(newSize);
//周遊原表，把原表中的資料，重新按newSize映射到新表
//for(size_t i = 0;i < _tables.size();++i)
//{
//
//}
//_tables.swap(newTables);
HashTable<K, V, HashFunc> newHT;
newHT._tables.resize(newSize);
for (size_t i = 0; i < _tables.size(); ++i)
{
if (_tables[i]._status == EXIST)
{
newHT.Insert(_tables[i]._kv);
}
}
_tables.swap(newHT._tables);
}
HashFunc hf;
size_t start = hf(kv.first) % _tables.size();
size_t i = 0;
size_t index = start;
//線性探測 or 二次探測
while (_tables[index]._status == EXIST)
{
++i;
//index = start + i * i;
index = start + i;
index %= _tables.size();
}
_tables[index]._kv = kv;
_tables[index]._status = EXIST;
++_n;
return true;
}
private:
vector<HashData<K, V>> _tables;
size_t _n = 0;//有效資料個數
};
void TestHashTable1()
{
//HashTable<int,int,Hash<int>> ht;
HashTable<int, int> ht;
int a[] = { 2,12,22,32,42,52,62 };
for (auto e : a)
{
ht.Insert(make_pair(e, e));
}
ht.Insert(make_pair(72, 72));
ht.Insert(make_pair(72, 72));
ht.Insert(make_pair(-1, -1));
ht.Insert(make_pair(-999, -999));
Hash<int> hs;
cout << hs(9) << endl;
cout << hs(-9) << endl;
cout << ht.Find(12) << endl;
ht.Erase(12);
cout << ht.Find(12) << endl;
}
struct Date
{
};
struct HashDate
{
size_t operator()(const Date& d)
{
//...
}
};
void TestHashTable2()
{
/*HashStr hs;
cout << hs("sort") << endl;
cout << hs("insert") << endl;
cout << hs("eat") << endl;
cout << hs("ate") << endl;
cout << hs("abcd") << endl;
cout << hs("aadd") << endl;*/
HashTable<string, string> ht;
ht.Insert(make_pair("sort", "排序"));
ht.Insert(make_pair("string", "字元串"));
//當key是一個定義類型時，需要配置一個仿函數，将key轉成整形
HashTable<Date, string, HashDate> htds;
}
}
namespace LinkHash
{
template<class T>
struct HashNode
{
T _data;
HashNode<T>* _next;
HashNode(const T& data) :_data(data), _next(nullptr)
{}
};
template<class K, class T,class KeyOfT, class HashFunc>
class HashTable;
template<class K,class T,class Ref,class Ptr,class KeyOfT,class HashFunc>
struct __HTIterator
{
typedef HashNode<T> Node;
typedef __HTIterator<K, T, Ref, Ptr, KeyOfT, HashFunc> Self;
Node* _node;
HashTable<K, T, KeyOfT, HashFunc>* _pht;
__HTIterator(Node* node,HashTable<K,T,KeyOfT,HashFunc>* pht):_node(node),_pht(pht)
{}
Ref operator*()
{
return _node->_data;
}
Ptr operator->()
{
return &_node->_data;
}
Self& operator++()
{
if (_node->_next)
{
_node = _node->_next;
}
else
{
KeyOfT kot;
HashFunc hf;
size_t index = hf(kot(_node->_data)) % _pht->_tables.size();
++index;
//找下一個不為空的值
while (index < _pht->_tables.size())
{
if (_pht->_tables[index])
{
break;
}
else
{
++index;
}
}
//表走完了，都沒有找到下一個桶
if (index == _pht->_tables.size())
{
_node = nullptr;
}
else
{
_node = _pht->_tables[index];
}
}
return *this;
}
bool operator!=(const Self& s) const
{
return _node != s._node;
}
bool operator==(const Self& s) const
{
return _node = s._node;
}
};
template<class K,class T,class KeyOfT,class HashFunc>
class HashTable
{
typedef HashNode<T> Node;
template<class K,class T,class Ref,class Ptr,class KeyOfT,class HashFunc>
friend struct __HTIterator;
typedef HashTable<K, T, KeyOfT, HashFunc> self;
public:
typedef __HTIterator<K, T, T&, T*, KeyOfT, HashFunc> iterator;
HashTable()
{}
//顯示指定編譯器去生成預設構造函數
//HashTable() = default;
HashTable(const self& ht)
{
_tables.resize(ht._tables.size());
for (size_t i = 0; i < ht._tables.size(); ++i)
{
Node* cur = ht._tables[i];
while (cur)
{
Node* copy = new Node(cur->_data);
copy->_next = _tables[i];
_tables[i] = copy;
cur = cur->_next;
}
}
}
//ht1 = ht2
self& operator=(self copy)
{
swap(_n, copy._n);
_tables.swap(copy._tables);
return *this;
}
~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;
}
}
iterator begin()
{
for (size_t i = 0; i < _tables.size(); ++i)
{
if (_tables[i])
{
return iterator(_tables[i], this);
}
}
return end();
}
iterator end()
{
return iterator(nullptr, this);
}
bool Erase(const K& key)
{
if (_tables.empty())
{
return false;
}
HashFunc hf;
size_t index = hf(key) % _tables.size();
Node* prev = nullptr;
Node* cur = _tables[index];
KeyOfT kot;
while (cur)
{
if (kot(cur->_data) == key)
{
if (prev == nullptr) //頭删
{
_tables[index] = cur->_next;
}
else //中間删除
{
prev->_next = cur->_next;
}
--_n;
delete cur;
return true;
}
else
{
prev = cur;
cur = cur->_next;
}
}
return false;
}
iterator Find(const K& key)
{
if (_tables.empty())
{
return end();
}
HashFunc hf;
size_t index = hf(key) % _tables.size();
Node* cur = _tables[index];
KeyOfT kot;
while (cur)
{
if (kot(cur->_data) == key)
{
return iterator(cur,this);
}
else
{
cur = cur->_next;
}
}
return end();
}
size_t GetNextPrime(size_t num)
{
static const unsigned long __stl_prime_list[28] =
{
53,97,193,389,769,
1543,3079,6151,12289,24593,
49157,98317,196613,393241,786433,
1572869,3145739,6291469,12582917,25165843,
50331653,100663319,201326611,402653189,805306457,
1610612741,3221225473,4294967291
};
for(size_t i = 0;i < 28;++i)
{
if (__stl_prime_list[i] > num)
{
return __stl_prime_list[i];
}
}
return __stl_prime_list[27];
}
pair<iterator,bool> Insert(const T& data)
{
KeyOfT kot;
iterator ret = Find(kot(data));
if (ret != end())
return make_pair(ret,false);
HashFunc hf;
//負載因子 == 1時擴容
if (_n == _tables.size())
{
//size_t newSize = _tables.size() == 0 ? 10 : _tables.size() * 2;
//...
size_t newSize = GetNextPrime(_tables.size());
/*if (newSize == _tables.size())
{
break;
}*/
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(kot(cur->_data)) % newTables.size();
//頭插
cur->_next = newTables[index];
newTables[index] = cur;
cur = next;
}
_tables[i] = nullptr;
}
_tables.swap(newTables);
}
size_t index = hf(kot(data)) % _tables.size();
Node* newnode = new Node(data);
//頭插
newnode->_next = _tables[index];
_tables[index] = newnode;
++_n;
return make_pair(iterator(newnode,this),false);
}
private:
/*struct Data
{
forward_list<T> _list;
set<T> _rbtree;
size_t len;
};
vector<Data> _table;*/
vector<Node*> _tables;
size_t _n = 0;//有效資料的個數
};
}
//unordered-map
#pragma once
#include"HashTable.h"
namespace bit
{
template<class K,class V,class hash = Hash<K>>
class unordered_map
{
struct MapKeyOfT
{
const K& operator()(const pair<K, V>& kv)
{
return kv.first;
}
};
public:
typedef typename LinkHash::HashTable<K, pair<K, V>, MapKeyOfT, hash>::iterator iterator;
iterator begin()
{
return _ht.begin();
}
iterator end()
{
return _ht.end();
}
V& operator[](const K& key)
{
auto ret = _ht.Insert(make_pair(key, V()));
return ret.first->second;
}
pair<iterator,bool> insert(const pair<K, V>& kv)
{
return _ht.Insert(kv);
}
private:
LinkHash::HashTable<K, pair<K,V>, MapKeyOfT, hash > _ht;
};
void test_unordered_map()
{
unordered_map<string, string> dict;
dict.insert(make_pair("sort", "排序"));
dict.insert(make_pair("string", "字元串"));
dict.insert(make_pair("map", "地圖、映射"));
/*cout << dict["sort"] << endl;
cout << dict["string"] << endl;
cout << dict["map"] << endl;*/
//dict["right"] = "右邊";
unordered_map<string, string>::iterator it = dict.begin();
while (it != dict.end())
{
cout << it->first << ":" << it->second << endl;
++it;
}
cout << endl;
unordered_map<string, string> copy(dict);
for (auto& kv : copy)
{
cout << kv.first << ":" << kv.second << endl;
}
cout << endl;
}
}
//unordered-set
#pragma once
namespace bit
{
template<class K,class hash = Hash<K>>
class unordered_set
{
struct SetKeyOfT
{
const K& operator()(const K& key)
{
return key;
}
};
public:
typedef typename LinkHash::HashTable<K, K, SetKeyOfT, hash>::iterator iterator;
iterator begin()
{
return _ht.begin();
}
iterator end()
{
return _ht.end();
}
pair<iterator,bool> insert(const K& key)
{
return _ht.Insert(key);
}
private:
LinkHash::HashTable<K, K, SetKeyOfT, hash> _ht;
};
void test_unordered_set()
{
unordered_set<int> us;
us.insert(4);
us.insert(14);
us.insert(34);
us.insert(7);
us.insert(24);
us.insert(17);
unordered_set<int>::iterator it = us.begin();
while (it != us.end())
{
cout << *it << " ";
++it;
}
cout << endl;
unordered_set<int> uss(us);
unordered_set<int>::iterator It = uss.begin();
while (It != uss.end())
{
cout << *It << " ";
++It;
}
cout << endl;
/*unordered_set<string> uss;
uss.insert("sort");
uss.insert("hash");*/
/*unordered_set<int> us;
for (size_t i = 0; i < 100; ++i)
{
us.insert(i);
}*/
}
}
//bitSet
#pragma once
#include<vector>
namespace bit
{
template<size_t N>
class bitset
{
public:
bitset()
{
_bits.resize(N / 8 + 1, 0);
}
void set(size_t x)
{
size_t i = x / 8;
size_t j = x % 8;
_bits[i] |= (1 << j);
}
void reset(size_t x)
{
size_t i = x / 8;
size_t j = x % 8;
_bits[i] &= (~(1 << j));
}
bool test(size_t x)
{
size_t i = x / 8;
size_t j = x % 8;
return _bits[i] & (1 << j);
}
private:
std::vector<char> _bits;
//std::vector<int> _bits;
};
void test_bitset()
{
bitset<100> bs;
bs.set(5);
bs.set(4);
bs.set(10);
bs.set(20);
cout << bs.test(5) << endl;
cout << bs.test(4) << endl;
cout << bs.test(10) << endl;
cout << bs.test(20) << endl;
cout << bs.test(21) << endl;
cout << bs.test(6) << endl << endl;
bs.reset(20);
bs.reset(10);
bs.reset(5);
cout << bs.test(5) << endl;
cout << bs.test(4) << endl;
cout << bs.test(10) << endl;
cout << bs.test(20) << endl;
cout << bs.test(21) << endl;
cout << bs.test(6) << endl;
//bitset<0xffffffff> bs;
//bitset<-1> bs;
}
}
template<size_t N>
class TwoBitSet
{
public:
void Set(size_t x)
{
if (!_bs1.test(x) && !_bs2.test(x)) //00 -> 01
{
_bs2.set(x);
}
else if (!_bs1.test(x) && _bs2.test(x)) //01 -> 10
{
_bs1.set(x);
_bs2.reset(x);
}
//10 表示已經出現2次或以上，不用處理
}
void PrintOnceNum()
{
for (size_t i = 0; i < N; ++i)
{
if (!_bs1.test(i) && _bs2.test(i)) // 01
{
cout << i << endl;
}
}
}
private:
bit::bitset<N> _bs1;
bit::bitset<N> _bs2;
};
void TestTwoBitSet()
{
int a[] = { 99,0,4,50,33,44,2,5,99,0,50,99,50,2 };
TwoBitSet<100> bs;
for (auto e : a)
{
bs.Set(e);
}
bs.PrintOnceNum();
}
void TestFindIntersection()
{
int a1[] = { 5,30,1,99,10 };
int a2[] = { 8,10,11,9,30,10,30 };
}
//BloomFilter
#pragma once
#include<bitset>
#include<string>
#include<time.h>
struct BKDRHash
{
size_t operator()(const string& s)
{
//BKDR
size_t value = 0;
for (auto ch : s)
{
value *= 3;
value += ch;
}
return value;
}
};
struct APHash
{
size_t operator()(const string& s)
{
size_t hash = 0;
for (long i = 0; i < s.size(); i++)
{
if ((i & 1) == 0)
{
hash ^= ((hash << 7) ^ s[i] ^ (hash >> 3));
}
else
{
hash ^= (~((hash << 11) ^ s[i] ^ (hash >> 5)));
}
}
return hash;
}
};
struct DJBHash
{
size_t operator()(const string& s)
{
size_t hash = 5381;
for(auto ch : s)
{
hash += (hash << 5) + ch;
}
return hash;
}
};
template<size_t N,
size_t X = 8,
class K = string,
class HashFunc1 = BKDRHash,
class HashFunc2 = APHash,
class HashFunc3 = DJBHash>
class BloomFilter
{
public:
void Set(const K& key)
{
size_t len = X * N;
size_t index1 = HashFunc1()(key) % len;
size_t index2 = HashFunc2()(key) % len;
size_t index3 = HashFunc3()(key) % len;
cout << index1 << endl;
cout << index2 << endl;
cout << index3 << endl << endl;
_bs.set(index1);
_bs.set(index2);
_bs.set(index3);
}
bool Test(const K& key)
{
size_t len = X * N;
size_t index1 = HashFunc1()(key) % len;
if (_bs.test(index1) == false)
return false;
size_t index2 = HashFunc2()(key) % len;
if (_bs.test(index2) == false)
return false;
size_t index3 = HashFunc3()(key) % len;
if (_bs.test(index3) == false)
return false;
return true; //存在誤判的
}
//不支援删除，删除可能會影響其它值。
void Reset(const K& key);
private:
bitset<X* N> _bs;
};
void TestBloomFilter1()
{
BloomFilter<100> bm;
bm.Set("sort");
bm.Set("left");
bm.Set("right");
bm.Set("eat");
bm.Set("ate");
bm.Set("https://www.cnblogs.com/-clq/archive/2012/05/31/2528153.html");
}
void TestBloomFilter2()
{
BloomFilter<100> bf;
bf.Set("張三");
bf.Set("李四");
bf.Set("牛魔王");
bf.Set("紅孩兒");
bf.Set("eat");
cout << bf.Test("張三") << endl;
cout << bf.Test("李四") << endl;
cout << bf.Test("牛魔王") << endl;
cout << bf.Test("紅孩兒") << endl;
cout << bf.Test("孫悟空") << endl;
cout << bf.Test("二郎神") << endl;
cout << bf.Test("豬八戒") << endl;
cout << bf.Test("ate") << endl;
//BloomFilter<100> bf;
srand(time(0));
size_t N = 100;
std::vector<std::string> v1;
for (size_t i = 0; i < N; ++i)
{
std::string ur1 = "https://www.cnblogs.com/-clq/archive/2012/05/31/2528153.html";
ur1 += std::to_string(1234 + i);
v1.push_back(ur1);
}
for (auto& str : v1)
{
bf.Set(str);
}
for (auto& str : v1)
{
cout << bf.Test(str) << endl;
}
cout << endl << endl;
std::vector<std::string> v2;
for (size_t i = 0; i < N; ++i)
{
std::string ur1 = "https://www.cnblogs.com/-clq/archive/2012/05/31/2528153.html";
ur1 += std::to_string(6789 + i);
v2.push_back(ur1);
}
size_t n2 = 0;
for (auto& str : v2)
{
if (bf.Test(str))
{
++n2;
}
}
cout << "相似字元串誤判率:" << (double)n2 / (double)N << endl;
std::vector<std::string> v3;
for (size_t i = 0; i < N; ++i)
{
string ur1 = "zhihu.com";
//std::string ur1 = "https://mail.qq.com/cgi-bin/frame_html?sid=0QvJ6bvfhn3EC1Iw&r=5976c09322eae24513a5ff315428cd86&;
//std::string ur1 = "https://www.sogou.com/tx?query=%E5%88%98%E5%BC%BA%E4%B8%9C%E4%BA%8B%E4%BB%B6%20%E5%A5%B3%E6%96%B9%E7%A7%B0%E8%87%AA%E6%84%BF%E5%8F%91%E7%94%9F%E5%85%B3%E7%B3%BB&hdq=sogou-site-706608cfdbcc1886&ekv=3&ie=utf8&";
//std::string ur1 = "https://www.sogou.com/sogou?ie=utf8&pid=sogou-wsse-af64b05ee108fa0c&query=%E4%BA%BA%E6%B0%91%E7%BD%91%3A%E5%BE%B7%E4%BA%91%E7%A4%BE%E8%AF%A5%E8%87%AA%E6%88%91%E6%A3%80%E8%A7%86%E4%BA%86";
ur1 += std::to_string(rand());
v3.push_back(ur1);
}
size_t n3 = 0;
for (auto& str : v3)
{
if (bf.Test(str))
{
++n3;
}
}
cout << "不相似字元串誤判率:" << (double)n3 / (double)N << endl;
}
設定為1
首先先用三個哈希函數算出對應的下标
再複用前面的位圖的函數将其bit位設為1即可
注意:當len越大時，即空間開的越大時，誤判率會越低
檢查在不在
三個bit位，隻要有一個bit位為0，則表示不在
注意:布隆過濾器不支援删除，因為支援删除會消耗很多空間，而且會存在誤删，比如上圖中的ate和eat，如果删除ate，那就會改變eat中的其中一個bit位
哈希切割
例:給兩個檔案，分别有100億個query，我們隻有1G記憶體，如何找到兩個檔案交集？分别給出精确算法和近似算法,這裡就要用到哈希切割
注意:如果Ai和Bi都太大，可以考慮換個哈希函數，再切割一次
全部代碼