目录
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&lang=zh";
//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都太大，可以考虑换个哈希函数，再切割一次?
全部代码