文章目录
- 1. unorder无序
- 1.1unordered_map
- 文档介绍
- 接口说明
- 1.2 unordered_set
- 2.哈希
- 常见的哈希函数
- 2.1 直接定址法--(常用)
- 2.2 除留余数法--(常用)
- (1).闭散列——开方定址发（已被淘汰）
- a.线性探测——冲突越多效率越低。
- b.二次探测
- (2).开散列——拉链法/哈希桶
- 2.3 平方取中法--(了解)
- 2.4 折叠法--(了解)
- 2.5 随机数法--(了解)
- 2.6 数学分析法--(了解)
- 3.封装
- UnorderedMap
- unoderedSet
- 4. 位图
- 4.1位图概念
- 4.2 位图的实现
- 4.3 位图的应用
- 4.4 位图特点：
- 5. 布隆过滤器
- 5.1 概念
- 5.2 布隆过滤器的查找
- 5.3 布隆过滤器删除
- 5.4 布隆过滤器优点
- 5.5 布隆过滤器缺陷
1. unorder无序
在C++98中，STL提供了底层为红黑树结构的一系列关联式容器，在查询时效率可达到log2Nlog_2Nlog2N，即最差情况下需要比较红黑树的高度次，当树中的节点非常多时，查询效率也不理想。最好的查询是，进行很少的比较次数就能够将元素找到，因此在C++11中，STL又提供了4个unordered系列的关联式容器，这四个容器与红黑树结构的关联式容器使用方式基本类似，只是其底层结构不同，本文中只对unordered_map和unordered_set进行介绍，unordered_multimap和unordered_multise可查看文档介绍
1.1unordered_map
文档介绍
- unordered_map是存储<key, value>键值对的关联式容器，其允许通过keys快速的索引到与其对应的value。
- 在unordered_map中，键值通常用于惟一地标识元素，而映射值是一个对象，其内容与此键关联。键和映射值的类型可能不同。
- 在内部,unordered_map没有对<kye, value>按照任何特定的顺序排序, 为了能在常数范围内找到key所对应的value，unordered_map将相同哈希值的键值对放在相同的桶中。
- unordered_map容器通过key访问单个元素要比map快，但它通常在遍历元素子集的范围迭代方面效率较低。
- unordered_maps实现了直接访问操作符(operator[])，它允许使用key作为参数直接访问value。
- 它的迭代器至少是前向迭代器。
接口说明
1.构造
| 函数声明 | 功能介绍 |
|---|---|
| unordered_map | 构造不同格式的unordered_map对象 |
2.容量
| 函数声明 | 功能介绍 |
|---|---|
| bool empty() const | 检测unordered_map是否为空 |
| size_t size() const | 获取unordered_map的有效元素个数 |
3.迭代器
| 函数声明 | 功能介绍 |
|---|---|
| begin | 返回unordered_map第一个元素的迭代器 |
| end | 返回unordered_map最后一个元素下一个位置的迭代器 |
| cbegin | 返回unordered_map第一个元素的const迭代器 |
| cend | 返回unordered_map最后一个元素下一个位置的const迭代器 |
4.元素访问
| 函数声明 | 功能介绍 |
|---|---|
| operator[] | 返回与key对应的value，没有一个默认值 |
注意：该函数中实际调用哈希桶的插入操作，用参数key与V()构造一个默认值往底层哈希桶中插入，如果key不在哈希桶中，插入成功，返回V()，插入失败，说明key已经在哈希桶中，将key对应的value返回
5.查询
| 函数声明 | 功能介绍 |
|---|---|
| iterator find(const K& key) | 返回key在哈希桶中的位置 |
| size_t count(const K& key) | 返回哈希桶中关键码为key的键值对的个数 |
6.修改操作
| 函数声明 | 功能介绍 |
|---|---|
| insert | 向容器中插入键值对 |
| erase | 删除容器中的键值对 |
| void clear() | 清空容器中有效元素个数 |
| void swap(unordered_map&) | 交换两个容器中的元素 |
7.桶操作
| 函数声明 | 功能介绍 |
|---|---|
| size_t bucket_count()const | 返回哈希桶中桶的总个数 |
| size_t bucket_size(size_t n)const | 返回n号桶中有效元素的总个数 |
| size_t bucket(const K& key) | 返回元素key所在的桶号 |
1.2 unordered_set
与map类似，可自行查看文档说明。
与map和set的区别：
map和set遍历是有序的，unordered系列是无序的
map和set是双向迭代器，unordered系列是单向的
基于上面比较，相比map、set更强大，为什么还要有unordered系列？
当有大量数据时，增删查改效率unordered系列更优，尤其是查！
2.哈希
哈希/散列——值与存储位置建立映射关联关系
概念：
顺序结构以及平衡树中，元素关键码与其存储位置之间没有对应的关系，因此在查找一个元素时，必须要经过关键码的多次比较。顺序查找时间复杂度为O(N)，平衡树中为树的高度，即O(log2Nlog_2 Nlog2N)，搜索的效率取决于搜索过程中元素的比较次数。
理想的搜索方法：可以不经过任何比较，一次直接从表中得到要搜索的元素。
如果构造一种存储结构，通过某种函数(hashFunc)使元素的存储位置与它的关键码之间能够建立一一映射的关系，那么在查找时通过该函数可以很快找到该元素。
当向该结构中：
- 插入元素
根据待插入元素的关键码，以此函数计算出该元素的存储位置并按此位置进行存放。 - 搜索元素
对元素的关键码进行同样的计算，把求得的函数值当做元素的存储位置，在结构中按此位置
取元素比较，若关键码相等，则搜索成功。
该方式即为哈希(散列)方法，哈希方法中使用的转换函数称为哈希(散列)函数，构造出来的结构称为哈希表(Hash Table)(或者称散列表)
例如：数据集合{1，7，6，4，5，9}；
哈希函数设置为：hash(key) = key % capacity; capacity为存储元素底层空间总的大小
常见的哈希函数
2.1 直接定址法–(常用)
计数排序，字符串值出现一次
不存在哈希冲突——计数排序，字符串只出现一次
取关键字的某个线性函数为散列地址：Hash（Key）= A*Key + B
优点：简单、均匀
缺点：需要事先知道关键字的分布情况
使用场景：适合查找比较小且连续的情况
面试题：字符串中第一个只出现一次字符（特例，全是小写字母，每一个都可以确定唯一位置）
2.2 除留余数法–(常用)
设散列表中允许的地址数为m，取一个不大于m，但最接近或者等于m的质数p作为除数，
按照哈希函数：Hash(key) = key% p(p<=m),将关键码转换成哈希地址
但是如果存在不同的值映射相同的位置就会出现，哈希冲突（哈希碰撞)
解决办法：
(1).闭散列——开方定址发（已被淘汰）
a.线性探测——冲突越多效率越低。
查找时，如果先删除3，再去找二十，由于之前设定了找到空就停止，所以会找不到20
解决方法：引入标志位
扩容：
负载因子（载荷因子）：a = 填入表中元素个数/散列表的长度（最大为1）
越大，冲突概率越大
越小，冲突概率越小
什么时候扩容？负载因子到一个基准值就扩容
基准值越大，冲突越多，效率越低，空间利用率越高
基准值越小，冲突越少，效率越高，空间利用率越低
代码中基准值为0.7
这里的扩容是开一个新表，但是不能直接将数据拷贝过来。
因为存在映射关系，表变大了，映射关系也会发生改变。
旧表冲突的数据在新表不冲突；旧表不冲突的数据在新表冲突
#pragma once
//标志位enum State
{
EMPTY,
EXIST,
DELETE
};template<class K, class V>
struct HashData
{
pair<K, V> _kv;
State _state = EMPTY;
};template<class K, class V>
class HashTable
{
public:
bool Insert(const pair<K, V>& kv)
{if (Find(kv.first))
return false;// 负载因子到了就扩容//整数与整数相除得整数，替换一下即可
if (_tables.size() == 0 || 10 * _size / _tables.size() >= 7) // 扩容
{
//size_t newSize = _table.size() == 0 ? 10 : _table.size() * 2;
//vector<HashData<K, V>> newTables;
//newTables.resize(newSize);
旧表的数据映射到新表
//for ()
//{//还得再写好多，此方法过于复杂//}//_table.swap(newTables);size_t newSize = _tables.size() == 0 ? 10 : _tables.size() * 2;
HashTable<K, V> newHT;//创建了一个自己类型的对象
newHT._tables.resize(newSize);
// 旧表的数据映射到新表——这里只需要复用之前所写的insert代码即可
for (auto e : _tables)
{
if (e._state == EXIST)
{
newHT.Insert(e._kv);
}
}_tables.swap(newHT._tables);//交换——释放旧表
}size_t hashi = kv.first % _tables.size();
// 线性探测
while (_tables[hashi]._state == EXIST)
{
hashi++;
hashi %= _tables.size();//防止出界
}_tables[hashi]._kv = kv;
_tables[hashi]._state = EXIST;
++_size;return true;
}HashData<K, V>* Find(const K& key)
{
if (_tables.size() == 0)
{
return nullptr;
}Hash hash;
size_t start = hash(key) % _tables.size();
size_t hashi = start;
while (_tables[hashi]._state != EMPTY)
{
if (_tables[hashi]._state != DELETE && _tables[hashi]._kv.first == key)
{
return &_tables[hashi];
}hashi++;
hashi %= _tables.size();//极端判断if (hashi == start)
{
break;
}
}return nullptr;
}bool Erase(const K& key)
{
HashData<K, V>* ret = Find(key);
if (ret)
{
ret->_state = DELETE;
--_size;
return true;
}
else
{
return false;
}
}void Print()
{
for (size_t i = 0; i < _tables.size(); ++i)
{
if (_tables[i]._state == EXIST)
{
printf("[%d:%d] ", i, _tables[i]._kv.first);
}
else
{
printf("[%d:*] ", i);
}
}
cout << endl;
}private:
//vector<pair<K, V>> _table;
vector<HashData<K, V>> _tables;
size_t _size = 0; // 存储多少个有效数据
};
三种测试场景——更加完善哈希表
1
void TestHT1()
{
//int a[] = { 1, 11, 4, 15, 26, 7, 44, 9 };
int a[] = { 1, 11, 4, 15, 26, 7, 44 };
HashTable<int, int> ht;
for (auto e : a)
{
ht.Insert(make_pair(e, e));
}ht.Print();ht.Erase(4);
cout << ht.Find(44)->_kv.first << endl;
cout << ht.Find(4) << endl;
ht.Print();ht.Insert(make_pair(-2, -2));//取模时会被提升成无符号的
ht.Print();cout << ht.Find(-2)->_kv.first << endl;
}
2.另一种场景：string不能取模
//string不能取模
//unodered_map hash<Key>
void TestHT2()
{
string arr[] = { "苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜", "苹果", "香蕉", "苹果", "香蕉" };//HashTable<string, int, HashFuncString> countHT;
HashTable<string, int> countHT;//统计次数
for (auto& str : arr)
{
auto ptr = countHT.Find(str);
if (ptr)
{
ptr->_kv.second++;
}
else
{
countHT.Insert(make_pair(str, 1));
}
}
}
用仿函数支持string取模：
//将string转成整型
//1.仿函数
template<class K>
struct HashFunc
{
size_t operator()(const K& key)
{
return (size_t)key;
}
};//2.
struct HashFuncString
{
size_t operator()(const string& key)
{
size_t val = 0;
for (auto ch : key)
{
val += ch;
}return val;
}
};// 特化
template<>
struct HashFunc<string>
{size_t operator()(const string& key)
{
size_t val = 0;
for (auto ch : key)
{val += ch;
}return val;
}
};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 * _size / _tables.size() >= 7) // 扩容
{
size_t newSize = _tables.size() == 0 ? 10 : _tables.size() * 2;
HashTable<K, V, Hash> newHT;
newHT._tables.resize(newSize);
// 旧表的数据映射到新表
for (auto e : _tables)
{
if (e._state == EXIST)
{
newHT.Insert(e._kv);
}
}_tables.swap(newHT._tables);
}Hash hash;
size_t hashi = hash(kv.first) % _tables.size();
// 线性探测
while (_tables[hashi]._state == EXIST)
{
hashi++;
hashi %= _tables.size();
}_tables[hashi]._kv = kv;
_tables[hashi]._state = EXIST;
++_size;return true;
}HashData<K, V>* Find(const K& key)
{
if (_tables.size() == 0)
{
return nullptr;
}Hash hash;
size_t start = hash(key) % _tables.size();
size_t hashi = start;
while (_tables[hashi]._state != EMPTY)
{
if (_tables[hashi]._state != DELETE && _tables[hashi]._kv.first == key)
{
return &_tables[hashi];
}hashi++;
hashi %= _tables.size();if (hashi == start)
{
break;
}
}return nullptr;
}bool Erase(const K& key)
{
HashData<K, V>* ret = Find(key);
if (ret)
{
ret->_state = DELETE;
--_size;
return true;
}
else
{
return false;
}
}void Print()
{
for (size_t i = 0; i < _tables.size(); ++i)
{
if (_tables[i]._state == EXIST)
{
printf("[%d:%d] ", i, _tables[i]._kv.first);
}
else
{
printf("[%d:*] ", i);
}
}
cout << endl;
}private:vector<HashData<K, V>> _tables;
size_t _size = 0; // 存储多少个有效数据
};
unordered_map不用转
void TestHT3()
{
HashFunc<string> hash;
cout << hash("abcd") << endl;
cout << hash("bcad") << endl;
cout << hash("eat") << endl;
cout << hash("ate") << endl;
cout << hash("abcd") << endl;
cout << hash("aadd") << endl << endl;cout << hash("abcd") << endl;
cout << hash("bcad") << endl;
cout << hash("eat") << endl;
cout << hash("ate") << endl;
cout << hash("abcd") << endl;
cout << hash("aadd") << endl << endl;
}
}
会出现，不一样的字符串但ASCII加起来的结果相等
解决方法：每次加的值都*131
template<>
struct HashFunc<string>
{
// BKDR
size_t operator()(const string& key)
{
size_t val = 0;
for (auto ch : key)
{
val *= 131;
val += ch;
}return val;
}
};
线性探测的缺点：
在某个位置冲突很多的情况下，互相占用，冲突一片。
hash+i(i>=0)
b.二次探测
hash + i^2(i>=0)，也不是彻底解决
Hash hash;
size_t start = hash(kv.first) % _tables.size();
size_t i = 0;
size_t hashi = start;
// 二次探测
while (_tables[hashi]._state == EXIST)
{
++i;
hashi = start + i*i;
hashi %= _tables.size();
}_tables[hashi]._kv = kv;
_tables[hashi]._state = EXIST;
++_size;
(2).开散列——拉链法/哈希桶
不会互相影响冲突的位置
搜索：O(N)
表里存的是指针数组
挂结点：使用单链表较好，节省空间，搜索效率高
不用排成有序，没有太大价值
扩容：
在元素个数刚好等于桶的个数时，可以给哈希表增容
负载因子到1就扩容
自定义类型，不用去写构造函数，会默认初始化
扩容优化：尽量让哈希表的大小是一个素数
哈希表的弱势：插入慢
namespace Bucket
{
template<class T>
struct HashNode
{
T _data;
HashNode<T>* _next;HashNode(const T& data)
:_data(data)
, _next(nullptr)
{}
};// 前置声明
template<class K, class T, class Hash, class KeyOfT>
class HashTable;template<class K, class T, class Hash, class KeyOfT>
struct __HashIterator
{
typedef HashNode<T> Node;
typedef HashTable<K, T, Hash, KeyOfT> HT;
typedef __HashIterator<K, T, Hash, KeyOfT> Self;Node* _node;
HT* _pht;__HashIterator(Node* node, HT* pht)
:_node(node)
, _pht(pht)
{}T& operator*()
{
return _node->_data;
}T* operator->()
{
return &_node->_data;
}Self& operator++()
{
if (_node->_next)
{
// 当前桶中迭代
_node = _node->_next;
}
else
{
// 找下一个桶
Hash hash;
KeyOfT kot;
size_t i = hash(kot(_node->_data)) % _pht->_tables.size();
++i;
for (; i < _pht->_tables.size(); ++i)
{
if (_pht->_tables[i])
{
_node = _pht->_tables[i];
break;
}
}// 说明后面没有有数据的桶了
if (i == _pht->_tables.size())
{
_node = nullptr;
}
}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 Hash, class KeyOfT>
class HashTable
{
typedef HashNode<T> Node;template<class K, class T, class Hash, class KeyOfT>
friend struct __HashIterator;
public:
typedef __HashIterator<K, T, Hash, KeyOfT> iterator;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);
}~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;
}
}//素数表inline size_t __stl_next_prime(size_t n)
{
static const size_t __stl_num_primes = 28;
static const size_t __stl_prime_list[__stl_num_primes] =
{
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 < __stl_num_primes; ++i)
{
if (__stl_prime_list[i] > n)
{
return __stl_prime_list[i];
}
}return -1;
}pair<iterator, bool> Insert(const T& data)
{
Hash hash;
KeyOfT kot;// 去重
iterator ret = Find(kot(data));
if (ret != end())
{
return make_pair(ret, false);
}// 负载因子到1就扩容
if (_size == _tables.size())
{
//size_t newSize = _tables.size() == 0 ? 10 : _tables.size() * 2;
vector<Node*> newTables;
//newTables.resize(newSize, nullptr);
newTables.resize(__stl_next_prime(_tables.size()), nullptr);
// 旧表中节点移动映射新表
for (size_t i = 0; i < _tables.size(); ++i)
{
Node* cur = _tables[i];
while (cur)
{
Node* next = cur->_next;size_t hashi = hash(kot(cur->_data)) % newTables.size();
cur->_next = newTables[hashi];
newTables[hashi] = cur;cur = next;
}_tables[i] = nullptr;
}_tables.swap(newTables);
}size_t hashi = hash(kot(data)) % _tables.size();
// 头插
//1.改指向2.自己变成新节点
Node* newnode = new Node(data);
newnode->_next = _tables[hashi];
_tables[hashi] = newnode;
++_size;return make_pair(iterator(newnode, this), true);
}iterator Find(const K& key)
{
if (_tables.size() == 0)
{
return end();
}Hash hash;
KeyOfT kot;
size_t hashi = hash(key) % _tables.size();
Node* cur = _tables[hashi];
while (cur)
{
if (kot(cur->_data) == key)
{
return iterator(cur, this);
}cur = cur->_next;
}return end();
}bool Erase(const K& key)
{
if (_tables.size() == 0)
{
return false;
}Hash hash;
KeyOfT kot;
size_t hashi = hash(key) % _tables.size();
Node* prev = nullptr;
Node* cur = _tables[hashi];
while (cur)
{
if (kot(cur->_data) == key)
{
// 1、头删
if (prev == nullptr)
{
_tables[hashi] = cur->_next;
}
// 2、中间删
else
{
prev->_next = cur->_next;
}delete cur;
--_size;return true;
}prev = cur;
cur = cur->_next;
}return false;
}size_t Size()
{
return _size;
}// 表的长度
size_t TablesSize()
{
return _tables.size();
}// 桶的个数
size_t BucketNum()
{
size_t num = 0;
for (size_t i = 0; i < _tables.size(); ++i)
{
if (_tables[i])
{
++num;
}
}return num;
}size_t MaxBucketLenth()
{
size_t maxLen = 0;
for (size_t i = 0; i < _tables.size(); ++i)
{
size_t len = 0;
Node* cur = _tables[i];
while (cur)
{
++len;
cur = cur->_next;
}//if (len > 0)
//printf("[%d]号桶长度:%d\n", i, len);if (len > maxLen)
{
maxLen = len;
}
}return maxLen;
}private:
vector<Node*> _tables;
size_t _size = 0; // 存储有效数据个数
};}
2.3 平方取中法–(了解)
假设关键字为1234，对它平方就是1522756，抽取中间的3位227作为哈希地址；
再比如关键字为4321，对它平方就是18671041，抽取中间的3位671(或710)作为哈希地址平方取中法比较适合：不知道关键字的分布，而位数又不是很大的情况
2.4 折叠法–(了解)
折叠法是将关键字从左到右分割成位数相等的几部分(最后一部分位数可以短些)，然后将这几部分叠加求和，并按散列表表长，取后几位作为散列地址。
折叠法适合事先不需要知道关键字的分布，适合关键字位数比较多的情况
2.5 随机数法–(了解)
选择一个随机函数，取关键字的随机函数值为它的哈希地址，即H(key) = random(key),其中random为随机数函数。
通常应用于关键字长度不等时采用此法
2.6 数学分析法–(了解)
设有n个d位数，每一位可能有r种不同的符号，这r种不同的符号在各位上出现的频率不一定相同，可能在某些位上分布比较均匀，每种符号出现的机会均等，在某些位上分布不均匀只有某几种符号经常出现。可根据散列表的大小，选择其中各种符号分布均匀的若干位作为散列地址。
3.封装
UnorderedMap
#pragma once#include "HashTable.h"namespace bit
{
template<class K, class V, class Hash = HashFunc<K>>
class unordered_map
{
struct MapKeyOfT
{
const K& operator()(const pair<K, V>& kv)
{
return kv.first;
}
};
public:
typedef typename Bucket::HashTable<K, pair<K, V>, Hash, MapKeyOfT>::iterator iterator;iterator begin()
{
return _ht.begin();
}iterator end()
{
return _ht.end();
}pair<iterator, bool> Insert(const pair<K, V>& kv)
{
return _ht.Insert(kv);
}V& operator[](const K& key)
{
pair<iterator, bool> ret = _ht.Insert(make_pair(key, V()));
return ret.first->second;
}private:
Bucket::HashTable<K, pair<K, V>, Hash, MapKeyOfT> _ht;
};void test_map()
{
unordered_map<string, string> dict;
dict.Insert(make_pair("sort", ""));
dict.Insert(make_pair("string", "ַ"));
dict.Insert(make_pair("left", ""));unordered_map<string, string>::iterator it = dict.begin();
while (it != dict.end())
{
cout << it->first << ":" << it->second << endl;
++it;
}
cout << endl;unordered_map<string, int> countMap;
string arr[] = { "ƻ", "", "ƻ", "", "ƻ", "ƻ", "", "ƻ", "㽶", "ƻ", "㽶" };
for (auto e : arr)
{
countMap[e]++;
}for (auto& kv : countMap)
{
cout << kv.first << ":" << kv.second << endl;
}
}
}
unoderedSet
#pragma once#include "HashTable.h"namespace bit
{
template<class K, class Hash = HashFunc<K>>
class unordered_set
{
struct SetKeyOfT
{
const K& operator()(const K& key)
{
return key;
}
};
public:
typedef typename Bucket::HashTable<K, K, Hash, SetKeyOfT>::iterator iterator;iterator begin()
{
return _ht.begin();
}iterator end()
{
return _ht.end();
}pair<iterator, bool> insert(const K& key)
{
return _ht.Insert(key);
}
private:
Bucket::HashTable<K, K, Hash, SetKeyOfT> _ht;
};void test_set()
{
unordered_set<int> s;
s.insert(2);
s.insert(3);
s.insert(1);
s.insert(2);
s.insert(5);unordered_set<int>::iterator it = s.begin();
//auto it = s.begin();
while (it != s.end())
{
cout << *it << " ";
++it;
}
cout << endl;
}
}
4. 位图
4.1位图概念
所谓位图，就是用每一位来存放某种状态，适用于海量数据，数据无重复的场景。通常是用来判断某个数据存不存在的
4.2 位图的实现
左移右移不是方向，是高位和低位
或等|= 111 101 000 011 只有0与0才是0，有1就是1
与等&= 111 100 只要有0就是0，两个都是1才是1
按位取反~
#pragma oncenamespace haha
{
template<size_t N>
class bitset
{
public://用非类型模板参数控制开空间的问题
bitset()
{
_bits.resize(N / 8 + 1, 0);//+1，是对8不能整除时防止越界
}//3个核心接口//把对应位置1
void set(size_t x)
{
size_t i = x / 8;//在第几个char
size_t j = x % 8;//在这个char的第几个比特位_bits[i] |= (1 << j);//把对应的第j位标志成1
}//把对应位置0
void reset(size_t x)
{
size_t i = x / 8;
size_t j = x % 8;_bits[i] &= ~(1 << j);
}//观察值是否在不在——需要一个bool值
bool test(size_t x)
{
size_t i = x / 8;
size_t j = x % 8;return _bits[i] & (1 << j);//两个都是1才是1
}private:
vector<char> _bits;
};void test_haha_set1()
{
bitset<100> bs1;
bs1.set(8);
bs1.set(9);
bs1.set(20);cout << bs1.test(8) << endl;
cout << bs1.test(9) << endl;
cout << bs1.test(20) << endl;bs1.reset(8);
bs1.reset(9);
bs1.reset(20);cout << bs1.test(8) << endl;
cout << bs1.test(9) << endl;
cout << bs1.test(20) << endl;
}void test_haha_set2()
{
bitset<-1> bs1;
//bitset<0xffffffff> bs2;
}
4.3 位图的应用
- 快速查找某个数据是否在一个集合中
- 排序 + 去重
- 求两个集合的交集、并集等
- 操作系统中磁盘块标记
4.4 位图特点：
优点：快、节省空间，不存在冲突
缺点：只能处理整数，相对局限
5. 布隆过滤器
5.1 概念
字符串用哈希算法转成整型再去映射一个位置进行标记
有可能会造成冲突
存在误判：
在：不准确
不在：准确的
不可能完全避免误判，但是可以降低误判率：每个值多映射几个位
理论：一个值映射的越多，误判率越低。但不敢映射太多，消耗空间太多。
快速过滤
开多少个比特位合适：
k 为哈希函数个数，m 为布隆过滤器长度，n 为插入的元素个数，p 为误报率
如何选择适合业务的 k 和 m 值呢，这里直接贴一个公式：
#pragma oncestruct HashBKDR
{
// BKDR
size_t operator()(const string& key)
{
size_t val = 0;
for (auto ch : key)
{
val *= 131;
val += ch;
}return val;
}
};struct HashAP
{
// BKDR
size_t operator()(const string& key)
{
size_t hash = 0;
for (size_t i = 0; i < key.size(); i++)
{
if ((i & 1) == 0)
{
hash ^= ((hash << 7) ^ key[i] ^ (hash >> 3));
}
else
{
hash ^= (~((hash << 11) ^ key[i] ^ (hash >> 5)));
}
}
return hash;
}
};struct HashDJB
{
// BKDR
size_t operator()(const string& key)
{
size_t hash = 5381;
for (auto ch : key)
{
hash += (hash << 5) + ch;
}return hash;
}
};// N表示准备要映射N个值
template<size_t N,
class K = string, class Hash1 = HashBKDR, class Hash2 = HashAP, class Hash3 = HashDJB>
class BloomFilter
{
public:
void Set(const K& key)
{
size_t hash1 = Hash1()(key) % (_ratio*N);
//cout << hash1 << endl;_bits->set(hash1);size_t hash2 = Hash2()(key) % (_ratio*N);
//cout << hash2 << endl;_bits->set(hash2);size_t hash3 = Hash3()(key) % (_ratio*N);
//cout << hash3 << endl;_bits->set(hash3);
}bool Test(const K& key)
{
size_t hash1 = Hash1()(key) % (_ratio*N);
//cout << hash1 << endl;
if (!_bits->test(hash1))
return false; // 准确的size_t hash2 = Hash2()(key) % (_ratio*N);
//cout << hash2 << endl;if (!_bits->test(hash2))
return false; // 准确的size_t hash3 = Hash3()(key) % (_ratio*N);
//cout << hash3 << endl;if (!_bits->test(hash3))
return false; // 准确的return true; // 可能存在误判
}// 能否支持删除->
void Reset(const K& key);private:
const static size_t _ratio = 5;
std::bitset<_ratio*N>* _bits = new std::bitset<_ratio*N>;
};void TestBloomFilter1()
{
BloomFilter<10> bf;
string arr1[] = { "苹果", "西瓜", "阿里", "美团", "苹果", "字节", "西瓜", "苹果", "香蕉", "苹果", "腾讯" };for (auto& str : arr1)
{
bf.Set(str);
}for (auto& str : arr1)
{
cout << bf.Test(str) << endl;
}
cout << endl << endl;string arr2[] = { "苹果111", "西瓜", "阿里2222", "美团", "苹果dadcaddxadx", "字节", "西瓜sSSSX", "苹果 ", "香蕉", "苹果$", "腾讯" };for (auto& str : arr2)
{
cout <<str<<":"<<bf.Test(str) << endl;
}
}void TestBloomFilter2()
{
srand(time(0));
const size_t N = 100000;
BloomFilter<N> bf;
cout << sizeof(bf) << endl;std::vector<std::string> v1;
std::string url = "https://www.cnblogs.com/-clq/archive/2012/05/31/2528153.html";for (size_t i = 0; i < N; ++i)
{
v1.push_back(url + std::to_string(1234 + i));
}for (auto& str : v1)
{
bf.Set(str);
}// 相似
std::vector<std::string> v2;
for (size_t i = 0; i < N; ++i)
{
std::string url = "http://www.cnblogs.com/-clq/archive/2021/05/31/2528153.html";
url += std::to_string(rand() + i);
v2.push_back(url);
}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 url = "zhihu.com";
url += std::to_string(rand()+i);
v3.push_back(url);
}size_t n3 = 0;
for (auto& str : v3)
{
if (bf.Test(str))
{
++n3;
}
}
cout << "不相似字符串误判率:" << (double)n3 / (double)N << endl;
}
5.2 布隆过滤器的查找
布隆过滤器的思想是将一个元素用多个哈希函数映射到一个位图中，因此被映射到的位置的比特位一定为1。所以可以按照以下方式进行查找：分别计算每个哈希值对应的比特位置存储的是否为零，只要有一个为零，代表该元素一定不在哈希表中，否则可能在哈希表中。
注意：布隆过滤器如果说某个元素不存在时，该元素一定不存在，如果该元素存在时，该元素可能存在，因为有些哈希函数存在一定的误判。
比如：在布隆过滤器中查找"alibaba"时，假设3个哈希函数计算的哈希值为：1、3、7，刚好和其他元素的比特位重叠，此时布隆过滤器告诉该元素存在，但实该元素是不存在的。
5.3 布隆过滤器删除
布隆过滤器不能直接支持删除工作，因为在删除一个元素时，可能会影响其他元素。比如：删除上图中"tencent"元素，如果直接将该元素所对应的二进制比特位置0，“baidu”元素也被删除了，因为这两个元素在多个哈希函数计算出的比特位上刚好有重叠。
一种支持删除的方法：将布隆过滤器中的每个比特位扩展成一个小的计数器，插入元素时给k个计数器(k个哈希函数计算出的哈希地址)加一，删除元素时，给k个计数器减一，通过多占用几倍存储空间的代价来增加删除操作。
缺陷：
- 无法确认元素是否真正在布隆过滤器中
- 存在计数回绕
5.4 布隆过滤器优点
- 增加和查询元素的时间复杂度为:O(K), (K为哈希函数的个数，一般比较小)，与数据量大小无关
- 哈希函数相互之间没有关系，方便硬件并行运算
- 布隆过滤器不需要存储元素本身，在某些对保密要求比较严格的场合有很大优势
- 在能够承受一定的误判时，布隆过滤器比其他数据结构有这很大的空间优势
- 数据量很大时，布隆过滤器可以表示全集，其他数据结构不能
- 使用同一组散列函数的布隆过滤器可以进行交、并、差运算
5.5 布隆过滤器缺陷
- 有误判率，即存在假阳性(False Position)，即不能准确判断元素是否在集合中(补救方法：再建立一个白名单，存储可能会误判的数据)
- 不能获取元素本身
- 一般情况下不能从布隆过滤器中删除元素
- 如果采用计数方式删除，可能会存在计数回绕问题
