大数据查重-位图算法
位：内存管理的最小单位是字节，一个字节是8个位。
有1亿个整数，最大值不超过1亿，问都有哪些元素重复了？谁是第一个重复的？ 内存限制100M
1亿 = 100M
如果是放到哈希表上：100M * 4 = 400M * 2 = 800M
内存限制100M，不让我们用哈希表，我们用位图算法：
什么是位图算法？
我们有下面一行数字：
我们用一个位存储数字是否出现过的状态，那么这几个数字，我们的位图数组需要定义多长呢？
我们一般是这样处理：
实现我们要找出这组数据的最大的数字19，因为小的值在位图数组里肯定是靠前存放，大的值靠后存放，只要能够保证把最大值的位能够表示出来，前面这些小的值的位必然也可以表现出来。
位图数组的长度怎么算呢？
假如我们用 char 来定义：一个char类型的元素1字节，一个字节8个位。
用最大值19除以8加个1
3个元素。
那么这些数字分别对应有3个元素的位数组的哪个位呢？
如果是char类型，就除以/模上8，如果是short，就除以/模上16，如果是int，就除以/模上32
以此类推。
我们定义好这个位图数组后，我们要做查重。
我们先遇到7，然后看这个7对应的这个位是0还是1，是0表示还没出现过，是1表示已经出现过。
我们要做查重，第一次遇到，设置成1，第二次遇到，发现是1，表示已经出现过了，这个数字是重复的了。
如何获取该位的值？
如何把这个位置置为1？
位图算法的优势：
大数据查重-位图算法代码实现
#include <iostream>
#include <vector>
#include <stdlib.h>
#include <time.h>
#include <memory>
using namespace std;
int main()
{
vector<int> vec{ 12,78,90,78,123,8,9,90 };
//定义位图数组
int max = vec[0];
for (int i = 1; i < vec.size(); i++)//O(n)
{
if (vec[i] > max)
max = vec[i];
}
int* bitmap = new int[max / 32 + 1]();//int是32个位，new把所有元素初始化为0
unique_ptr<int> ptr(bitmap);//为了可以自动释放内存
//找第一个重复出现的数字
for (auto key : vec)
{
int index = key / 32;
int offset = key % 32;
//取key对应的位的值
if (0 == (bitmap[index] & (1 << offset)))//0表示key没有出现过
{
bitmap[index] |= (1 << offset);//把当前位记为1
}
else
{
//cout << key << "是第一个重复出现的数字" << endl;
//return 0;
cout << key << "重复出现过!" << endl;
}
}
}
变换一下位图算法
找谁是第一个不重复的？
(用2个位保存数据的状态)
2的2次方：4个值了
我们只需要记录1和2就可以了。
先把所有的元素往位图数组上放1遍，判断，不存在的话，置为1，如果发现是1，就置为2。
第一个不重复的安装位图数组的顺序去找第一个位是1的值，就是第一个不重复的数字。
位图算法的缺陷
int的上限值是20亿 unsigned int的上限值是40亿
现在有3个值，1,3，10亿
如果用位图算法：
int bitmap[1000000000/32+1] 需要内存大小：30M
此时用哈希表才3*4 = 12 * 2 = 24byte
使用位图算法，推荐的数据序列：数据的个数 >= 序列里面数字的最大值，要相当