devbox
从前慢现在也慢
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

＜位图（bitset）和布隆过滤器(BloomFilter)＞——《C++高阶》_bitset和布隆过滤器

作者：从前慢现在也慢 | 2024-04-16 22:56:05

赞

踩

bitset和布隆过滤器

目录

1. 哈希的应用

1.1 位图

1.1.1 位图概念

1.1.2 位图的实现

1.1.3 位图的应用

1.2 布隆过滤器

1.2.1 布隆过滤器提出

1.2.2布隆过滤器概念

 1.2.3 布隆过滤器的插入

1.2.4 布隆过滤器的查找

1.2.5 布隆过滤器删除

1.2.6 布隆过滤器优点

1.2.7 布隆过滤器缺陷

2. 海量数据处理类题目解析

2.1 哈希切割

2.2 位图应用

2.3 布隆过滤器

3.位图与布隆过滤器完整源码：

3.1位图模拟实现源码：

3.2 布隆过滤器模拟实现源码:

3.3 附用的unordered_set、unordered_map、OpenHash:

3.4 test.cpp:​

后记：●由于作者水平有限，文章难免存在谬误之处，敬请读者斧正，俚语成篇，恳望指教！

                                                                           ——By 作者：新晓·故知

1. 哈希的应用

1.1 位图

1.1.1 位图概念

1. 面试题

给40亿个不重复的无符号整数，没排过序。给一个无符号整数，如何快速判断一个数是否在

这40亿个数中。【腾讯】

分析：不能使用set/unordered_set，因为内存不够。也不能使用外排序+二分查找，因为不能很好的支持快速随机访问！

1. 遍历，时间复杂度O(N)

2. 排序(O(NlogN))，利用二分查找: logN

3. 位图解决

数据是否在给定的整形数据中，结果是在或者不在，刚好是两种状态，那么可以使用一

个二进制比特位来代表数据是否存在的信息，如果二进制比特位为1，代表存在，为0

代表不存在。比如：

直接定址法哈希——用一个比特位标识映射值在不在！

2. 位图概念

所谓位图，就是用每一位来存放某种状态，适用于海量数据，数据无重复的场景。通常是用

来判断某个数据存不存在的。

1.1.2 位图的实现

  1. class bitset
  2. {
  3. public:
  4.  bitset(size_t bitCount)
  5.  : _bit((bitCount>>5)+1), _bitCount(bitCount)
  6.  {}
  7.  // 将which比特位置1
  8.  void set(size_t which)
  9.  {
  10.  if(which > _bitCount)
  11.  return;
  12.  size_t index = (which >> 5);
  13.  size_t pos = which % 32;
  14. _bit[index] |= (1 << pos);
  15.  }
  16.  // 将which比特位置0
  17.  void reset(size_t which)
  18.  {
  19.  if(which > _bitCount)
  20.  return;
  21.  size_t index = (which >> 5);
  22.  size_t pos = which % 32;
  23.  _bit[index] &= ~(1<<pos);
  24.  }
  25.  // 检测位图中which是否为1
  26.  bool test(size_t which)
  27.  {
  28.  if(which > _bitCount)
  29.  return false;
  30.  size_t index = (which >> 5);
  31.  size_t pos = which % 32;
  32.  return _bit[index] & (1<<pos);
  33.  }
  34.  // 获取位图中比特位的总个数
  35.  size_t size()const{ return _bitCount;}
  36.  // 位图中比特为1的个数
  37.  size_t Count()const
  38.  {
  39.      int bitCnttable[256] = {
  40. 0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8};
  41.  
  42.  size_t size = _bit.size();
  43.  size_t count = 0;
  44.  for(size_t i = 0; i < size; ++i)
  45.  {
  46.  int value = _bit[i];
  47.  int j = 0;
  48.  while(j < sizeof(_bit[0]))
  49.  {
  50.  unsigned char c = value;
  51.  count += bitCntTable[c];
  52.  ++j;
  53.  value >>= 8;
  54.  }
  55.  }
  56.  return count;
  57.  }
  58. private:
  59.  vector<int> _bit;
  60. size_t _bitCount;
  61. };

1.1.3 位图的应用

1. 快速查找某个数据是否在一个集合中

2. 排序 + 去重

3. 求两个集合的交集、并集等

4. 操作系统中磁盘块标记

1.2 布隆过滤器

1.2.1 布隆过滤器提出

我们在使用新闻客户端看新闻时，它会给我们不停地推荐新的内容，它每次推荐时要去重，去掉那些已经看过的内容。问题来了，新闻客户端推荐系统如何实现推送去重的？ 用服务器记录了用户看过的所有历史记录，当推荐系统推荐新闻时会从每个用户的历史记录里进行筛选，过滤掉那些已经存在的记录。 如何快速查找呢？

1. 用哈希表存储用户记录，缺点：浪费空间

2. 用位图存储用户记录，缺点：位图一般只能处理整形，如果内容编号是字符串，就无法处理了。

3. 将哈希与位图结合，即布隆过滤器

1.2.2布隆过滤器概念

布隆过滤器是由布隆（Burton Howard Bloom）在1970年提出的 一种紧凑型的、比较巧妙的概率型数据结构，特点是高效地插入和查询，可以用来告诉你 “某样东西一定不存在或者可能存在”，它是用多个哈希函数，将一个数据映射到位图结构中。此种方式不仅可以提升查询效率，也可以节省大量的内存空间。

 1.2.3 布隆过滤器的插入

  1. struct BKDRHash
  2. {
  3.  size_t operator()(const string& s)
  4.  {
  5.  // BKDR
  6.  size_t value = 0;
  7.  for (auto ch : s)
  8.  {
  9.  value *= 31;
  10.  value += ch;
  11.  }
  12.  return value;
  13.  }
  14. };
  15. struct APHash
  16. {
  17.  size_t operator()(const string& s)
  18.  {
  19.  size_t hash = 0;
  20.  for (long i = 0; i < s.size(); i++)
  21.  {
  22.  if ((i & 1) == 0)
  23.  {
  24.  hash ^= ((hash << 7) ^ s[i] ^ (hash >> 3));
  25.  }
  26.  else
  27.  {
  28.  hash ^= (~((hash << 11) ^ s[i] ^ (hash >> 5)));
  29.  }
  30.  }
  31.  return hash;
  32.  }
  33. };
  34. struct DJBHash
  35. {
  36.  size_t operator()(const string& s)
  37.  {
  38.  size_t hash = 5381;
  39.  for (auto ch : s)
  40.  {
  41.  hash += (hash << 5) + ch;
  42.  }
  43.  return hash;
  44.  }
  45. };
  46. template<size_t N,
  47. size_t X = 5,
  48. class K = string,
  49. class HashFunc1 = BKDRHash,
  50. class HashFunc2 = APHash,
  51. class HashFunc3 = DJBHash>
  52. class BloomFilter
  53. {
  54. public:
  55.  void Set(const K& key)
  56.  {
  57.  size_t len = X*N;
  58.  size_t index1 = HashFunc1()(key) % len;
  59.  size_t index2 = HashFunc2()(key) % len;
  60.  size_t index3 = HashFunc3()(key) % len;
  61.  /* cout << index1 << endl;
  62.  cout << index2 << endl;
  63.  cout << index3 << endl<<endl;*/
  64.  _bs.set(index1);
  65.  _bs.set(index2);
  66.  _bs.set(index3);
  67.  }
  68.  bool Test(const K& key)
  69.  {
  70.  size_t len = X*N;
  71.  size_t index1 = HashFunc1()(key) % len;
  72.  if (_bs.test(index1) == false)
  73.  return false;
  74.  size_t index2 = HashFunc2()(key) % len;
  75.  if (_bs.test(index2) == false)
  76.  return false;
  77.  size_t index3 = HashFunc3()(key) % len;
  78.  if (_bs.test(index3) == false)
  79.  return false;
  80.  return true;  // 存在误判的
  81.  }
  82.  // 不支持删除，删除可能会影响其他值。
  83.  void Reset(const K& key);
  84. private:
  85.  bitset<X*N> _bs;
  86. };

1.2.4 布隆过滤器的查找

布隆过滤器的思想是将一个元素用多个哈希函数映射到一个位图中，因此被映射到的位置的比特

位一定为1。所以可以按照以下方式进行查找：分别计算每个哈希值对应的比特位置存储的是否为零，只要有一个为零，代表该元素一定不在哈希表中，否则可能在哈希表中。

注意：布隆过滤器如果说某个元素不存在时，该元素一定不存在，如果该元素存在时，该元素可能存在，因为有些哈希函数存在一定的误判。

比如：在布隆过滤器中查找"alibaba"时，假设3个哈希函数计算的哈希值为：1、3、7，刚好和其他元素的比特位重叠，此时布隆过滤器告诉该元素存在，但实该元素是不存在的。

1.2.5 布隆过滤器删除

布隆过滤器不能直接支持删除工作，因为在删除一个元素时，可能会影响其他元素。

比如：删除上图中"tencent"元素，如果直接将该元素所对应的二进制比特位置0，“baidu”元素也被删除了，因为这两个元素在多个哈希函数计算出的比特位上刚好有重叠。

一种支持删除的方法：将布隆过滤器中的每个比特位扩展成一个小的计数器，插入元素时给k个计数器(k个哈希函数计算出的哈希地址)加一，删除元素时，给k个计数器减一，通过多占用几倍存储空间的代价来增加删除操作。

缺陷：

1. 无法确认元素是否真正在布隆过滤器中

2. 存在计数回绕

1.2.6 布隆过滤器优点

1. 增加和查询元素的时间复杂度为:O(K), (K为哈希函数的个数，一般比较小)，与数据量大小无关

2. 哈希函数相互之间没有关系，方便硬件并行运算

3. 布隆过滤器不需要存储元素本身，在某些对保密要求比较严格的场合有很大优势

4. 在能够承受一定的误判时，布隆过滤器比其他数据结构有这很大的空间优势

5. 数据量很大时，布隆过滤器可以表示全集，其他数据结构不能

6. 使用同一组散列函数的布隆过滤器可以进行交、并、差运算

1.2.7 布隆过滤器缺陷

1. 有误判率，即存在假阳性(False Position)，即不能准确判断元素是否在集合中(补救方法：再建立一个白名单，存储可能会误判的数据)

2. 不能获取元素本身

3. 一般情况下不能从布隆过滤器中删除元素

4. 如果采用计数方式删除，可能会存在计数回绕问题

2. 海量数据处理类题目解析

2.1 哈希切割

给一个超过100G大小的log fifile, log中存着IP地址, 设计算法找到出现次数最多的IP地址？

与上题条件相同，如何找到top K的IP？如何直接用Linux系统命令实现？

2.2 位图应用

1. 给定100亿个整数，设计算法找到只出现一次的整数？

分析：使用两个比特位，标识3种状态。出现0次：00  出现1次：01  出现2次及以上：10

2. 给两个文件，分别有100亿个整数，我们只有1G内存，如何找到两个文件交集？

3. 位图应用变形：1个文件有100亿个int，1G内存，设计算法找到出现次数不超过2次的所有整数

注：放在位图找交集的意义是先去重。

 位图的优点：

1.节省空间

2.处理快速

缺点：只能针对整型映射

2.3 布隆过滤器

1. 给两个文件，分别有100亿个query，我们只有1G内存，如何找到两个文件交集？分别给出

精确算法和近似算法

2. 如何扩展BloomFilter使得它支持删除元素的操作

布隆过滤器映射的位数越多，冲突的概率越小

布隆过滤器的底层就是一个位图
布隆过滤器支持删除，但删除会影响其他位值，因此会付出很大的代价。删除的方式是计数。

 

3.位图与布隆过滤器完整源码：

因为涉及到附用unordered_set、unordered_map，所以这里给出完整的源码。

3.1位图模拟实现源码：

bitset:

位图1：

  1. #pragma once
  2. #include <vector>
  3. //位图1
  4. namespace my
  5. {
  6. 	// N个比特位的位图  10  16
  7. 	template<size_t N>
  8. 	class bitset
  9. 	{
  10. 	public:
  11. 		bitset()
  12. 		{
  13. 			// +1保证足够比特位，最多浪费8个
  14. 			_bits.resize(N / 8 + 1, 0);
  15. 		}
  16.  
  17. 		//x映射的位标记成1
  18. 		void set(size_t x)
  19. 		{
  20. 			// x映射的比特位在第几个char对象
  21. 			size_t i = x / 8;
  22.  
  23. 			// x在char第几个比特位
  24. 			size_t j = x % 8;
  25.  
  26. 			_bits[i] |= (1 << j);
  27. 		}
  28.  
  29. 		void reset(size_t x)
  30. 		{
  31. 			// x映射的比特位在第几个char对象
  32. 			size_t i = x / 8;
  33.  
  34. 			// x在char第几个比特位
  35. 			size_t j = x % 8;
  36.  
  37. 			//! && ||
  38. 			//~ &  | 
  39. 			_bits[i] &= (~(1 << j));
  40. 		}
  41.  
  42. 		bool test(size_t x)
  43. 		{
  44. 			// x映射的比特位在第几个char对象
  45. 			size_t i = x / 8;
  46.  
  47. 			// x在char第几个比特位
  48. 			size_t j = x % 8;
  49.  
  50. 			return _bits[i] & (1 << j);
  51. 		}
  52.  
  53. 	private:
  54. 		std::vector<char> _bits;
  55. 		//vector<int> _bits;
  56. 	};
  57.  
  58. 	template<size_t N>
  59. 	class two_bitset
  60. 	{
  61. 	public:
  62. 		void set(size_t x)
  63. 		{
  64. 			int in1 = _bs1.test(x);
  65. 			int in2 = _bs2.test(x);
  66. 			if (in1 == 0 && in2 == 0)
  67. 			{
  68. 				_bs2.set(x);
  69. 			}
  70. 			else if (in1 == 0 && in2 == 1)
  71. 			{
  72. 				_bs1.set(x);
  73. 				_bs2.reset(x);
  74. 			}
  75. 		}
  76.  
  77. 		bool is_once(size_t x)
  78. 		{
  79. 			return _bs1.test(x) == 0 && _bs2.test(x) == 1;
  80. 		}
  81.  
  82. 	private:
  83. 		bitset<N> _bs1;
  84. 		bitset<N> _bs2;
  85. 	};
  86. }

 位图2：

  1. #pragma once
  2. #include <vector>
  3. //位图2
  4. namespace my
  5. {
  6. 	// N个比特位的位图  10  16
  7. 	template<size_t N>
  8. 	class bitset
  9. 	{
  10. 	public:
  11. 		bitset()
  12. 		{
  13. 			// +1保证足够比特位，最多浪费8个
  14. 			_bits.resize(N / 8 + 1, 0);
  15. 		}
  16.  
  17. 		//x映射的位标记成1
  18. 		void set(size_t x)
  19. 		{
  20. 			// x映射的比特位在第几个char对象
  21. 			size_t i = x / 8;
  22.  
  23. 			// x在char第几个比特位
  24. 			size_t j = x % 8;
  25.  
  26. 			_bits[i] |= (1 << j);
  27. 		}
  28.  
  29. 		void reset(size_t x)
  30. 		{
  31. 			// x映射的比特位在第几个char对象
  32. 			size_t i = x / 8;
  33.  
  34. 			// x在char第几个比特位
  35. 			size_t j = x % 8;
  36.  
  37. 			//! && ||
  38. 			//~ &  | 
  39. 			_bits[i] &= (~(1 << j));
  40. 		}
  41.  
  42. 		bool test(size_t x)
  43. 		{
  44. 			// x映射的比特位在第几个char对象
  45. 			size_t i = x / 8;
  46.  
  47. 			// x在char第几个比特位
  48. 			size_t j = x % 8;
  49.  
  50. 			return _bits[i] & (1 << j);
  51. 		}
  52.  
  53. 	private:
  54. 		std::vector<char> _bits;
  55. 		//vector<int> _bits;
  56. 	};
  57.  
  58. 	template<size_t N>
  59. 	class two_bitset
  60. 	{
  61. 	public:
  62. 		void set(size_t x)
  63. 		{
  64. 			int in1 = _bs1.test(x);
  65. 			int in2 = _bs2.test(x);
  66. 			//00
  67. 			if (in1 == 0 && in2 == 0)
  68. 			{
  69. 				_bs2.set(x);  //01
  70. 			}
  71. 			//01
  72. 			else if (in1 == 0 && in2 == 1)
  73. 			{
  74. 				_bs1.set(x);  //10
  75. 				_bs2.reset(x);
  76. 			}
  77. 			//10
  78. 			else if (in1 == 1 && in2 == 0)
  79. 			{
  80. 				_bs2.set(x);  //11
  81. 			}
  82. 		}
  83. 		bool is_once(size_t x)
  84. 		{
  85. 			return _bs1.test(x) == 0 && _bs2.test(x) == 1;
  86. 		}
  87.  
  88. 	private:
  89. 		bitset<N> _bs1;
  90. 		bitset<N> _bs2;
  91. 	};
  92. }

3.2 布隆过滤器模拟实现源码:

BloomFilter:

3.3 附用的unordered_set、unordered_map、OpenHash:

unordered_set:

  1. #include"OpenHT.h"
  2.  
  3. namespace my
  4. {
  5. 	template<class K, class HashFunc = DefaultHash<K>>
  6. 	class unordered_set
  7. 	{
  8. 		//内部类
  9. 		struct SetKeyOfT
  10. 		{
  11. 			const K& operator()(const K& key)
  12. 			{
  13. 				return key;
  14. 			}
  15. 		};
  16. 	public:
  17. 		typedef typename Bucket::HashTable<K, K, SetKeyOfT, HashFunc>::iterator iterator;
  18.  
  19. 		iterator begin()
  20. 		{
  21. 			return _ht.begin();
  22. 		}
  23.  
  24. 		iterator end()
  25. 		{
  26. 			return _ht.end();
  27. 		}
  28. 		//bool insert(const K& key)
  29. 		pair<iterator, bool> insert(const K& key)
  30. 		{
  31. 			return _ht.Insert(key);
  32. 		}
  33. 		iterator find(const K& key)
  34. 		{
  35. 			return _ht.Find(key);
  36. 		}
  37. 		bool erase(const K& key)
  38. 		{
  39. 			return _ht.Erase(key);
  40. 		}
  41. 	private:
  42. 		Bucket::HashTable<K, K, SetKeyOfT,HashFunc> _ht;
  43. 	};
  44. 	
  45. }

unordered_map:

  1. #include"OpenHT.h"
  2.  
  3. namespace my
  4. {
  5. 	template<class K, class V, class HashFunc = DefaultHash<K>>
  6. 	class unordered_map
  7. 	{
  8. 		//内部类
  9. 		struct MapKeyOfT
  10. 		{
  11. 			const K& operator()(const pair<K,V>& kv)
  12. 			{
  13. 				return kv.first;
  14. 			}
  15. 		};
  16. 	public:
  17. 		//定义map的迭代器
  18. 		typedef typename Bucket::HashTable<K, pair<K, V>, MapKeyOfT, HashFunc> ::iterator iterator;
  19. 		iterator begin()
  20. 		{
  21. 			return _ht.begin();
  22. 		}
  23.  
  24. 		iterator end()
  25. 		{
  26. 			return _ht.end();
  27. 		}
  28. 		//bool insert(const pair<K, V>& kv)
  29. 		pair<iterator,bool> insert(const pair<K, V>& kv)
  30. 		{
  31. 			return _ht.Insert(kv);
  32.  
  33. 		}
  34. 		iterator find(const K& key)
  35. 		{
  36. 			return _ht.Find(key);
  37. 		}
  38. 		bool erase(const K& key)
  39. 		{
  40. 			return _ht.Erase(key);
  41. 		}
  42. 		V& operator[](const K& key)
  43. 		{
  44. 			//pair<iterator, bool> ret = insert(make_pair(key, V()));
  45. 			auto ret = insert(make_pair(key, V()));
  46. 			return ret.first->second;  //first是迭代器，而map里面访问second要用->,其实这里有两个->,但为了可读性
  47. 		}
  48. 	private:
  49. 		Bucket::HashTable<K, pair<K, V>, MapKeyOfT,HashFunc> _ht;
  50. 	};
  51. }

OpenHash:

  1. #pragma once
  2. #include<iostream>
  3. #include<string>
  4. #include<vector>
  5. #include<map>
  6. #include<set>
  7. #include<unordered_map>
  8. #include<unordered_set>
  9. using namespace std;
  10.  
  11. //仿函数
  12. template<class K>
  13. struct DefaultHash        //1.普通类直接强转
  14. {
  15. 	size_t operator()(const K& key)
  16. 	{
  17. 		return(size_t)key; //支持取模，强转为整数
  18. 	}
  19. };
  20. template<>
  21. struct DefaultHash<string>     //String类特化
  22. {
  23. 	size_t operator()(const string& key)
  24. 	{
  25. 		//4.BKDR法
  26. 		size_t hash = 0;
  27. 		for (auto ch : key)
  28. 		{
  29. 			hash = hash * 131 + ch;
  30. 		}
  31. 		return hash;
  32. 	}
  33. };
  34. namespace Bucket
  35. {
  36. 	template<class T>
  37. 	struct HashNode
  38. 	{
  39. 		T _data;
  40. 		HashNode<T>* _next;
  41. 		HashNode(const T& data)
  42. 			:_data(data)
  43. 			, _next(nullptr)
  44. 		{}
  45. 	};
  46.  
  47. 	template<class K, class T, class KeyOfT, class HashFunc>
  48. 	class HashTable;
  49.  
  50. 	template<class K, class T, class KeyOfT, class HashFunc>
  51. 	class __HTIterator   //单向迭代器
  52. 	{
  53. 		typedef HashNode<T> Node;
  54. 		typedef __HTIterator<K, T, KeyOfT, HashFunc> Self;
  55. 	public:
  56. 		Node* _node;
  57. 		HashTable<K, T, KeyOfT, HashFunc>* _pht;
  58. 		__HTIterator(){}   //默认哈希迭代器构造函数
  59. 		__HTIterator(Node* node, HashTable<K, T, KeyOfT, HashFunc>* pht)
  60. 			:_node(node)
  61. 			,_pht(pht)
  62. 		{}
  63.  
  64. 		Self& operator++()
  65. 		{
  66. 			if (_node->_next)
  67. 			{
  68. 				_node = _node->_next;
  69. 			}
  70. 			else
  71. 			{
  72. 				KeyOfT kot;
  73. 				HashFunc hf;
  74. 				size_t hashi = hf(kot(_node->_data))%_pht->_tables.size();
  75. 				++hashi;
  76. 				//找下一个不为空的桶
  77. 				for (; hashi < _pht->_tables.size(); ++hashi)
  78. 				{
  79. 					if (_pht->_tables[hashi])
  80. 					{
  81. 						_node = _pht->_tables[hashi];
  82. 						break;
  83. 					}
  84. 				}
  85.  
  86. 				// 没有找到不为空的桶，用nullptr去做end标识
  87. 				if (hashi == _pht->_tables.size())
  88. 				{
  89. 					_node = nullptr;
  90. 				}
  91. 			}
  92.  
  93. 			return *this;
  94. 		}
  95.  
  96. 		T& operator*()
  97. 		{
  98. 			return _node->_data;
  99. 		}
  100.  
  101. 		T* operator->()
  102. 		{
  103. 			return &_node->_data;
  104. 		}
  105.  
  106. 		bool operator!=(const Self& s) const
  107. 		{
  108. 			return _node != s._node;
  109. 		}
  110.  
  111. 		bool operator==(const Self& s) const
  112. 		{
  113. 			return _node == s._node;
  114. 		}
  115. 	};
  116.  
  117. 	//unordered_set--->HashTable<K, K, SetKeyOfT> _ht;
  118. 	//unordered_map--->HashTable<K, pair<K, V>, MapKeyOfT> _ht;
  119. 	template<class K, class T, class KeyOfT, class HashFunc>
  120. 	class HashTable
  121. 	{
  122. 		template<class K, class T, class KeyOfT, class HashFunc>
  123. 		friend class __HTIterator;
  124. 		typedef HashNode<T> Node;
  125. 	public:
  126. 		typedef __HTIterator<K, T, KeyOfT, HashFunc> iterator;
  127. 		iterator begin()
  128. 		{
  129. 			for (size_t i = 0; i < _tables.size(); ++i)
  130. 			{
  131. 				Node* cur = _tables[i];
  132. 				if (cur)
  133. 				{
  134. 					return iterator(cur, this);
  135. 				}
  136. 			}
  137.  
  138. 			return end();
  139. 		}
  140.  
  141. 		iterator end()
  142. 		{
  143. 			return iterator(nullptr, this);
  144. 		}
  145. 		//手动实现Node的析构函数
  146. 		~HashTable()
  147. 		{
  148. 			for (size_t i = 0; i < _tables.size(); ++i)
  149. 			{
  150. 				Node* cur = _tables[i];
  151. 				while (cur)
  152. 				{
  153. 					Node* next = cur->_next;
  154. 					delete cur;
  155. 					cur = next;
  156. 				}
  157. 				_tables[i] = nullptr;
  158. 			}
  159. 		}
  160. 		
  161. 		///
  162. 		HashTable() = default;  //强制生成默认构造函数
  163.  
  164. 		链表桶的深拷贝
  165. 		//HashTable(const HashTable<K, V> ht)
  166. 		//{
  167. 		//	int sz = ht._tables.size();
  168. 		//	for (int i = 0; i < sz; i++)
  169. 		//	{
  170. 		//		Node* cur = ht._tables[i];
  171. 		//		while (cur)
  172. 		//		{
  173. 		//			this->Insert(cur->_kv);
  174. 		//			cur = cur->_next;
  175. 		//		}
  176. 		//	}
  177. 		//	_n = ht._n;
  178.  
  179. 		//}
  180. 		链表桶的赋值重载
  181. 		//HashTable<K, V>& operator=(HashTable<K, V> ht)
  182. 		//{
  183. 		//	//现代写法
  184. 		//	ht._tablle.swap(_tables);
  185. 		//	_n = ht._n;
  186. 		//}
  187. 		///
  188. 		size_t GetNextPrime(size_t prime)
  189. 		{
  190. 			const int PRIMECOUNT = 28;
  191. 			static const size_t primeList[PRIMECOUNT] =
  192. 			{
  193. 				53ul, 97ul, 193ul, 389ul, 769ul,
  194. 				1543ul, 3079ul, 6151ul, 12289ul, 24593ul,
  195. 				49157ul, 98317ul, 196613ul, 393241ul, 786433ul,
  196. 				1572869ul, 3145739ul, 6291469ul, 12582917ul, 25165843ul,
  197. 				50331653ul, 100663319ul, 201326611ul, 402653189ul, 805306457ul,
  198. 				1610612741ul, 3221225473ul, 4294967291ul
  199. 			};
  200.  
  201. 			// 获取比prime大那一个素数
  202. 			size_t i = 0;
  203. 			for (; i < PRIMECOUNT; ++i)
  204. 			{
  205. 				if (primeList[i] > prime)
  206. 					return primeList[i];
  207. 			}
  208.  
  209. 			return primeList[i];
  210. 		}
  211. 		//bool Insert(const T& data)
  212. 		pair<iterator,bool> Insert(const T& data)
  213. 		{
  214. 			HashFunc hf;
  215. 			KeyOfT kot;
  216. 			//if (Find(kot(data)))  //使用仿函数，不知道data是set还是map
  217. 			//if (Find(kot(data))!=end())  //使用仿函数，不知道data是set还是map
  218.  
  219. 			iterator pos = Find(kot(data));
  220. 			if(pos!=end())
  221. 			{
  222. 				//return false;
  223. 				return make_pair(pos,false);
  224. 			}
  225.  
  226. 			//负载因子（这里设置为1）  扩容
  227. 			if (_tables.size() == _n)
  228. 			{
  229. 				//写法2：扩容
  230. 				//size_t newSize = _tables.size() == 0 ? 10 : _tables.size() * 2;
  231. 				//写法3：
  232. 				size_t newSize = GetNextPrime(_tables.size());
  233. 				if (newSize != _tables.size())
  234. 				{
  235. 					vector<Node*> newTable;
  236. 					newTable.resize(newSize, nullptr);
  237.  
  238. 					for (size_t i = 0; i < _tables.size(); ++i)
  239. 					{
  240. 						Node* cur = _tables[i];
  241. 						while (cur)
  242. 						{
  243. 							size_t hashi = hf(kot(cur->_data)) % newSize;  //hf转换为整型,kot()取k
  244. 							cur->_next = newTable[hashi];
  245. 							newTable[hashi] = cur;
  246. 							cur = cur->_next;
  247. 						}
  248. 						_tables[i] = nullptr;
  249. 					}
  250. 					newTable.swap(_tables);
  251.  
  252. 				}
  253. 			}
  254. 			size_t hashi = hf(kot(data)); //两层仿函数调用
  255. 			hashi %= _tables.size();
  256. 			//头插到对应的桶即可
  257. 			Node* newnode = new Node(data);
  258. 			newnode->_next = _tables[hashi];
  259. 			_tables[hashi] = newnode;
  260. 			++_n;
  261. 			//return true;
  262. 			return make_pair(iterator(newnode,this),false);
  263. 		}
  264. 		//Node* Find(const K& key)
  265. 		iterator Find(const K& key)
  266. 		{
  267. 			if (_tables.size() == 0)
  268. 			{
  269. 				//return nullptr;
  270. 				return iterator(nullptr,this);
  271.  
  272. 			}
  273. 			
  274. 			KeyOfT kot;
  275. 			//写法1：有名对象
  276. 			HashFunc hf;
  277. 			size_t hashi = hf(key);
  278.  
  279. 			//写法2：匿名对象
  280. 			//size_t hashi = HashFunc()(key);
  281.  
  282. 			hashi %= _tables.size();
  283. 			Node* cur = _tables[hashi];
  284. 			while (cur)
  285. 			{
  286. 				if (kot(cur->_data) == key)
  287. 				{
  288. 					//return cur;
  289. 					return iterator(cur, this);
  290. 				}
  291. 				cur = cur->_next;
  292. 			}
  293. 			//return nullptr;  //效率高，是因为直接返回了指针
  294. 			return iterator(nullptr, this);
  295. 		}
  296. 		bool Erase(const K& key)
  297. 		{
  298. 			if (_tables.size() == 0)
  299. 			{
  300. 				return false;
  301. 			}
  302. 			KeyOfT kot;
  303.  
  304. 			//写法1：有名对象
  305. 			HashFunc hf;
  306. 			size_t hashi = hf(key);
  307. 			hashi %= _tables.size();
  308. 			Node* cur = _tables[hashi];
  309. 			Node* prev = nullptr;
  310. 			while (cur)
  311. 			{
  312. 				if (kot(cur->_data) == key)
  313. 				{
  314. 					if (prev == nullptr)
  315. 					{
  316. 						_tables[hashi] = cur->_next;
  317. 					}
  318. 					else
  319. 					{
  320. 						prev->_next = cur->_next;
  321. 					}
  322. 					delete cur;
  323. 					return true;
  324. 					
  325. 				}
  326. 				cur = cur->_next;
  327. 			}
  328. 			return false;
  329. 		}
  330. 	private:
  331. 		//指针数组
  332. 		//没有使用list，是因为list是双向链表，成本大 vector<list<>> _tables; 但不用手动写析构函数
  333. 		vector<Node*> _tables;    
  334. 		//开散列采用挂起，如果新表扩容，那么当旧表释放，vector会将自己的释放，
  335. 		//但是挂在vector的结点Node* 不会自动释放，因为Node* 是内置类型，需要手动释放。
  336. 		size_t _n = 0;
  337. 	};
  338. }

3.4 test.cpp:

  1. #include"OpenHT.h"
  2. #include"UnorderedSet.h"
  3. #include"UnorderedMap.h"
  4. #include"BitSet.h"
  5. #include"BloomFilter.h"
  6. //
  7. //1.库中的UnorderedSet、UnorderedMap测试
  8. void test_std_UnorderedSet()
  9. {
  10. 	std::unordered_set<int> s;
  11. 	s.insert(9);
  12. 	s.insert(7);
  13. 	s.insert(2);
  14. 	s.insert(1);
  15. 	s.insert(6);
  16. 	s.insert(5);
  17. 	//1.迭代器遍历
  18. 	//unordered_set<int>::iterator it = s.begin();
  19. 	//auto it = s.begin();
  20. 	//写法2：
  21. 	std::unordered_set<int>::iterator it;
  22. 	it = s.begin();
  23. 	while (it != s.end())
  24. 	{
  25. 		cout << *it << " ";
  26. 		++it;
  27. 	}
  28. 	cout << endl;
  29. 	//2.范围for遍历
  30. 	for (auto e : s)
  31. 	{
  32. 		cout << e << " ";
  33. 	}
  34. 	cout << endl;
  35. }
  36. void test_std_UnorderedMap()
  37. {
  38. 	std::unordered_map<string, string> dict;
  39. 	dict.insert(make_pair("sort", "排序"));
  40. 	dict.insert(make_pair("left", "左边"));
  41. 	dict.insert(make_pair("left", "剩余"));
  42. 	dict["string"];
  43. 	dict["left"] = "剩余";
  44. 	dict["string"] = "字符串";
  45. 	//迭代器遍历
  46. 	//std::unordered_map<string, string>::iterator it = dict.begin();
  47. 	auto it = dict.begin();
  48. 	while (it != dict.end())
  49. 	{
  50. 		cout << it->first << " " << it->second << endl;
  51. 		++it;
  52. 	}
  53. 	cout << endl;
  54. 	//范围for遍历
  55. 	for (auto& kv : dict)
  56. 	{
  57. 		cout << kv.first << " " << kv.second << endl;
  58. 	}
  59. }
  60. //
  61. //2.模拟实现UnorderedSet、UnorderedMap测试
  62. void test_my_UnorderedSet()
  63. {
  64. 	my::unordered_set<int> s;
  65. 	s.insert(9);
  66. 	s.insert(7);
  67. 	s.insert(2);
  68. 	s.insert(1);
  69. 	s.insert(6);
  70. 	s.insert(5);
  71. 	//1.迭代器遍历
  72. 	//my::unordered_set<int>::iterator it = s.begin();
  73. 	//auto it = s.begin();
  74. 	//写法2：
  75. 	my::unordered_set<int>::iterator it;
  76. 	it = s.begin();
  77. 	while (it != s.end())
  78. 	{
  79. 		cout << *it << " ";
  80. 		++it;
  81. 	}
  82. 	cout << endl;
  83. 	//2.范围for遍历
  84. 	for (auto e : s)
  85. 	{
  86. 		cout << e << " ";
  87. 	}
  88. 	cout << endl;
  89. }
  90. void test_my_UnorderedMap()
  91. {
  92. 	my::unordered_map<string, string> dict;
  93. 	dict.insert(make_pair("sort", "排序"));
  94. 	dict.insert(make_pair("left", "左边"));
  95. 	dict.insert(make_pair("left", "剩余"));
  96. 	dict["string"];
  97. 	dict["left"] = "剩余";
  98. 	dict["string"] = "字符串";
  99. 	//迭代器遍历
  100. 	//my::unordered_map<string, string>::iterator it = dict.begin();
  101. 	auto it = dict.begin();
  102. 	while (it != dict.end())
  103. 	{
  104. 		cout << it->first << " " << it->second << endl;
  105. 		++it;
  106. 	}
  107. 	cout << endl;
  108. 	//范围for遍历
  109. 	for (auto& kv : dict)
  110. 	{
  111. 		cout << kv.first << " " << kv.second << endl;
  112. 	}
  113. }
  114. //
  115. //3.模拟实现bitset测试
  116. void test_my_bit_set()
  117. {
  118. 	my::bitset<100> bs;
  119. 	bs.set(18);
  120. 	bs.set(19);
  121.  
  122. 	cout << bs.test(18) << endl;
  123. 	cout << bs.test(19) << endl;
  124. 	cout << bs.test(20) << endl;
  125.  
  126.  
  127. 	bs.reset(18);
  128. 	bs.reset(18);
  129.  
  130. 	cout << bs.test(18) << endl;
  131. 	cout << bs.test(19) << endl;
  132. 	cout << bs.test(20) << endl;
  133.  
  134. 	//my::bitset<INT_MAX> bigBS;
  135. 	my::bitset<0xFFFFFFFF> bigBS;
  136. 	//my::bitset<-1> bigBS;
  137.  
  138.  
  139.  
  140. 	//bit_set<2^32-1> bigBS; // pow
  141. }
  142.  
  143. //4.模拟实现two_bitset
  144. void test_my_two_bitset()
  145. {
  146. 	int a[] = { 4, 3, 2, 4, 5, 2, 2, 4, 7, 8, 9, 2, 1,3,7 };
  147. 	my::two_bitset<10> tbs;
  148. 	for (auto e : a)
  149. 	{
  150. 		tbs.set(e);
  151. 	}
  152.  
  153. 	for (size_t i = 0; i < 10; ++i)
  154. 	{
  155. 		if (tbs.is_once(i))
  156. 		{
  157. 			cout << i << " ";
  158. 		}
  159. 	}
  160. 	cout << endl;
  161. }
  162.  
  163. //5.模拟实现BloomFilter测试
  164. void test_my_BloomFilter1()
  165. {
  166. 	//插入10个数据
  167. 	//写法1：43是计算的值（具体参见文档）
  168. 	//my::BloomFilter<string, 43, my::BKDRHash, my::APHash, my::DJBHash> bf;
  169. 	//写法2：43是计算的值（具体参见文档），因为模板给了缺省值，因此这里只传第一个数据类型即可
  170. 	my::BloomFilter<43> bf;
  171.  
  172. 	string a[] = { "铭记历史","勿忘国耻","振兴中华","吾辈自强","1931.09.18","九*一八事变","2022.09.18"};
  173. 	for (auto e : a)
  174. 	{
  175. 		cout << e <<" ";
  176. 	}
  177. 	cout << endl;
  178. 	
  179. 	for (auto& e : a)
  180. 	{
  181. 		bf.Set(e);
  182. 	}
  183. 	for (auto& e : a)
  184. 	{
  185. 		cout << bf.Test(e) << endl;
  186. 	}
  187. 	cout << bf.Test("缅怀先烈") << endl;
  188. 	cout << bf.Test("吾辈自强") << endl;
  189. 	cout << bf.Test("砥砺前行") << endl;
  190. }
  191. //6.模拟实现布隆过滤器测试对比误判率
  192. void test_my_BloomFilter2()
  193. {
  194. 		srand(time(0));
  195. 		//给不同的值，观察误判率
  196. 		//一般来说，空间越大，冲突率越小
  197. 		const size_t N = 10000;
  198. 	  /*const size_t N = 60000;
  199. 		const size_t N = 100000;*/
  200. 	  /*my::BloomFilter<5 * N> bf;
  201. 		my::BloomFilter<6 * N> bf;*/
  202. 		my::BloomFilter<8 * N> bf;
  203.  
  204.  
  205.  
  206. 		std::vector<std::string> v1;
  207. 		std::string url = "https://www.cnblogs.com/-clq/archive/2012/05/31/2528153.html";
  208.  
  209. 		for (size_t i = 0; i < N; ++i)
  210. 		{
  211. 			v1.push_back(url + std::to_string(1234 + i));
  212. 		}
  213.  
  214. 		for (auto& str : v1)
  215. 		{
  216. 			bf.Set(str);
  217. 		}
  218. 		//打印判断的key的bool返回值（1或0）
  219. 		/*for (auto& str : v1)
  220. 		{
  221. 		cout << bf.Test(str) << endl;
  222. 		}
  223. 		cout << endl << endl;*/
  224. 		//给一个相似的字符串
  225. 		std::vector<std::string> v2;
  226. 		for (size_t i = 0; i < N; ++i)
  227. 		{
  228. 			std::string url = "https://www.cnblogs.com/-clq/archive/2012/05/31/2528153.html";
  229. 			url += std::to_string(999999 + i);
  230. 			v2.push_back(url);
  231. 		}
  232. 		//判断并统计。如果在，就是误判
  233. 		size_t n2 = 0;
  234. 		for (auto& str : v2)
  235. 		{
  236. 			if (bf.Test(str))
  237. 			{
  238. 				++n2;
  239. 			}
  240. 		}
  241. 		cout << "相似字符串误判率:" << (double)n2 / (double)N << endl;
  242.  
  243. 		std::vector<std::string> v3;
  244. 		for (size_t i = 0; i < N; ++i)
  245. 		{
  246. 			string url = "zhihu.com";
  247. 			url += std::to_string(rand());
  248. 			v3.push_back(url);
  249. 		}
  250.  
  251. 		size_t n3 = 0;
  252. 		for (auto& str : v3)
  253. 		{
  254. 			if (bf.Test(str))
  255. 			{
  256. 				++n3;
  257. 			}
  258. 		}
  259. 		cout << "不相似字符串误判率:" << (double)n3 / (double)N << endl;
  260. }
  261. int main()
  262. {
  263. 	//test_std_UnorderedSet();
  264. 	//test_std_UnorderedMap();
  265.  
  266. 	//test_my_UnorderedSet();
  267. 	//test_my_UnorderedMap();
  268.  
  269. 	//test_my_bit_set();
  270. 	//test_my_two_bitset();
  271.  
  272. 	//test_my_BloomFilter1();
  273. 	test_my_BloomFilter2();
  274.  
  275. 	return 0;
  276. }

后记：
●由于作者水平有限，文章难免存在谬误之处，敬请读者斧正，俚语成篇，恳望指教！

                                                                           ——By 作者：新晓·故知

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/从前慢现在也慢/article/detail/436881
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号