位图
概念
位图: 所谓位图,就是用每一位来存放某种状态,适用于海量数据,数据无重复的场景。通常是用来判断某个数据存不存在的。
适用场景: 如果我们需要对大量的数据进行处理,判断该数据在不在,比如40亿个整形数据,如果我们用unordered_set来存放这些数据,大约需要占用16G的内存,显然这是不妥的,如果我们选择用一个数据结构,该数据结构可以存放40亿个数据在不在的状态,也就是开42亿个比特位大小的空间(整形数据总共是约42亿个),约500M,这样就可以将数据存下去了。
如下图: (其中1代表在,0代表不在,所以1,2,5,7这几个元素是在的)
![](/i/l/?n=23&i=blog/2976263/202212/2976263-20221230110558484-596337638.png)
原理
补充知识
什么是高地址、低地址?
![](/i/l/?n=23&i=blog/2976263/202212/2976263-20221230110611453-376852870.png)
什么是数据的低位、高位?
![](/i/l/?n=23&i=blog/2976263/202212/2976263-20221230110635353-1243851270.png)
小端模式
数据的低位放在低地址空间,数据的高位放在高地址空间
实例讲解
例子1:存放二进制数:1011-0100-1111-0110-1000-1100-0001-0101
注意注意:我们在存放的时候是以一个存储单元为单位来存放,存储单元内部不需要再转变顺序啦!
就例如下面的低位0001-0101存放在0号地址,我们不需要把它变成1010-1000,不需要!!不需要!!
![](/i/l/?n=23&i=blog/2976263/202212/2976263-20221230110653694-954161531.png)
读取数据:注意一定一定是从低地址读起!!!我们知道这是小端存储,所以在读出来的时候会从低位开始放!!!
![](/i/l/?n=23&i=blog/2976263/202212/2976263-20221230110720014-1043912155.png)
例子2:存放十六进制数:2AB93584FE1C
十六进制数每一位转化为二进制就是4位:2对应0010,A对应1010,以此类推。所以在存放的时候两个十六进制位就占用一个存储单元
![](/i/l/?n=23&i=blog/2976263/202212/2976263-20221230110745661-1616275099.png)
大端模式
数据的高位放在低地址空间,数据的低位放在高地址空间
实例演示:
例子1:存放二进制数:1011-0100-1111-0110-1000-1100-0001-0101
![](/i/l/?n=23&i=blog/2976263/202212/2976263-20221230110758527-1826312686.png)
读取数据:注意仍然是从低地址开始读,我们知道这是大端模式,当我们从0号地址读到1011-0100时,我们知道它是高位,所以放到高位的位置上去
![](/i/l/?n=23&i=blog/2976263/202212/2976263-20221230110811992-1641355390.png)
例子2:存放十六进制数:2AB93584FE1C
![](/i/l/?n=23&i=blog/2976263/202212/2976263-20221230110825794-1394675418.png)
读取数据:注意从低地址开始读取,读到的从高地址开始放!!!
![](/i/l/?n=23&i=blog/2976263/202212/2976263-20221230110839672-1933877531.png)
位图原理
位图中的每个数据单元都是一个bit位,这样子平时我们都要话32位4字节来存储数据,而现在我们只需要花1个字节就能”存储数据”,在空间上减少了约32倍的容量。例如40G的数据我们只要花1.3G来存储。但是我们平时操作的数据类型最小就是一个字节,我们不能直接对位进行操作,所以我们可以借助位运算来对数据进行操作。下面我们来看看数据在位图中是如何存储的
我们这里给出一个数组
int arr[] = {1,2,4,5,7,10,11,14,16,17,21,23,24,28,29,31};则我们只需要花1个字节来存这些数据
![](/i/l/?n=23&i=blog/2976263/202212/2976263-20221230110852891-695839275.png)
解释:我们目前很多的机器都是小端存储,也就是低地址存低位,一个整形数据中,第一个字节用来存储0-7的数字,第二个字节用来存储8-15的数字,第三个字节用来存储16-23的数字,第四个字节用来存储24-31的数字。我们来看看数字10是如何存储的。先通过模上32,取余还是10,然后再将4字节中第10个比特位置为1,则表示该数字出现过。由于我们的机器是小端存储,所以我们的每个比特位都是要从右边开始计算的
所以说我们只需要将对应的比特位置为1即可。但是如果我们要存储的数据很大呢?其实也很简单,我们可以定义一个数组,当做一个位图,如果该数字在0-31之间,我们就存储在0号下标的元素中进行操作,如果在32-63之间,则就在1号下标之间进行操作。计算下标我们可以通过模32来获得下标
实现
整体框架
在实现位图中,我们的成员变量只需要一个数组就可以实现。而这个数组有多我们要开多大呢?数组多开一个整形空间,就能多存32个数字,所以我们可以让用户提供一个准确的数,这个数是一个数据量,也是数的最大范围。我们可以通过该数模上32,就可以获得该数组的大小,但是0~31模上32为0,我们开0个空间那显然不合适,所以我们要开bitCount/32 + 1
个空间大小的数组
class bitset
{
public:
bitset(size_t bitCount)
:bitCount(bitCount)
{
//resize会将vector中的元素初始化为0
_bitset.resize(bitCount / 32 + 1);
}
private:
vector<int> _bitset;
int bitCount;// 开num比特位的空间
};
把某位置为1
分为三步:
- 计算出x对应的数组下标: 先确定这个数应该处在第几个数组中,也就是index=x/32
- 计算处x在对应数组中的比特位的位置: 通过把x对32取模,得到x在第index个整形的第pos个位置
- 将计算出来的比特位置为1:操作位,我们可以通过位运算来操作,可以先将1左移pos位后再和整数进行或运算
举例:假设pos=5,数据为10010011
- 将1进行左移5位==>100000
- 将数据和第一步计算出来的结果进行或运算----->10010011 | 100000 =10110011,此时我们就将指定位置置位1了
代码实现:
// 每个字节用0和1记录某个数字存在状态
// 把x所在的数据在位图的那一位变成1
void set(int x)
{
if (x > bitCount) return;
int index = x / 32;// x是第index个整数
int pos = x % 32;// x是第index个整数的第pos个位
_bitset[index] |= (1 << pos);
}
把某位置为0
分为两步:
- 找到那一位:和上面的方法一样
- 把这位设置为0:通过先将1进行左移pos位,然后取反,将结果再和原来数据进行与运算
举例:假设pos=5,数据为10110011
- 将1进行左移5位后并取反011111
- 将第一步计算出来的结果和数据进行与运算----->10110011 & 011111 = 10010011,删除成功
代码实现:
// 把x所在的数据在位图的那一位变成0
void reset(int x)
{
if (x > bitCount) return;
int index = x / 32;// x是第index个整数
int pos = x % 32;// x是滴index个整数的第pos个位
_bitset[index] &= ~(1 << pos);
}
判断某位是否为1
分为两步:
- 找到那一位: 和上面的方法一样
- 把这位设置为0:将数组下标为index的整数向右移pos位,然后再和1进行与运算,如果为1则表示存在,否则不存在
举例:pos=5,数据为10110011
- 将数据进行右移5位00000101
- 将第一步计算出来的结果和1进行与运算----->00000101 & 1 = 1,此时表示该数字存在,返回true
// 判断x是否存在
bool test(int x)
{
if (x > bitCount) return false;
int index = x / 32;// x是第index个整数
int pos = x % 32;// x是滴index个整数的第pos个位
return _bitset[index] & (1 << pos);
}
完整代码以及测试
#define _CRT_SECURE_NO_WARNINGS
#include<iostream> //引入头文件
#include<vector>
#include <string>
#include <new>
#include<algorithm>
using namespace std; //标准命名空间
class bitset
{
public:
bitset(size_t bitCount)
:bitCount(bitCount)
{
//resize会将vector中的元素初始化为0
_bitset.resize(bitCount / 32 + 1);
}
// 每个字节用0和1记录某个数字存在状态
// 把x所在的数据在位图的那一位变成1
void set(int x)
{
if (x > bitCount) return;
int index = x / 32;// x是第index个整数
int pos = x % 32;// x是第index个整数的第pos个位
_bitset[index] |= (1 << pos);
}
// 把x所在的数据在位图的那一位变成0
void reset(int x)
{
if (x > bitCount) return;
int index = x / 32;// x是第index个整数
int pos = x % 32;// x是滴index个整数的第pos个位
_bitset[index] &= ~(1 << pos);
}
// 判断x是否存在
bool test(int x)
{
if (x > bitCount) return false;
int index = x / 32;// x是第index个整数
int pos = x % 32;// x是滴index个整数的第pos个位
return _bitset[index] & (1 << pos);
}
private:
vector<int> _bitset;
int bitCount;// 开num比特位的空间
};
void TesstBitset1()
{
bitset bs(100);
bs.set(99);
bs.set(0);
bs.set(98);
bs.set(55);
bs.set(75);
bs.set(35);
;
bs.reset(99);
bs.reset(87);
for (size_t i = 0; i <= 100; ++i)
{
cout << i << ":" << bs.test(i) << " ";
if (i != 0 && i % 10 == 0)
cout << endl;
}
}
int main() {
TesstBitset1();
system("pause");
return EXIT_SUCCESS;
}
运行结果如下:
![](/i/l/?n=23&i=blog/2976263/202212/2976263-20221230110929700-213440982.png)
位图的应用
有以下几个:
- 快速查找某个数据是否在一个集合中
- 排序+去重
- 操作系统中磁盘的标记等
缺点: 只能处理整形数据
布隆过滤器
引入
我们在使用新闻客户端看新闻时,它会给我们不停地推荐新的内容,它每次推荐时要去重,去掉那些已经看过的内容。问题来了,新闻客户端推荐系统如何实现推送去重的? 用服务器记录了用户看过的所有历史记录,当推荐系统推荐新闻时会从每个用户的历史记录里进行筛选,过滤掉那些已经存在的记录。
如何快速查找?
- 哈希表: 用哈希表存储用户的历史记录。缺点: 空间消耗比较大
- 位图: 用位图存储用户的历史记录。 缺点: 位图一般只能处理整形,如果内容编号是字符串,就无法处理了。但我们可以使用一些哈希算法把字符串类型转换成整型,比如BKDR哈希算法,但是这里还存在一个问题。字符串的组合方式太多了,一个字符的取值有256种,一个数字只有10种,所以不可避免会出现哈希冲突
- 布隆过滤器: 将哈希表和位图结合使用。
概念
布隆过滤器是由布隆(Burton Howard Bloom)在1970年提出的一种紧凑的、比较巧妙的概率型数据结构,特点是高效地插入和查询
布隆过滤器其实就是位图的一个变形和延申,虽然无法避免哈希冲突,但我们可以想办法降低误判的概率;当一个数据映射到位图中时,布隆过滤器会用多个哈希函数映射到多个比特位,当判断一个数据是否在位图当中时,需要分别根据这些哈希函数计算出对应的比特位,比特位设置了代表着当前状态的默认值,设置为 1 则判定为该数据存在,这一点很类似于我们定义红黑数的节点颜色。
布隆过滤器使用多个哈希函数进行映射,目的就在于降低哈希冲突的概率,一个哈希函数产生冲突的概率可能比较大,但多个哈希函数同时产生冲突的概率可就没那么大了!
举个例子:针对值 “source” 和三个不同的哈希函数分别生成了哈希值 2、4、7
![](/i/l/?n=23&i=blog/2976263/202212/2976263-20221230110944362-531189567.png)
现在,如果我们要查询"source"这个字符串是否存在,就要判断位图中下标2,4,7对应的值是否均为1,若是,则说明此字符串“可能”存在。注意这里就可能出现误判了(下面介绍)
布隆过滤器误判
布隆过滤器是一个大型位图(bit数组或向量) + 多个无偏哈希函数
如果我们要映射一个值到布隆过滤器中,我们需要使用多个不同的哈希函数生成多个哈希值,并对每个生成的哈希值指向的 bit 位置 1,例如针对值 “source” 和三个不同的哈希函数分别生成了哈希值 2、4、7,则有下图
![](/i/l/?n=23&i=blog/2976263/202212/2976263-20221230110944362-531189567.png)
现在,如果我们要查询"source"这个字符串是否存在,就要判断位图中下标2,4,7对应的值是否均为1,若是,则说明此字符串“可能”存在。注意这里就可能出现误判了,至于为什么我们先再存一个字符串"create",假设哈希函数返回3,4,8,则对应的图如下:
![](/i/l/?n=23&i=blog/2976263/202212/2976263-20221230111006790-1257590834.png)
- 值得注意的是,4 这个 bit 位由于两个值的哈希函数都返回了这个 bit 位,因此它被覆盖了。现在我们如果想查询 “flower” 这个值是否存在,哈希函数返回了 2、5、8三个值,结果我们发现 5 这个 bit 位上的值为 0,说明没有任何一个值映射到这个 bit 位上,因此我们可以很确定地说 “flower” 这个值不存在。而当我们需要查询 “source” 这个值是否存在的话,那么哈希函数必然会返回 2、4、7,然后我们检查发现这三个 bit 位上的值均为 1,那么我们可以说 “source” 存在了么?答案是不可以,只能是 “source” 这个值可能存在(发生了误判)。
- 这是为什么呢?答案很简单,因为随着增加的值越来越多,被置为 1 的 bit 位也会越来越多,这样某个值 “taobao” 即使没有被存储过,但是万一哈希函数返回的三个 bit 位都被其他值置位了 1 ,那么程序还是会判断 “taobao” 这个值存在。像上面的字符串source,哈希函数返回的是2,4,7,可是先前的字符串create,哈希函数返回的是3,4,8,你怎么知道比特位4的值对应的是字符串source呢?我说它是字符串create的也没毛病吧,因此“source”可能存在。这就是误判出现的典型现象。
总结:布隆过滤器是无法解决误判的问题的,一个key通过多种哈希函数映射多个比特位只能说是降低误判的概率,但无法去除。
布隆过滤器优缺点
优点:
-
增加和查询元素的时间复杂度为:O(K), (K为哈希函数的个数,一般比较小),与数据量大小无关
-
哈希函数相互之间没有关系,方便硬件并行运算
-
布隆过滤器不需要存储元素本身,在某些对保密要求比较严格的场合有很大优势
-
在能够承受一定的误判时,布隆过滤器比其他数据结构有这很大的空间优势
-
数据量很大时,布隆过滤器可以表示全集,其他数据结构不能
-
使用同一组散列函数的布隆过滤器可以进行交、并、差运算
缺点:
- 有误判率,即存在假阳性(False Position),即不能准确判断元素是否在集合中(补救方法:再建立一个白名单,存储可能会误判的数据)
- 不能获取元素本身
- 一般情况下不能从布隆过滤器中删除元素
- 如果采用计数方式删除,可能会存在计数回绕问题
误判控制
- 很显然,过小的布隆过滤器很快所有的 bit 位均为 1,那么查询任何值都会返回“可能存在”,起不到过滤的目的了。布隆过滤器的长度会直接影响误报率,布隆过滤器越长其误报率越小。
- 另外,哈希函数的个数也需要权衡,个数越多则布隆过滤器 bit 位置位 1 的速度越快,且布隆过滤器的效率越低;但是如果太少的话,那我们的误报率会变高。
大佬在权衡过其中的关系后得出了一套比较得当的公式:
![](/i/l/?n=23&i=blog/2976263/202212/2976263-20221230111019720-905153345.png)
k 是哈希函数个数
m 为布隆过滤器长度
n为插入的元素个数
p为误判率
实现
整体框架
这里用到了上一篇博客中的位图实现,其中这里放置了3个哈希函数,用了映射不同的概率。
在这里完整代码bitset.h文件
#pragma once
#include<iostream> //引入头文件
#include<vector>
#include <string>
#include <new>
#include<algorithm>
using namespace std; //标准命名空间
class bitset
{
public:
bitset(size_t bitCount)
:bitCount(bitCount)
{
//resize会将vector中的元素初始化为0
_bitset.resize(bitCount / 32 + 1);
}
// 每个字节用0和1记录某个数字存在状态
// 把x所在的数据在位图的那一位变成1
void set(int x)
{
if (x > bitCount) return;
int index = x / 32;// x是第index个整数
int pos = x % 32;// x是第index个整数的第pos个位
_bitset[index] |= (1 << pos);
}
// 把x所在的数据在位图的那一位变成0
void reset(int x)
{
if (x > bitCount) return;
int index = x / 32;// x是第index个整数
int pos = x % 32;// x是滴index个整数的第pos个位
_bitset[index] &= ~(1 << pos);
}
// 判断x是否存在
bool test(int x)
{
if (x > bitCount) return false;
int index = x / 32;// x是第index个整数
int pos = x % 32;// x是滴index个整数的第pos个位
return _bitset[index] & (1 << pos);
}
private:
vector<int> _bitset;
int bitCount;// 开num比特位的空间
};
哈希函数个数和布隆过滤器长度的关系:
m = -n*ln(p) / (ln(2)^2)
k = m/n * ln(2)k 是哈希函数个数
m 为布隆过滤器长度
n为插入的元素个数
p为误判率
其中k=3,整体算下来,m≈4.34n,所以这里我们选择m为5
template<class T = string, class Hash1 = BKDRHash, class Hash2 = SDBHash, class Hash3 = RSHash>
class BloomFilter
{
public:
// 布隆过滤器的长度 近似等于4.3~5倍插入元素的个数
// 这里取 5
BloomFilter(size_t size)
:_bs(5 * size)
, _N(5 * size)
{}
private:
bitset _bs;
size_t _N;// 能够映射元素个数
};
三个字符串哈希函数如下: 用他们作为缺省参数,默认处理字符串类型
// BKDRHash
struct BKDRHash
{
size_t operator()(const string& str)
{
register size_t hash = 0;
for (size_t i = 0; i < str.length(); ++i)
{
hash = hash * 131 + str[i];
}
return hash;
}
};
// SDBHash
struct SDBHash
{
size_t operator()(const string str)
{
register size_t hash = 0;
for (size_t i = 0; i < str.length(); ++i)
{
hash = 65599 * hash + str[i];
//hash = (size_t)ch + (hash << 6) + (hash << 16) - hash;
}
return hash;
}
};
// RSHash
struct RSHash
{
size_t operator()(const string str)
{
register size_t hash = 0;
size_t magic = 63689;
for (size_t i = 0; i < str.length(); ++i)
{
hash = hash * magic + str[i];
magic *= 378551;
}
return hash;
}
};
插入
布隆过滤器的插入就是提供一个Set接口,核心思想就是把插入的元素通过三个哈希函数获取对应的整型并%比特位数从而获得对应的3个映射位置,再把这三个位置置为1即可
步骤
- 先用不同的哈希函数计算出该数据分别要映射到位图的哪几个位置
- 然后把位图中的这几个位置设置为1
void set(const T& x)
{
size_t index1 = Hash1()(x) % _N;
size_t index2 = Hash2()(x) % _N;
size_t index3 = Hash3()(x) % _N;
_bs.set(index1);
_bs.set(index2);
_bs.set(index3);
}
查找
布隆过滤器的思想是将一个元素用多个哈希函数映射到一个位图中,因此被映射到的位置的比特位一定为
步骤:
-
先用不同的哈希函数计算出该数据分别要映射到位图的哪几个位置
-
然后判断位图中的这几个位置是否都为1,如果有一个不为1,说明该元素一定不在容器中,否则表示在容器中
注意: 可能会误报,判断在是不准确的,判断不在是准确的。(因为一个数据判断出它是在的,可能是它映射的几个数据可能是其它数据映射导致这几个位置为1的,所以判断结果为在,该结果有误判;而判断一个数据为不在时,那这个数据是一定不在的,因为它映射的几个位置不全为1)
bool IsInBloomFilter(const T& x)
{
size_t index1 = Hash1()(x) % _N;
size_t index2 = Hash2()(x) % _N;
size_t index3 = Hash3()(x) % _N;
return _bs.test(index1)
&& _bs.test(index2)
&& _bs.test(index3);// 可能会误报,判断在是不准确的,判断不在是准确的
}
删除
布隆过滤器不能直接支持删除工作,因为在删除一个元素时,可能会影响其他元素。
- 比如:删除上图中"create"元素,如果直接将该元素所对应的二进制比特位置0,“source”元素也被删除了,因为这两个元素在多个哈希函数计算出的比特位上刚好有重叠。
一种支持删除的方法(计数法删除):
- 将布隆过滤器中的每个比特位扩展成一个小的计数器,插入元素时给k个计数器(k个哈希函数计算出的哈希地址)加一,删除元素时,给k个计数器减一,通过多占用几倍存储空间的代价来增加删除操作。
- 缺陷:
- 无法确认元素是否真正在布隆过滤器中
- 存在计数回绕
当然,为什么至今过滤器都没有提供对应的删除接口呢?其实过滤器的本来目的就是为了提高效率和节省空间,但是在确认存在时去遍历文件,文件 IO 和磁盘 IO 的时间开销是不小的,其次在每个比特位增加额外的计数器,更是让空间开销飙升到本身的好几倍。
完整代码以及测试
BloomFilter.cpp文件
#define _CRT_SECURE_NO_WARNINGS
#include"bitset.h"
template<class T>
struct Hash
{
const T& operator()(const T& key)
{
return key;
}
};
// BKDRHash
struct BKDRHash
{
size_t operator()(const string& str)
{
register size_t hash = 0;
for (size_t i = 0; i < str.length(); ++i)
{
hash = hash * 131 + str[i];
}
return hash;
}
};
// SDBHash
struct SDBHash
{
size_t operator()(const string str)
{
register size_t hash = 0;
for (size_t i = 0; i < str.length(); ++i)
{
hash = 65599 * hash + str[i];
//hash = (size_t)ch + (hash << 6) + (hash << 16) - hash;
}
return hash;
}
};
// RSHash
struct RSHash
{
size_t operator()(const string str)
{
register size_t hash = 0;
size_t magic = 63689;
for (size_t i = 0; i < str.length(); ++i)
{
hash = hash * magic + str[i];
magic *= 378551;
}
return hash;
}
};
template<class T = string, class Hash1 = BKDRHash, class Hash2 = SDBHash, class Hash3 = RSHash>
class BloomFilter
{
public:
// 布隆过滤器的长度 近似等于4.3~5倍插入元素的个数
// 这里取 5
BloomFilter(size_t size)
:_bs(5 * size)
, _N(5 * size)
{}
void set(const T& x)
{
size_t index1 = Hash1()(x) % _N;
size_t index2 = Hash2()(x) % _N;
size_t index3 = Hash3()(x) % _N;
_bs.set(index1);
_bs.set(index2);
_bs.set(index3);
}
bool IsInBloomFilter(const T& x)
{
size_t index1 = Hash1()(x) % _N;
size_t index2 = Hash2()(x) % _N;
size_t index3 = Hash3()(x) % _N;
return _bs.test(index1)
&& _bs.test(index2)
&& _bs.test(index3);// 可能会误报,判断在是不准确的,判断不在是准确的
}
private:
bitset _bs;
size_t _N;// 能够映射元素个数
};
void TestBloomFilter()
{
BloomFilter<string> bf(100);
bf.set("douyin");
bf.set("kuaishou");
bf.set("pass cet6");
bf.set("aabb");
cout << bf.IsInBloomFilter("pass cet6") << endl;
cout << bf.IsInBloomFilter("kuaishou") << endl;
cout << bf.IsInBloomFilter("douyin") << endl;
cout << bf.IsInBloomFilter("abab") << endl;
}
int main() {
TestBloomFilter();
system("pause");
return EXIT_SUCCESS;
}
布隆过滤器优缺点
优点:
- 增加和查询元素的时间复杂度为:O(K), (K为哈希函数的个数,一般比较小),与数据量大小无关
- 哈希函数相互之间没有关系,方便硬件并行运算
- 布隆过滤器不需要存储元素本身,在某些对保密要求比较严格的场合有很大优势
- 在能够承受一定的误判时,布隆过滤器比其他数据结构有这很大的空间优势
- 数据量很大时,布隆过滤器可以表示全集,其他数据结构不能
- 使用同一组散列函数的布隆过滤器可以进行交、并、差运算
缺点:
- 有误判率,即存在假阳性(False Position),即不能准确判断元素是否在集合中(补救方法:再建立一个白名单,存储可能会误判的数据)
- 不能获取元素本身
- 一般情况下不能从布隆过滤器中删除元素
- 如果采用计数方式删除,可能会存在计数回绕问题
海量数据处理问题
哈希切割
- 给一个超过100G大小的log file, log中存着IP地址, 设计算法找到出现次数最多的IP地址? 如何找到top K的IP?如何直接用Linux系统命令实现?
a. 先创建1000个小文件A0-A999,然后计算i = hash(IP)%1000,i是多少,IP就进入编号为i的文件中,也就是Ai文件中,这样相同的IP就都进入了同一个文件中。先将一个小文件加载到内存中,依次读取放入unordered_map<string, int> 中,同时用一个pair<string, int> max记录当前出现次数最多的IP,然后不断更新记录当前的max,这样就得到出现次数最多的IP地址
b. 和上面的方法一样,这里用一个大小为K的堆来存储topK的IP
位图应用
1.给定100亿个整数,设计算法找到只出现一次的整数?
100亿个整数占用40G的空间,如果直接加载到内存中,空间肯定是不够的,所以我们这里可以考虑用位图来处理。
方案一: 改进位图,用两个比特位表示整数,用其中的三种状态00(没出现)、01(出现一次)和10(出现两次及以上)。消耗内存为:2*4 *(2^32-1)/32 byte≈1G
方案二: 用两个位图同时操作,对应比特位无数据时,两个位图此处设为0,有一个数据时,将两个位图中一个设为0,一个设为1,有两个及以上数据时,两个位图中对于比特位都设置为1。消耗空间和上面那种方法一样,也是1G
2.给两个文件,分别有100亿个整数,我们只有1G内存,如何找到两个文件交集?
方案一: 将文件1的整数映射到一个位图中,然后读取文件2中的数据,判断是否在位图中,在就是交集,消耗内存500M
方案二: 将文件1的整数映射到一个位图中, 将文件2的整数映射到另一个位图中,然后将两个位图进行按位与,与之后位图中为1的位就是两个文件的交集
3.位图应用变形:1个文件有100亿个int,1G内存,设计算法找到出现次数不超过2次的所有整数
方案: 和第一题思路一致,找出状态为00、01和10的即可,其中状态为11代表的是出现3次及以上。消耗内存为1G
布隆过滤器
1.给两个文件,分别有100亿个query,我们只有1G内存,如何找到两个文件交集?分别给出精确算法和近似算法
query是一个查询语句的意思,一个query语句的大小平均约为30-60字节100亿个query大约占用300-600G。
方案一(近似算法): 将文件1的query映射到布隆过滤器中,读取文件2中的query,判断是否在布隆过滤器中,在就是交集,是交集的一定在里面。(缺陷:交集中的数会不准确,因为有些数会误判,混到交集里面,判断在是不准确的,判断不在是准确的)
方案二(精确算法):
1.把文件1和文件2分别切分成A0、A1…A999和B0、B1…B999,两个文件分别切分成1000个小文件,然后将A0加载到内存放到unordered_set中,再依次和B0、B1…B999这10001个文件进行比较,然后加载A1到内存中,以此类推。用unordered_set的效率还是很高的,基本上是常数次。![]()
2.优化:哈希切分
不再使用平均切分,使用哈希切分,用公式:i = Hash(query)%1000。i是多少就进入编号为i的文件中。不同的query可能会进入编号不同的文件中,但相同的query一定会进入编号相同的文件中。
先将文件Ai加载到内存中,放到unordered_set中,然后读取Bi中query,判断是否在,在就是交集。这里只需要比较1000次,比上面那种方式比较次数少很多。
2.如何扩展BloomFilter使得它支持删除元素的操作
标签:index,进阶,32,布隆,C++,哈希,过滤器,位图,size From: https://www.cnblogs.com/yzsn12138/p/17014415.html方案: 用几个比特位来表示计数器。缺陷:给的为如果少了,容易导致计数溢出,如果位数多了,那么空间开销就会很多,是以牺牲布隆过滤器的优势为代价的。