目录
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都太大，可以考虑换个哈希函数，再切割一次
全部代码
转载：https://blog.csdn.net/weixin_58867976/article/details/125464703
查看评论