代码会存放在

https://github.com/sjmshsh/Data-Struct-HandWriting

通过阅读本篇文章你可以学到

• 哈希思想及其本质
• 使用C++实现简易的哈希表
• 哈希思想的应用
  • 位图
  • 布隆过滤器
  • 哈希切分
  • 极致升华海量数据处理面试题
• 拓展 – 一致性哈希算法
• 用Golang实现简易的一致性哈希算法

哈希的本质我认为是以空间换取时间。牺牲空间以换取时间复杂度为O(1)哈希的用途很广泛例如RedisC++的STLJava的集合Go的map等等都用到了哈希他们的原理虽然略有区别但是基本上相同所以我们只要理解了这个思想就可以以分钟为单位的去学习其他地方的哈希。

哈希概念

其实增删查改CRUD一直是一个很大的话题为何要增删查改增删查改本质上是一种管理方式就好比操作系统中操作系统是一个管理员管理员需要先描述再组织描述就是把相关的数据抽象成一个结构体或者说类对象。组织就是对这些结构体或者类对象使用某种方式管理起来。数据的管理方式有很多常见的数据结构有链表栈堆红黑树AVL树B/B+树等等当然还有我们的哈希。

顺序结构以及平衡树中元素关键码与其存储位置之间没有对应的关系因此在查找一个元素时必须要经过关键码的多次比较。顺序查找时间复杂度为O(N)平衡树中为树的高度即O(logN)搜索的效率取决

于搜索过程中元素的比较次数。

理想的搜索方法可以不经过任何比较一次直接从表中得到要搜索的元素。 如果构造一种存储结构通过某种函数hashFunc使元素的存储位置与它的关键码之间能够建立一一映射的关系那么在查找时通过该函数可以很快找到该元素。

所以哈希的本质其实是简历映射关系的过程映射的建立是需要花费空间的但是它带来的O(1)的时间复杂度。

插入元素

根据待插入元素的关键码以此函数计算出该元素的存储位置并按此位置进行存放。

搜索元素

对元素的关键码进行同样的计算把求得的函数值当做元素的存储位置在结构中按此位置取元素比较若关键码相等则搜索成功。

该方式即为哈希(散列)方法哈希方法中使用的转换函数称为哈希(散列)函数构造出来的结构称为哈希表(Hash Table)(或者称散列表)。

现在可能还是很迷但是举一个例子就好了。

例如数据集合{176459}

哈希函数设置为hash(key) = key % capacity; capacity为存储元素底层空间总的大小。

好那么我们现在再次插入44这个元素可以发现我的位置已经被占了这就是所谓的哈希冲突问题。

哈希冲突

对不同的关键字可能得到同一散列地址即[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-2mcgJXBA-1673943600773)(null)]而{[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-ChcppzIi-1673943601177)(null)]这种现象称为冲突英语Collision)。

– 来自《维基百科》

1. 哈希冲突是否可以避免

   答哈希冲突是不可能避免的只能尽量的减小哈希冲突的概率因为在算哈希值的时候我们使用某种算法进行计算难免会遇到计算的哈希值是相同的情况。

2. 哈希冲突会带来什么影响

   答当冲突到达一定的程度的时候哈希表的效率会显著的降低具体原因后续再讲。

3. 如何尽可能的规避哈希冲突

   答引起哈希冲突的一个很重要的原因就是哈希函数的设计不合理。一个优秀的哈希函数应该满足以下几个条件

   • 哈希函数的定义域必须包括需要存储的全部关键码而如果散列表允许有m个地址时其值域必须在0到m-1之间
   • 哈希函数计算出来的地址能均匀分布在整个空间中
   • 哈希函数应该比较简单如果很复杂的话那么计算成本也是很高的

因此我们这个时候来介绍一下哈希函数。

哈希函数

这里跳过可以去网上查一下数学问题。我们到时候模拟实现采用的是除留余数法。

除留余数法–(常用)

设散列表中允许的地址数为m取一个不大于m但最接近或者等于m的质数p作为除数按照哈希函数Hash(key) = key% p(p<=m),将关键码转换成哈希地址哈希函数设计的越精妙产生哈希冲突的可能性就比较低但是无法避免那么我们如果真的遇到了哈希冲突应该怎么解决呢

哈希冲突解决

解决哈希冲突的两种常见方法是闭散列和开散列

闭散列

闭散列也叫开放定址法当发生哈希冲突时如果哈希表未被装满说明在哈希表中必然还有空位置那

么可以把key存放到冲突位置中的下一个空位置中去。那如何寻找下一个空位置呢

线性探测

线性探测从发生冲突的位置开始依次向后探测直到寻找到下一个空位为止。

• 插入

  • 通过哈希函数获取待插入元素在哈希表中的位置
  • 如何该位置中没有元素则直接插入新元素如果该位置中有元素发生哈希冲突使用线性探测找到下一个空位置插入新元素。

• 删除

  采用闭散列处理哈希冲突时不能随便物理删除哈希表中的已有元素若直接删除元素会影响其他元素的搜索。例如删除了元素4那么我的44其实就找不到了。因为我们应该使用伪删除法来删除一个元素。

  	enum Status
  	{
  		EXIST, // 位置已经有元素
  		EMPTY, // 位置为空
  		DELETE // 删除
  	};
  

线性探测的实现

先给出几个需要注意的点

• 注意我的取模不能模容量要模大小

  	size_t i = kv.first % _tables.size();
  	// 不能取模capacity
  	// size_t i = kv.first % _tables.capacity();
  

  原因是如果你模容量的话可能会出现内存访问越界的问题。

• 思考哈希表什么情况下进行扩容如何扩容

  首先回答一个问题为什么要进行扩容原因很简答

  1. 数据量太多了哈希表放不下了
  2. 你可以想象一下在同一片空间下数据越来越多是不是发生哈希冲突的概率会越来越大那么再向一下线性探测的过程如果哈希冲突很严重的话就相当于遍历了哈希表效率严重下降。

  那么什么时候进行扩容呢

  1. 散列表的载荷因子定义为α = 填入表中的元素个数 / 散列表的长。度[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传α是散列表装满程度的标志因子。由于表长是定值[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传α与“填入表中的元素个数”成正比所以α越大表明填入表中的元素越多产生冲突的可能性就越大反之α越小标明填入表中的元素越少产生冲突的可能性就越小。实际上散列表的平均查找长度是载荷因子[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传α的函数只是不同处理冲突的方法有不同的函数。

     对于开放定址法荷载因子是特别重要因素应严格限制在0.7-0.8以下。超过0.8查表时的CPU缓存不命中cache missing按照指数曲线上升。因此一些采用开放定址法的hash库如Java的系统库限制了荷载因子为0.75超过此值将resize散列表。

#pragma once
#include <vector>
#include <string>

using namespace std;


template<class K>
struct Hash
{
	size_t operator() (const K& key)
	{
		return key;
	}
};

// 如果K是stribg类型会走这个特化版本
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;
	};

	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;
				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> 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;
			// 不能取模capacity
			// size_t i = kv.first % _tables.capacity();

			// 线性探测
			while (_tables[index]._status == EXIST)
			{
				i++;
				index = start + i * i;
				index %= _tables.size();
			}
			_tables[index]._kv = kv;
			_tables[index]._status = EXIST;
			++_n;
			return true;
		}
	private:
		vector<HashData<K, V>> _tables;
		size_t _n; // 有效数据的个数
	};


	struct Date
	{
	public:
		int a = 1;
	};

	struct HashDate
	{
		size_t operator() (const Date* d)
		{
			// ...
		}
	};

	void TestHashTable1()
	{
		HashTable<string, int> ht;
		ht.Insert(make_pair("lxy", 12));
		cout << ht.Find("lxy") << endl;
		ht.Erase("lxy");
		cout << ht.Find("lxy") << endl;

		// 当key是一个定义类型时需要配置这个仿函数将key转换成整形
		HashTable<Date, string, HashDate> htds;
	}
}

线性探测其实缺点很大一旦发生哈希冲突所有的冲突连在一起容易产生数据堆积。因此我们可以进行一次优化使用二次探测。

二次探测

线性探测是每次遇到重复的就找下一个位置而二次探测就是遇到重复的话就跳过一段距离避免数据的堆积。

线性探测的缺陷是产生冲突的数据堆积在一块这与其找下一个空位置有关系因为找空位置的方式就

是挨着往后逐个去找因此二次探测为了避免该问题找下一个空位置的方法为 Hi = (H0 + i^2) % m。其中i = 1,2,3…是通过散列函数Hash(x)对元素的关键码key进行计算得到的位置m是表的大小。如果要插入44产生冲突使用解决后的情况为

但是二次探测也有很大的缺点就是每次跳跃平方的话在负载因子到达一定程度的时候你可能跳几万次都跳不到空位因此如果是二次探测的话要严格控制负载因子。

研究表明甚至要到达0.5。对空间的浪费是很大的。于是我们有了一个更好的解决方案也就是开散列。

顺便放一个代码我们只需要改一个地方就可以了就是扩容的时候控制一下即可。

开散列

开散列法又叫链地址法(开链法)首先对关键码集合用散列函数计算散列地址具有相同地址的关键码归于同一子集合每一个子集合称为一个桶各个桶中的元素通过一个单链表链接起来各链表的头结点存储在哈希表中。

这个位置我们可以称作是哈希桶每一个哈希桶里面存放的是发生了哈希冲突的元素。

极端场景是一个哈希桶内冲突的元素太多了链表太长因此当一个桶长度超过一定的值之后由链表转换为红黑树代码实现就链表吧红黑树太难了。

关于开散列的负载因子实际上是1也就是每一次插入的时候都会发生哈希冲突的时候再扩容比较好。因为它不会像闭散列一样发生堆积。

扩容的代价是很大的所以能少扩容负载因子就尽量大一点要做权衡。如果数据量大到离谱例如一个亿每次扩容都可能会造成一定的性能抖动。

那么关于字符串放入哈希表使用字符串哈希算法就可以了在网上搜几个就可以。然后C++使用仿函数实现即可。

还有一个需要注意的点就是研究表明我们每次最好模一个素数这样可以减小哈希冲突的概率。

因此使用素数表的方法来实现STL也是这么做的。

代码实现

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* cur = _tables[index];
			Node* prev = nullptr;
			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;
				}
			}
		}

		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];
		}

		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;
			}
			// 负载因子 == 1 时扩容
			if (_n == _tables.size())
			{
				size_t newSize = GetNextPrime(_tables.size());
				vector<Node*> newTables;
				newTables.resize(newSize);
				for (size_t i = 0; i < _tables.size(); i++)
				{
					HashFunc hf;
					Node* cur = _tables[i];
					while (cur)
					{
						Node* next = cur->_next;
						size_t index = hf(cur->_kv.first) % newTables.size();
						// 头插
						cur->_next = newTables[index];
						cur = next;
					}
					_tables[i] = nullptr;
				}
				newTables.swap(_tables);
			}

			HashFunc hf;
			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<Node*> _tables;
		size_t _n; // 有效数据的个数
	};

	void TestHashTable()
	{
		int a[] = { 4, 24, 14, 7,37,37,57,67,34,14,54 };
		HashTable<int, int> ht;
		for (auto e : a)
		{
			ht.Insert(make_pair(e, e));
		}
	}
}

哈希的应用

位图

海量数据处理面试题1

我们从一道面试题来引入位图

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

中。【腾讯】

1. 首先分析题目我的脑子里面的第一想法是遍历时间复杂度O(N)然后进行优化先排序时间复杂度O(NlogN)然后利用二分查找logN。d
2. 仔细一想哎40亿个数字内存放不下哎只能用其他的方式。

这里可以使用位图。

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

#pragma once

#include <vector>

using namespace std;

namespace bit
{
	template<size_t N>
	class bit_set
	{
	public:
		bit_set()
		{
			_bits.resize(N / 8 + 1);
		}

		// 设置为1
		void set(size_t x)
		{
			// 这个i算的是它在第几个char里面
			size_t i = x / 8;
			// 这个j算的是它是第几个位
			size_t j = x % 8;
			_bits[i] |= (1 << j);
		}

		// 清理为0
		void reset(size_t x)
		{
			size_t i = x / 8;
			size_t j = x % 8; 
			_bits[i] &= (~(1 << j));
		}

		// 探测这个位是否是1
		bool test(size_t x)
		{
			size_t i = x / 8;
			size_t j = x % 8;
			return _bits[i] & (1 << j);
		}
	private:
		vector<char> _bits;
		// vector<int> _bits;
	};

	void test_bit_set()
	{
		bit_set<0xffffffff> bs;
	}
}

海量数据处理面试题2

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

首先分析一下题目

数字出现的频率可以分为三种情况

1. 出现0次
2. 出现1次
3. 出现2次以及以上

思路是改造位图结构以前是一个比特位标识一个值现在改成两个比特位标识一个值。

定义两个比特位图

bit_set<N> _bs1;
bit_set<N> _bs2;

这两个比特位图可以标识以下几种状态

• 00 数字出现了0次
• 01 数字出现了1次
• 10 数字出现了2次
• 11 数字出现了3次

这样用两个比特位图就可以找到只出现一次的整数了。

#pragma once

#include <vector>

using namespace std;

namespace bit
{
	template<size_t N>
	class bit_set
	{
	public:
		bit_set()
		{
			_bits.resize(N / 8 + 1);
		}

		// 设置为1
		void set(size_t x)
		{
			// 这个i算的是它在第几个char里面
			size_t i = x / 8;
			// 这个j算的是它是第几个位
			size_t j = x % 8;
			_bits[i] |= (1 << j);
		}

		// 清理为0
		void reset(size_t x)
		{
			size_t i = x / 8;
			size_t j = x % 8; 
			_bits[i] &= (~(1 << j));
		}

		// 探测这个位是否是1
		bool test(size_t x)
		{
			size_t i = x / 8;
			size_t j = x % 8;
			return _bits[i] & (1 << j);
		}
	private:
		vector<char> _bits;
		// vector<int> _bits;
	};

	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);
			}
			// 11 表示以及出现2次或者以上不用处理			
		}

		void PrintOnceNum()
		{
			for (size_t i = 0; i < N; i++)
			{
				if (!_bs1.test(i) && _bs2.test(i)) // 01
				{
					cout << i << endl;
				}
			}
		}
	private:
		// 然后设置的到bs1一旦设置到bs1就已经说明完成了两次了
		bit_set<N> _bs1;
		// 第一次设置到bs2
		bit_set<N> _bs2;
	};

	void test_bit_set()
	{
		bit_set<0xffffffff> bs;
	}

	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();
	}
}

海量数据处理面试题3

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

思路1把一个文件中的整数set到一个比特位图读取第二个文件中的整数判断在不在位图。在就是交际不在就不是交集。

这个思路看起来可以但是实际上有一个很大的缺点

int a1[] = {5, 30, 1, 99, 10};
int a2[] = {8, 10, 11, 9, 30, 10, 30};

8不在。10在。11不在。9不在。30在。10在。30在。最终结果。

10 30 10 30

还要加入到set进行去重。可行但是还是不完美。

思路2把文件set到一个位图然后同时再set到另外一个位图然后把两个位图相与与完是1的就是交集。

海量数据处理面试题4

1个文件有100亿个int1G内存设计算法找到出现次数不能超过2次的所有整数。

两个位图即可跟第二题差不多。

总结一下

1. 快速查找某一个数据是否在一个集合中
2. 排序
3. 求两个集合的交集并集
4. 操作系统中磁盘块标记
5. 。。。。

布隆过滤器

布隆过滤器的提出

我们在使用新闻客户端看新闻时它会给我们不停地推荐新的内容它每次推荐时要去重去掉那些已经看

过的内容。问题来了新闻客户端推荐系统如何实现推送去重的 用服务器记录了用户看过的所有历史记

录当推荐系统推荐新闻时会从每个用户的历史记录里进行筛选过滤掉那些已经存在的记录。 如何快速查

找呢Tips推荐系统是可以有容错性的所以这是一种解决方案

1. 用哈希表存储用户记录缺点浪费空间
2. 用位图存储用户记录缺点不能处理哈希冲突
3. 将哈希与位图结合即布隆过滤器

特点

一句话解决

本质上布隆过滤器是一种数据结构比较巧妙的概率型数据结构probabilistic data structure特点是高效地插入和查询可以用来告诉你 “某样东西一定不存在或者可能存在”。

布隆过滤器是可以过滤字符串的首先我们使用字符串哈希算法把字符串转换成一个整数。

然后把这个整数映射到比特位图里面其实这就是布隆过滤器。

如果比特位是0的话那么说明这个位置对应的字符串一定不存在如果比特位是1的话代码可能存在因为我们前面已经了解到了哈希冲突是无法避免的。

既然无法避免我们就需要去尽可能规避。

1. 首先选择优秀的字符串哈希函数
2. 其次使用多个字符串哈希函数同时进行映射减少冲突的概率。
3. 开的空间尽可能提升负载因子尽可能小

例如这里是3个哈希函数的例子。

插入

算3个哈希插入。

查找

如果我找到了有一个比特位为0那么我可以百分百说没有这个字符串。如果我找到了3个比特位都是1。那么这个值因为哈希冲突的原因可能不存在就是这么一个道理。

删除

不能支持删除工作因为在删除一个元素的时候可能会影响其他元素。

比如删除上图中"tencent"元素如果直接将该元素所对应的二进制比特位置0“baidu”元素也被删除了

因为这两个元素在多个哈希函数计算出的比特位上刚好有重叠。

一种支持删除的方法将布隆过滤器中的每个比特位扩展成一个小的计数器插入元素时给k个计数器(k个哈

希函数计算出的哈希地址)加一删除元素时给k个计数器减一通过多占用几倍存储空间的代价来增加删

除操作。这相当于是引用计数吧。但是存在计数回绕问题。所以这个计数器取多少是一个玄学问题。

代码实现

#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 *= 31;
			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,// 这个X越大空间分配越多但是于此同时误判率是越低的
	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;
		cout << len << endl;
		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> bits;
	bits.Set("我的名字是李鑫阳");
}

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 url = "https://www.cnblogs.com/-clq/archive/2012/05/31/2528153.html";
		url += std::to_string(1234 + i);
		v1.push_back(url);
	}

	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 url = "https://www.cnblogs.com/-clq/archive/2012/05/31/2528153.html";
		url += std::to_string(6789 + 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";
		//std::string url = "https://www.baidu.com/s?wd=ln2&rsv_spt=1&rsv_iqid=0xc1c7784f000040b1&issp=1&f=8&rsv_bp=1&rsv_idx=2&ie=utf-8&tn=baiduhome_pg&rsv_dl=tb&rsv_enter=1&rsv_sug3=8&rsv_sug1=7&rsv_sug7=100&rsv_sug2=0&rsv_btype=i&prefixsug=ln2&rsp=5&inputT=4576&rsv_sug4=5211";
		//std::string url = "https://zhidao.baidu.com/question/1945717405689377028.html?fr=iks&word=ln2&ie=gbk&dyTabStr=MCw0LDMsMiw2LDEsNSw3LDgsOQ==";
		std::string url = "https://www.cnblogs.com/-clq/archive/2012/01/31/2333247.html";
		url += std::to_string(rand());
		v3.push_back(url);
	}

	size_t n3 = 0;
	for (auto& str : v3)
	{
		if (bf.Test(str))
		{
			++n3;
		}
	}
	cout << "不相似字符串误判率:" << (double)n3 / (double)N << endl;

}

应用场景

• 规避缓存击穿
• 垃圾邮件判断
• 。。。数据量大节约空间允许误判等场景

海量数据面试题5

给两个文件分别有100亿个query我们只有1G内存如何找到两个文件交集分别给出精确算法和近似算法

近似算法使用布隆过滤器即可。但是存在误判。

如果要给出精确算法的话那么我们就得使用哈希切分思想了。

哈希切分

首先分析一下内存1个G内存1个query大概10字节。100亿个query大概100G左右。那么我们切分成200个小文件即可。

我们把两个文件命名为A号文件和B号文件。

首先在A号文件中读取queryi = BKRDHash(query) % 200。这个quert就进入Ai号小文件。B同理。

我们有结论**A和B中相同的query一定进入编号相同的小文件。**这是由哈希的性质决定的因为哈希一样的query计算出来的i是相同的。

所以我们查找的时候只需要把Ai号和Bi号文件加载进入内存然后查找就可以了相同的query必定是相同的字符串里面。

海量数据面试题6

给一个超过100G大小的log file, log中存着IP地址, 设计算法找到出现次数最多的IP地址 与上题条件相同如何找到top K的IP如何直接用Linux系统命令实现

答使用哈希切分这样相同IP的一定进入相同文件然后使用小根堆来以O(logN)来统计出现次数最多的IP地址。

步骤如下

• Hash分桶法
• 将100G文件分成1000份将每个IP地址映射到相应文件中file_id = hash(ip) % 1000
• 在每个文件中分别求出最高频的IP再合并 Hash分桶法
• 使用Hash分桶法把数据分发到不同文件
• 各个文件分别统计top K
• 最后Top K汇总
• Linux命令假设top 10sort log_file | uniq -c | sort -nr k1,1 | head -10

拓展一致性哈希算法

我写过博客可以看一看

https://blog.csdn.net/qq_61039408/article/details/128697332?spm=1001.2014.3001.5501