首先我们根据一个面试题来进入位图的理解 1. 面试题 给40亿个不重复的无符号整数,没排过序。给一个无符号整数,如何快速判断一个数是否在这40亿个数中。
大家思考一下,如果按照我们以往的思维,用直接遍历的方法来进行判断的话,40亿个整数,一共160亿个字节,需要的内存太大了,不符合实际,时间复杂度也很高。可能又会有人说,用二分法,但是这样的时间复杂度依然很高,所以就有了用位图解决的方法!
这个题目只需要判断这40亿个数字在或者不在,所以我们仔细想一想,只需要用标记就可以,用0和1标记即可,位图的概念就引出了: 数据是否在给定的整形数据中,结果是在或者不在,刚好是两种状态,那么可以使用一个二进制比特位来代表数据是否存在的信息,如果二进制比特位为1,代表存在,为0代表不存在。所谓位图,就是用每一位来存放某种状态,适用于海量数据,数据无重复的场景。通常是用来判断某个数据存不存在的。
本来一个数字需要4个字节来存储,但是用位图的话,一个数字就用一个字节的一个比特位来标记即可就比原先的遍历的方法所需的空间缩小了32倍!
比如: 我想要标记这些数字在不在,就将这些数字从左至右分别放入一个字节char内,但是char内部八个比特位的空间的编号时从右至左的!
就比如说: 画出这个图大家就应该理解了
那么位图如何实现呢?
我们构造一个位图的类bitset N是你的数字的个数,N/32后就是你需要的几个整形的空间,记得+1 然后在构造函数中将每个比特位置为0 i对应的是第几个整形空间的位置 j对应的是第i个整形空间的第j个位置 整形一共有32个字节 每个整形的最右边为第一个位置,编号为0 最左边为最后一个位置编号为31
template<size_t N>
class bitset
{
public:
bitset()
{
_bits.resize(N / 32 + 1, 0);
}
//将位图中的各个比特位进行标记
void set(size_t x)
{
int i = x / 32;
int j = x % 32;
_bit[i] |= (1 << j);
}
//将位图中对应x的比特位置零
void reset(size_t x)
{
int i = x / 32;
int j = x % 32;
_bit[i] &= ~(1 << j);
}
//判断
bool test(size_t x)
{
int i = x / 32;
int j = x % 32;
return _bits[i] & (1 << j);
}
private:
vector<int> _bits;
};
如果要标记某个位置,就将第i个位置的整形往或上1往左边移动j位后的结果(1和0或1都为1)
如果要删除某个位置,就要将它置零,所以第i个位置的整形与上1往左边移动j位后取反的结果, 1往做移动j位后取反,就只有第j位为0,其他位置都为1,与上第i个位置,第j个位置无论是0还是1都会置为0,其他位置是0就变为0,是1还是1
判断某个数是否存在就要看这个比特位是否为1,所以第i个位置的整形与上1往左边移动j位后的结果,第j位是0就是0,是1就是1,返回bool值即可
放一张图会更加清晰:
位图速度快,而且节省空间但是我们可以发现,位图他只能解决整形的问题,如果遇上string呢,就没有办法了,所以就有了下面的这种方法:
我们在使用新闻客户端看新闻时,它会给我们不停地推荐新的内容,它每次推荐时要去重,去掉 那些已经看过的内容。问题来了,新闻客户端推荐系统如何实现推送去重的? 用服务器记录了用 户看过的所有历史记录,当推荐系统推荐新闻时会从每个用户的历史记录里进行筛选,过滤掉那 些已经存在的记录。 如何快速查找呢?
布隆过滤器是由布隆(Burton Howard Bloom)在1970年提出的 一种紧凑型的、比较巧妙的概 率型数据结构,特点是高效地插入和查询,可以用来告诉你 “某样东西一定不存在或者可能存 在”,它是用多个哈希函数,将一个数据映射到位图结构中。此种方式不仅可以提升查询效率,也可以节省大量的内存空间。
就是说一个数据,可以通过多个哈希函数对应多个位置
布隆过滤器的思想是将一个元素用多个哈希函数映射到一个位图中,因此被映射到的位置的比特位一定为1。
所以可以按照以下方式进行查找:
分别计算每个哈希值对应的比特位置存储的是否为零,只要有一个为零,代表该元素一定不在哈希表中,否则可能在哈希表中。
注意:布隆过滤器如果说某个元素不存在时,该元素一定不存在,如果该元素存在时,该元素可能存在,因为有些哈希函数存在一定的误判。
比如:在布隆过滤器中查找"alibaba"时,假设3个哈希函数计算的哈希值为:1、3、7,刚好和其 他元素的比特位重叠,此时布隆过滤器告诉该元素存在,但实该元素是不存在的。
所以说布隆过滤器是存在误判率的!
那么如何降低误判率呢? 我们可以更多的哈希函数来进行存储计算,越多误判率越低,但是平均空间就越大
布隆过滤器不能直接支持删除工作,因为在删除一个元素时,可能会影响其他元素。
比如:删除上图中"tencent"元素,如果直接将该元素所对应的二进制比特位置0,“baidu”元素也 被删除了,因为这两个元素在多个哈希函数计算出的比特位上刚好有重叠。
一种支持删除的方法:将布隆过滤器中的每个比特位扩展成一个小的计数器,插入元素时给k个计数器(k个哈希函数计算出的哈希地址)加一,删除元素时,给k个计数器减一,通过多占用几倍存储空间的代价来增加删除操作。
但是也有不小的缺陷:
给一个超过100G大小的log file, log中存着IP地址, 设计算法找到出现次数最多的IP地址? 与上题条件相同,如何找到top K的IP?如何直接用Linux系统命令实现?
这个题目我们就用一个哈希函数进行切割,将这个100g的log file分成若干个小的文件,然后再对依次对这些小文件进行处理,使用map统计每个小文件里每个ip出现的次数,然后提取出每个map中的出现次数最多的ip,和其他小文件的出现次数最多的比较,选出最大的一个ip 但是如果统计中抛出内存异常的话就是单个小文件过大,还需要换一个哈希函数进行更加仔细的切分
例如:i=hashfunc(ip)%100 ip进入依次第i个小文件里 相同的ip一定是进入相同的小文件!
好了,今天的分享到这里就结束了,感谢大家的支持!