当前位置：首页 > news >正文

沈阳网站设计营销型昆明百度推广开户费用

news 2025/7/7 1:01:53

沈阳网站设计营销型,昆明百度推广开户费用,网站cms大全,死链接对网站的影响目录一、位图 1、位图概念 2、位图实现 2.1、位图结构 2.2、比特位置1 2.3、比特位置0 2.4、检测位图中比特位 3、位图例题 3.1、找到只出现一次的整数 3.2、找到两个文件交集 3.3、找到出现次数不超过2次的所有整数二、布隆过滤器 1、布隆过滤器提出 2、布隆过…

一、位图

1、位图概念

2、位图实现

2.1、位图结构

2.2、比特位置1

2.3、比特位置0

2.4、检测位图中比特位

3、位图例题

3.1、找到只出现一次的整数

3.2、找到两个文件交集

3.3、找到出现次数不超过2次的所有整数

二、布隆过滤器

1、布隆过滤器提出

2、布隆过滤器概念

3、布隆过滤器实现

3.1、布隆过滤器的插入

3.2、布隆过滤器的查找

3.3、布隆过滤器删除

4、布隆过滤器例题

4.1、找到两个存贮query的文件的交集

4.2、哈希切割

一、位图

1、位图概念

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

位图的优点：

速度快
节省空间

位图的缺点：

只能映射整型，其他类型如：浮点数、string等等不能存储映射。

2、位图实现

2.1、位图结构

位图类的结构如下：

template<size_t N>
class bitset
{
public:bitset(){_bits.resize(N / 8 + 1, 0);}//将某个比特位置1void set(size_t x){}//将某个比特位置0void reset(size_t x){}//检查位图中某个比特位是否为1bool test(size_t x){}private:vector<char> _bits;
};

2.2、比特位置1

实现代码：

	void set(size_t x){size_t i = x / 8;size_t j = x % 8;_bits[i] |= (1 << j);}

用除法计算 x 映射的位在数组的第 i 个 char 类型内。用取模计算 x 映射的位在第 i 个 char 类型的第 j 个比特位。然后用按位或运算把指定比特位置1。

需要注意的是在进行按位或运算时，使用的是 1 左移 j 位，而不是右移。这是因为在我们人类的主观认识上，数位的排列是下面这样的：

但实际上，在计算机的虚拟层储存逻辑上，数位的保存是这样的：

我们所说的左移与右移，并不是向左移动或者向右移动，而是向高位移动与向低位移动。因此为了找到目标位置，需要使用左移，而不是右移。

2.3、比特位置0

实现代码：

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

用除法计算 x 映射的位在数组的第 i 个 char 类型内。用取模计算 x 映射的位在第 i 个 char 类型的第 j 个比特位。然后用按位非与运算把指定比特位置1。

2.4、检测位图中比特位

实现代码：

	bool test(size_t x){size_t i = x / 8;size_t j = x % 8;return _bits[i] & (1 << j);}

3、位图例题

3.1、找到只出现一次的整数

设置状态：出现 0 次，状态是 00 。出现 1 次，状态是 01 。出现 2 次及以上，状态是 10 。

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

测试结果如下：

3.2、找到两个文件交集

方法一：把其中一个文件的值读取到位图中，再读取另一个文件，判断在不在上面的位图中，在就是交集，取出该值，并把对应位图置0。

方法二：创建两个位图，读取文件1的数据映射到位图1，读取文件2的数据映射到位图2。然后让位图1与位图2按位与。最终结果是交集。

3.3、找到出现次数不超过2次的所有整数

设置状态：出现 0 次，状态是 00 。出现 1 次，状态是 01 。出现 2 次，状态是 10 。出现 3 次及以上，状态是 11 。

实现代码与 3.1 中类似。

二、布隆过滤器

1、布隆过滤器提出

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

用哈希表存储用户记录，缺点：浪费空间。
用位图存储用户记录，缺点：位图一般只能处理整形，如果内容编号是字符串，就无法处理了。
将哈希与位图结合，即布隆过滤器。

2、布隆过滤器概念

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

布隆过滤器可以降低冲突的概率。一个值映射到一个位置，容易误判，映射到多个位置，就可以降低误判率。

布隆过滤器的优点：

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

布隆过滤器的缺点：

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

3、布隆过滤器实现

3.1、布隆过滤器的插入

向布隆过滤器中插入："baidu"：

向布隆过滤器中插入："tencent"：

实现代码：

struct BKDRHash
{size_t operator()(const string& s){size_t hash = 0;for (auto ch : s){hash += ch;hash *= 31;}return hash;}
};struct DJBHash
{size_t operator()(const string& s){size_t hash = 5381;for (auto ch : s){hash += (hash << 5) + ch;}return hash;}
};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;}
};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);}
private:static const size_t _X = 4; // 布隆过滤器的长度与数据数量的倍数关系bitset<N*_X> _bs;  //这样可以有效的减少不同数据间的冲突
};

3.2、布隆过滤器的查找

布隆过滤器的思想是将一个元素用多个哈希函数映射到一个位图中，因此被映射到的位置的比特位一定为1。所以可以按照以下方式进行查找：分别计算每个哈希值对应的比特位置存储的是否为零，只要有一个为零，代表该元素一定不在哈希表中，否则可能在哈希表中。

实现代码：

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;//依然存在误判，有可能把不在的判断成在
}

需要注意的是，即使使用了三个哈希函数进行判断，仍然存在误判的可能性。如果判断该数据不存在，则该数据一定不存在。如果判断该数据存在，则该数据有一定的可能性其实不存在。

因此，布隆过滤器只能运用于能够容忍误判的场景，比如视频推送等等。而对于一些不容忍误判的场景下，布隆过滤器也有相应的解决方法：如果判断出数据存在，就到数据库中进行二次确认，依然存在就返回存在，不存在就返回不存在。

哈希函数个数，代表一个值映射几个位，哈希函数越多，误判率越低，但是哈希函数越多，平均占的空间就越大。