1. AI技术聚合首页
  2. IT

hash应用

青葱年少 • • IT • 阅读 38

目录

一、位图

1.1、引出位图

1.2、位图的概念

1.3、位图的应用

1.4、位图模拟实现

二、布隆过滤器

2.1、什么是布隆过滤器

2.2、布隆过滤器应用的场景

2.3、布隆过滤器的原理

2.4、布隆过滤器的查找

2.5、布隆过滤器的插入

2.6、布隆过滤器的删除

2.7、布隆过滤器的优缺点

2.8、布隆过滤器的模拟实现

一、位图

1.1、引出位图

我们在了解位图之前，前看一道题：

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

对于这道题,我们有两个思路:
1、内存内查找: 面对40亿个无符号整数,我们可以使用搜索树和哈希表,时间复杂度也就为O(n),因为搜索树不仅存储数据,还要存储颜色,parent,child指针等,哈希表还要存储迭代器,size等内置成员,进而导致内存存不下.

2、文件内查找:排序 + 二分查找,时间复杂度为0(log2),将40亿个数据保存在文件中，在进行排序。效率更低。。。

3、位图。unsigned int最大值是42亿多，而这里的40亿个数据都是不重复的，我们可以考虑使用一个32位的位图对这些数据映射（值是多少就映射在对应的位置，占用的内存不超过2G），将要查找的数据进行判断即可。

1.2、位图的概念

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

在上题中,40亿的无符号整型的范围为:0–4294967295,在开辟位图空间时,我们不是根据数据的个数在位图上映射的,而是根据数据的大小映射在位图上.所以,我们要开2^32-1的比特位大小的空间,让所有无符号整型数据都能映射在位图上.

1.3、位图的应用

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

2: 排序 + 去重 . ( 根据位图性质,哈希函数映射原理)

3: 求两个集合的交集,并集等.

4: 操作系统磁块标记.

1.4、位图模拟实现

#pragma once

#include <vector>
#include <string>
#include <time.h>

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:
	vector<char> _bits;
};

void test_bitset1()
{
	bitset<100> bs;
	bs.set(10);
	bs.set(11);
	bs.set(15);
	cout << bs.test(10) << endl;
	cout << bs.test(15) << endl;

	bs.reset(10);

	cout << bs.test(10) << endl;
	cout << bs.test(15) << endl;

	bs.reset(10);
	bs.reset(15);

	cout << bs.test(10) << endl;
	cout << bs.test(15) << endl;
}

void test_bitset2()
{
	//bitset<-1> bs1;
	bitset<0xFFFFFFFF> bs1;
}

template<size_t N>
class twobitset
{
public:
	void set(size_t x)
	{
		// 00 -> 01
		if (_bs1.test(x) == false
		&& _bs2.test(x) == false)
		{
			_bs2.set(x);
		}
		else if (_bs1.test(x) == false
			&& _bs2.test(x) == true)
		{
		// 01 -> 10
			_bs1.set(x);
			_bs2.reset(x);
		}
		// 10
	}

	void Print()
	{
		for (size_t i = 0; i < N; ++i)
		{
			if (_bs2.test(i))
			{
				cout << i << endl;
			}
		}
	}

public:
	bitset<N> _bs1;
	bitset<N> _bs2;
};

二、布隆过滤器

2.1、什么是布隆过滤器

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

                          

2.2、布隆过滤器应用的场景

布隆过滤器可以告诉我们 “某样东西一定不存在或者可能存在”，也就是说布隆过滤器说这个数不存在则一定不存，布隆过滤器说这个数存在可能不存在（误判，后续会讲），**利用这个判断是否存在的特点可以做很多有趣的事情。

  1. 网络爬虫：在爬取网页时，可以使用布隆过滤器来过滤掉已经爬取过的网页，避免重复爬取。

  2. 垃圾邮件过滤：布隆过滤器可以用来判断一封邮件是否是垃圾邮件，从而进行过滤。

  3. URL去重：在爬虫或者搜索引擎中，经常需要对URL进行去重操作，布隆过滤器可以高效地判断一个URL是否已经被处理过。

  4. 缓存穿透问题：布隆过滤器可以用来解决缓存穿透问题，即某个请求的数据不存在于缓存中，但是频繁地访问会导致缓存服务器压力过大。

  5. 数据库查询优化：在数据库查询中，可以使用布隆过滤器来过滤掉不存在于数据库中的数据，从而减少不必要的查询开销。

2.3、布隆过滤器的原理

数据结构：布隆过滤器它实际上是一个很长的二进制向量和一系列随机映射函数。

以Redis中的布隆过滤器实现为例，Redis中的布隆过滤器底层是一个大型位数组（二进制数组）+多个无偏hash函数。

一个大型位数组（二进制数组）：

多个无偏hash函数：

无偏hash函数就是能把元素的hash值计算的比较均匀的hash函数，能使得计算后的元素下标比较均匀的映射到位数组中。

如下就是一个简单的布隆过滤器示意图，其中k1、k2代表增加的元素，a、b、c即为无偏hash函数，最下层则为二进制数组。

在布隆过滤器增加元素之前，首先需要初始化布隆过滤器的空间，也就是上面说的二进制数组，除此之外还需要计算无偏hash函数的个数。布隆过滤器提供了两个参数，分别是预计加入元素的大小n，运行的错误率f。布隆过滤器中有算法根据这两个参数会计算出二进制数组的大小l，以及无偏hash函数的个数k。

  • 错误率越低，位数组越长，控件占用较大
  • 错误率越低，无偏hash函数越多，计算耗时较长

2.4、布隆过滤器的查找

       布隆过滤器的思想是将一个元素用多个哈希函数映射到一个位图中，因此被映射到的位置的比特 位一定为1。所以可以按照以下方式进行查找：分别计算每个哈希值对应的比特位置存储的是否为 零，只要有一个为零，代表该元素一定不在哈希表中，否则可能在哈希表中。      注意：布隆过滤器如果说某个元素不存在时，该元素一定不存在，如果该元素存在时，该元素可 能存在，因为有些哈希函数存在一定的误判。      比如：在布隆过滤器中查找”alibaba”时，假设3个哈希函数计算的哈希值为：1、3、7，刚好和其 他元素的比特位重叠，此时布隆过滤器告诉该元素存在，但实该元素是不存在的

2.5、布隆过滤器的插入

往布隆过滤器增加元素，添加的key需要根据k个无偏hash函数计算得到多个hash值，然后对数组长度进行取模得到数组下标的位置，然后将对应数组下标的位置的值置为1

  • 通过k个无偏hash函数计算得到k个hash值
  • 依次取模数组长度，得到数组索引
  • 将计算得到的数组索引下标位置数据修改为1

例如：向布隆过滤器中插入：“baidu”

2.6、布隆过滤器的删除

布隆过滤器不能直接支持删除工作，因为在删除一个元素时，可能会影响其他元素。 比如：删除上图中”tencent”元素，如果直接将该元素所对应的二进制比特位置0，“baidu”元素也 被删除了，因为这两个元素在多个哈希函数计算出的比特位上刚好有重叠。 一种支持删除的方法：将布隆过滤器中的每个比特位扩展成一个小的计数器，插入元素时给k个计 数器(k个哈希函数计算出的哈希地址)加一，删除元素时，给k个计数器减一，通过多占用几倍存储 空间的代价来增加删除操作。 缺陷： 1. 无法确认元素是否真正在布隆过滤器中 2. 存在计数回绕

2.7、布隆过滤器的优缺点

1、优点：

1. 增加和查询元素的时间复杂度为:O(K), (K为哈希函数的个数，一般比较小)，与数据量大小无关 2. 哈希函数相互之间没有关系，方便硬件并行运算 3. 布隆过滤器不需要存储元素本身，在某些对保密要求比较严格的场合有很大优势 4. 在能够承受一定的误判时，布隆过滤器比其他数据结构有这很大的空间优势 5. 数据量很大时，布隆过滤器可以表示全集，其他数据结构不能 6. 使用同一组散列函数的布隆过滤器可以进行交、并、差运算

2、缺点：

1. 有误判率，即存在假阳性(False Position)，即不能准确判断元素是否在集合中(补救方法：再 建立一个白名单，存储可能会误判的数据) 2. 不能获取元素本身 3. 一般情况下不能从布隆过滤器中删除元素 4. 如果采用计数方式删除，可能会存在计数回绕问题

2.8、布隆过滤器的模拟实现

struct BKDRHash
{
	size_t operator()(const string& s)
	{
		size_t hash = 0;
		for (auto ch : s)
		{
			hash += ch;
			hash *= 31;
		}

		return hash;
	}
};

struct APHash
{
	size_t operator()(const string& s)
	{
		size_t hash = 0;
		for (long i = 0; i < s.size(); i++)
		{
			size_t ch = s[i];
			if ((i & 1) == 0)
			{
				hash ^= ((hash << 7) ^ ch ^ (hash >> 3));
			}
			else
			{
				hash ^= (~((hash << 11) ^ ch ^ (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;
	}
};

// N最多会插入key数据的个数
template<size_t N,
class K = string,
class Hash1 = BKDRHash,
class Hash2 = APHash,
class Hash3 = DJBHash>
class BloomFilter
{
public:
	void set(const K& key)
	{
		size_t len = N*_X;
		size_t hash1 = Hash1()(key) % len;
		_bs.set(hash1);

		size_t hash2 = Hash2()(key) % len;
		_bs.set(hash2);

		size_t hash3 = Hash3()(key) % len;
		_bs.set(hash3);

		//cout << hash1 << " " << hash2 << " " << hash3 << " " << endl << endl;
	 }

	bool test(const K& key)
	{
		size_t len = N*_X;

		size_t hash1 = Hash1()(key) % len;
		if (!_bs.test(hash1))
		{
			return false;
		}

		size_t hash2 = Hash2()(key) % len;
		if (!_bs.test(hash2))
		{
			return false;
		}

		size_t hash3 = Hash3()(key) % len;
		if (!_bs.test(hash3))
		{
			return false;
		}

		// 在      不准确的，存在误判
		// 不在    准确的

		return true;
	}
private:
	static const size_t _X = 6;
	bitset<N*_X> _bs;
};

版权声明：本文为博主作者：#欲速则不达#原创文章，版权归属原作者，如果侵权，请联系我们删除！

原文链接：https://blog.csdn.net/m0_69323023/article/details/135707944

共计人评分，平均分

到目前为止还没有投票！成为第一位评论此文章。

赞 (0)
青葱年少的头像青葱年少普通用户
0
上一篇 2024年2月19日
下一篇 2024年2月19日

相关推荐