• 哈希的应用

    目录

    一.位图

    1.概念 

    2.bitset使用

    3.实现

    4.题

    二.哈希切割

    三.布隆过滤器

    1.概念

    2.实现代码

    3.插入

    4.查找

    5.删除

    6.优缺点

    （1）优点

    （2）缺点

    7.题

    前言：位图是根据哈希思想来通过bit位存储某种状态的，是适用于海量数据的情况。布隆过滤器是为了解决除整型外其它类型的海量数据的情况，思想与位图相同。哈希切割则是另一个对大文件进行哈希切分成多个小文件的思想。

    一.位图

    1.概念 

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

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

            这道题就可以用位图来解决：数据是否在给定的整型数据中，结果是在或者不在，刚好是两种状态，那么可以使用一个二进制bit位来代表数据是否存在的信息，如果二进制bit位为1，代表存在；为0，代表不存在。

    2.bitset使用

            位图的实现并不难，并且在C++中是有这个的，bitset可以看作是一种特殊的容器，是二进制位的容器。主要的接口如下：

    set(size_t pos)：将pos数所映射的bit位标记为1

    reset(size_t pos)：将pos数所映射的bit标记回0

    test(size_t pos)：检测pos数所映射的bit为是否为1，为1则返回true

    3.实现

           我们这里用vector来实现位图。

           首先是一个构造函数，要开N / 8 + 1个空间，因为一个字节有8个bit位，并且我们不确定这个N是否为8的倍数，因此我们要多开一个空间，即使浪费也只是最多浪费8个而已。

            set函数首先要得到x映射的bit位在第几个char对象（这里用x / 8就可以得到），然后再得到x在该char对象的第几个bit位（这里用x % 8就可以得到）。最后通过按位或|【_bits[i] |= (1 << j)】操作，就可以在不影响其它位的情况下，将对应的char对象的对应的bit位变为1。

            reset函数前面也是要得到对应的位置，然后通过按位与&【_bits[i] &= (~(1 << j))】操作，在不影响其它位的情况下，将对应的char对象的对应的bit位变为0。

            test函数前面一样要得到对应的位置，然后通过按位与【_bits[i] & (1 << j)】操作，在不影响任何位的情况下，可以判断对应char对象的对应的bit位为1还是0，并返回一个bool类型。为1则为true，为0则为false。

    1. namespace hb
    2. {
    3. 	// N个bit位的位图
    4. 	template<size_t N>
    5. 	class bitset
    6. 	{
    7. 	public:
    8. 		bitset()
    9. 		{
    10. 			// +1保证bit位，最多浪费8个
    11. 			_bits.resize(N / 8 + 1, 0);
    12. 		}
    13.  
    14. 		// x映射的位标记成1
    15. 		void set(size_t x)
    16. 		{
    17. 			// x映射的bit位在第几个char对象
    18. 			size_t i = x / 8;
    19.  
    20. 			// x在char的第几个bit位
    21. 			size_t j = x % 8;
    22.  
    23. 			_bits[i] |= (1 << j);
    24. 		}
    25.  
    26. 		void reset(size_t x)
    27. 		{
    28. 			size_t i = x / 8;
    29.  
    30. 			size_t j = x % 8;
    31.  
    32. 			_bits[i] &= (~(1 << j));
    33. 		}
    34.  
    35. 		bool test(size_t x)
    36. 		{
    37. 			// x映射的bit位在第几个char对象
    38. 			size_t i = x / 8;
    39.  
    40. 			size_t j = x % 8;
    41.  
    42. 			return _bits[i] & (1 << j);
    43. 		}
    44.  
    45. 	private:
    46. 		std::vector<char> _bits;
    47. 	};
    48. }

    4.题

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

            可以创建两个位图，如果没有出现，两个位图对应的位置都是0（即00）；出现一次的，让两个位图对应的位置分别是0和1（即01）；出现两次及以上的，让两个位图对应的位置分别是1和0（即10）。

            最后判断，如果是01的就是要找的只出现一次的整数。

    1. class two_bitset
    2. {
    3. public:
    4. 	void set(size_t x)
    5. 	{
    6. 		int in1 = _bs1.test(x);
    7. 		int in2 = _bs2.test(x);
    8. 		if (in1 == 0 && in2 == 0)
    9. 		{
    10. 			_bs2.set(x);
    11. 		}
    12. 		else if (in1 == 0 && in2 == 1)
    13. 		{
    14. 			_bs1.set(x);
    15. 			_bs2.reset(x);
    16. 		}
    17. 	}
    18.  
    19. 	bool is_once(size_t x)
    20. 	{
    21. 		return _bs1.test(x) == 0 && _bs2.test(x) == 1;
    22. 	}
    23. private:
    24. 	bitset _bs1;
    25. 	bitset _bs2;
    26. };

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

            位图的题都差不多，这道题要先对两个文件的整数去重，然后再分别存在两个位图中，出现的数就变为1，最后两个相比较，为1的就是交集。

    （3）1个文件有100亿个int，1G内存，设计算法找到出现次数不超过2次的所有整数。

            创建两个位图，如果没有出现，两个位图对应的位置都是0（即00）；出现一次的，让两个位图对应的位置分别是0和1（即01）；出现两次的，让两个位图对应的位置分别是1和0（即10）；

    出现两次以上的，让两个位图对应的位置都是1（即11）。

            最后判断，如果是01和10的就是结果。

             与（1）几乎一样，只是多了个11。

    二.哈希切割

    我们看这样一道题：给一个超过100个G大小的log文件，log中存着ip地址，设计算法找到出现次数最多的IP地址。

            这道题是属于KV模型的，就不能用布隆过滤器（布隆过滤器本质上就是位图，布隆过滤器是用来解决处理整数外的其它类型，在下面介绍）来解决了，因此我们可以用哈希切割这一思想。

            首先我们依次读取ip，并按照i = HashFunc（ip） % 100，这样切分成100个小文件【A0，A1，A2... A99】（这就可以使相同的ip一定进入同一个小文件）。

            但是存在这样的问题，映射冲突这个编号文件的ip太多，这就可能导致内存不足，因此我们可以采用抛异常的方式来解决。

    1. try
    2. {
    3.     countMap[ip]++;
    4. }
    5. catch(exception& e)
    6. {
    7.     countMap.clear();
    8.  
    9.     // 捕获内存不足的异常，说明内存不够
    10.     // 针对这个小文件，再次换个哈希函数，进行哈希切分，再切分成小文件
    11. }
    12.     // 再对小文件依次统计

    三.布隆过滤器

    1.概念

            布隆过滤器是由布隆提出的一种紧凑、比较巧妙的概率型数据结构，特点是可以高效地插入和查询，可以解决“某种东西一定不存在，或者可能存在”。

            它是用多个哈希函数，将一个数据映射到位图结构中。此种方式不仅可以提升查询效率，也可以节省大量的内存空间。

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

    2.实现代码

            布隆过滤器要用多种哈希函数主要去对string类型进行不同的转化，然后使一个字符串产生多种映射位置，依次分别进行插入，并根据这个进行查找或者删除。

    1. namespace hb
    2. {
    3. 	struct BKDRHash
    4. 	{
    5. 		size_t operator()(const string& s)
    6. 		{
    7. 			// BKDR
    8. 			size_t value = 0;
    9. 			for (auto ch : s)
    10. 			{
    11. 				value *= 31;
    12. 				value += ch;
    13. 			}
    14. 			return value;
    15. 		}
    16. 	};
    17.  
    18. 	struct APHash
    19. 	{
    20. 		size_t operator()(const string& s)
    21. 		{
    22. 			size_t hash = 0;
    23. 			for (long i = 0; i < s.size(); i++)
    24. 			{
    25. 				if ((i & 1) == 0)
    26. 				{
    27. 					hash ^= ((hash << 7) ^ s[i] ^ (hash >> 3));
    28. 				}
    29. 				else
    30. 				{
    31. 					hash ^= (~((hash << 11) ^ s[i] ^ (hash >> 5)));
    32. 				}
    33. 			}
    34. 			return hash;
    35. 		}
    36. 	};
    37.  
    38. 	struct DJBHash
    39. 	{
    40. 		size_t operator()(const string& s)
    41. 		{
    42. 			size_t hash = 5381;
    43. 			for (auto ch : s)
    44. 			{
    45. 				hash += (hash << 5) + ch;
    46. 			}
    47. 			return hash;
    48. 		}
    49. 	};
    50.  
    51.  
    52. 	struct JSHash
    53. 	{
    54. 		size_t operator()(const string& s)
    55. 		{
    56. 			size_t hash = 1315423911;
    57. 			for (auto ch : s)
    58. 			{
    59. 				hash ^= ((hash << 5) + ch + (hash >> 2));
    60. 			}
    61. 			return hash;
    62. 		}
    63. 	};
    64.  
    65. 	template <size_t M,
    66. 	class K = string,
    67. 	class HashFunc1 = BKDRHash,
    68. 	class HashFunc2 = APHash,
    69. 	class HashFunc3 = DJBHash,
    70. 	class HashFunc4 = JSHash>
    71. 	class BloomFilter
    72. 	{
    73. 	public:
    74. 		void Set(const K& key)
    75. 		{
    76. 			size_t hash1 = HashFunc1()(key) % M;
    77. 			size_t hash2 = HashFunc2()(key) % M;
    78. 			size_t hash3 = HashFunc3()(key) % M;
    79. 			size_t hash4 = HashFunc4()(key) % M;
    80.  
    81. 			_bs.set(hash1);
    82. 			_bs.set(hash2);
    83. 			_bs.set(hash3);
    84. 			_bs.set(hash4);
    85. 		}
    86.  
    87. 		bool Test(const K& key)
    88. 		{
    89. 			size_t hash1 = HashFunc1()(key) % M;
    90. 			if (_bs.test(hash1) == false)
    91. 			{
    92. 				return false;
    93. 			}
    94.  
    95. 			size_t hash2 = HashFunc2()(key) % M;
    96. 			if (_bs.test(hash2) == false)
    97. 			{
    98. 				return false;
    99. 			}
    100.  
    101. 			size_t hash3 = HashFunc3()(key) % M;
    102. 			if (_bs.test(hash3) == false)
    103. 			{
    104. 				return false;
    105. 			}
    106.  
    107. 			size_t hash4 = HashFunc4()(key) % M;
    108. 			if (_bs.test(hash4) == false)
    109. 			{
    110. 				return false;
    111. 			}
    112.  
    113. 			return true; // 存在误判
    114. 		}
    115. 	private:
    116. 		bitset _bs;
    117. 	};
    118. }

    3.插入

            根据不同的哈希函数得到不同的映射位置，并分别将其插入进位图中。

    1. void Set(const K& key)
    2. {
    3. 	size_t hash1 = HashFunc1()(key) % M;
    4. 	size_t hash2 = HashFunc2()(key) % M;
    5. 	size_t hash3 = HashFunc3()(key) % M;
    6. 	size_t hash4 = HashFunc4()(key) % M;
    7.  
    8. 	_bs.set(hash1);
    9. 	_bs.set(hash2);
    10. 	_bs.set(hash3);
    11. 	_bs.set(hash4);
    12. }

    4.查找

    根据布隆过滤器的思想，我们可以按照这样的方式进行查找：

            分别计算每个哈希值对应的比特位置存储的是否为0，只要这些位置只要有一个为0，就代表该元素一定不在哈希表中，否则可能在哈希表中。

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

    1. bool Test(const K& key)
    2. {
    3. 	size_t hash1 = HashFunc1()(key) % M;
    4. 	if (_bs.test(hash1) == false)
    5. 	{
    6. 		return false;
    7. 	}
    8.  
    9. 	size_t hash2 = HashFunc2()(key) % M;
    10. 	if (_bs.test(hash2) == false)
    11. 	{
    12. 		return false;
    13. 	}
    14.  
    15. 	size_t hash3 = HashFunc3()(key) % M;
    16. 	if (_bs.test(hash3) == false)
    17. 	{
    18. 		return false;
    19. 	}
    20.  
    21. 	size_t hash4 = HashFunc4()(key) % M;
    22. 	if (_bs.test(hash4) == false)
    23. 	{
    24. 		return false;
    25. 	}
    26.  
    27. 	return true; // 存在误判
    28. }

    5.删除

            布隆过滤器正常是不能直接支持删除的，因为在删除一个元素时，可能会影响其它元素。

            有一种删除的方法是：将布隆过滤器中的每个比特位扩展成一个小的计数器，插入元素时给k个计数器（k分哈希函数计算处的哈希地址）+1，在删除元素时，给k个计数器-1，这样通过多占几倍的存储空间代价来增加删除操作。

    6.优缺点

    （1）优点

    ① 增加和查询元素的时间复杂度为O(K)，（K为哈希函数的个数，一般比较小）

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

    ③ 不需要存储元素本身，在某些对保密要求比较严格而的场合有很大优势

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

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

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

    （2）缺点

    ① 有误判率，不能准确判断元素是否在集合中（可以通过创建一个白名单，来存储可能会误判的数据）

    ② 不能获取元素本身

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

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

    7.题

    （1）给两个文件，分别由100亿个query（100字节），但只有1G内存，如何找到两个文件交集？分别给出近似算法和精确算法。

            近似算法就是通过布隆过滤器，跟位图中的（2）求交集一样，只是这里是利用布隆过滤器进行了转化。

            精确算法要用到布隆过滤器和哈希切割来实现，按照i = HashFunc（query） % 1000，这样切分成1000个小文件【A0，A1，A2... A999】，另一个文件也是如此，切分成1000个小文件【B0，B1，B2... B999】。切分之后，注意这里可以直接用set分别找编号相同的小文件交集（因为这里是使用set的，因此一定是精确的）。

  • 相关阅读:
    1.1 网页的基本概念
    Android 行情都这样了，面试问的还这么难？
    AI项目十五：PP-Humanseg训练及onnxruntime部署
    网课查题公众号搭建-附带查题接口
    【C语言】深剖字符串函数和内存函数
    vmware workstation pro 17.5 安装 macos 13.5.2 虚拟机超详细图文教程
    es笔记四之中文分词插件安装与使用
    识别人体神经网络的软件,识别人体神经网络系统
    台达DOP-B07S410触摸屏出现HMI no response无法上传的解决办法
    mssql ，数据库还原BAK命令行方式
  • 原文地址：https://blog.csdn.net/qq_60750110/article/details/126889004