本章主要讲解C++中对哈希的应用有关方面的内容,位图,布隆,海量数据处理
给40亿个不重复的无符号整数,没排过序。给一个无符号整数,如何快速判断一个数是否在这40亿个数中
成员函数 | 功能 |
---|---|
set | 设置指定位或所有位 |
reset | 清空指定位或所有位 |
flip | 反转指定位或所有位 |
test | 获取指定位的状态 |
count | 获取被设置位的个数 |
size | 获取可以容纳的位的个数 |
any | 如果有任何一个位被设置则返回true |
none | 如果没有位被设置则返回true |
all | 如果所有位都被设置则返回true |
#include <iostream>
#include <bitset>
using namespace std;
int main()
{
bitset<8> bs;
bs.set(2); //设置第2位
bs.set(4); //设置第4位
cout << bs << endl; //00010100
bs.flip(); //反转所有位
cout << bs << endl; //11101011
cout << bs.count() << endl; //6
cout << bs.test(3) << endl; //1
bs.reset(0); //清空第0位
cout << bs << endl; //11101010
bs.flip(7); //反转第7位
cout << bs << endl; //01101010
bs.reset(); //清空所有位
cout << bs.none() << endl; //1
bs.set(); //设置所有位
cout << bs.all() << endl; //1
return 0;
}
注:使用成员函数set、reset、flip时,若指定了某一位则操作该位,若未指定位则操作所有位
template<size_t N>
class bitset
{
public:
bitset()
{
_bits.resize(N / 8 + 1,0);//开辟空间并置为0
//_bits.resize((N >> 3) + 1,0);
}
bool test(size_t x)
{
size_t i = x / 8;//处于的该数组的第几个空间
size_t j = x % 8;//处于的该空间的第几个比特位
return _bits[i] & (1 << j);
}
void set(size_t x)
{
size_t i = x / 8;//处于的该数组的第几个空间
size_t j = x % 8;//处于的该空间的第几个比特位
_bits[i] |= (1 << j);//该位置置为1
}
void reset(size_t x)
{
size_t i = x / 8;//处于的该数组的第几个空间
size_t j = x % 8;//处于的该空间的第几个比特位
_bits[i] &= (~(1 << j));//该位置置为0
}
private:
vector<char> _bits;
};
当字符串使用哈希时,无可避免的会出现哈希冲突的问题(可能两个不同的内容映射相同的位置),而位图又是一个不能解决哈希冲突的数据结构。于是布隆过滤器则是使用了多个哈希函数,将数据映射到多个位置上面,才能确保数据的准确性,减小误判的概率
使用了多个哈希函数,将数据映射到多个位置上面,并将对应位置标记为1
布隆过滤器不能直接支持删除工作,因为在删除一个元素时,可能会影响其他元素(哈希冲突)
将布隆过滤器中的每个比特位扩展成一个小的计数器,插入元素时给k个计数器(k个哈希函数计算出的哈希地址)加一,删除元素时,给k个计数器减一,通过多占用几倍存储空间的代价来增加删除操作
struct _BKDRHash
{
//BKDRHash
size_t operator()(const std::string& key)
{
size_t hash = 0;
for (size_t i = 0; i < key.size(); i++)
{
hash *= 131;
hash += key[i];
}
return hash;
}
};
struct _SDBMHash
{
//SDBMHash
size_t operator()(const std::string& key)
{
size_t hash = 0;
for (size_t i = 0; i < key.size(); i++)
{
hash *= 65599;
hash += key[i];
}
return hash;
}
};
struct _RSHash
{
//RSHash
size_t operator()(const std::string& key)
{
size_t hash = 0;
size_t magic = 63689;
for (size_t i = 0; i < key.size(); i++)
{
hash *= magic;
hash += key[i];
magic *= 378551;
}
return hash;
}
};
template<size_t N,class K=std::string,
class Hash1=_BKDRHash,class Hash2=_SDBMHash,class Hash3=_RSHash>
class BloomFilter
{
public:
bool Test(const K& key)
{
size_t index1 = Hash1()(key) % len;
size_t index2 = Hash2()(key) % len;
size_t index3 = Hash3()(key) % len;
if (!_bs.test(index1) || !_bs.test(index2) || !_bs.test(index3))
return false;
return true;
}
void Set(const K& key)
{
size_t index1 = Hash1()(key) % len;
size_t index2 = Hash2()(key) % len;
size_t index3 = Hash3()(key) % len;
_bs.set(index1);
_bs.set(index2);
_bs.set(index3);
}
private:
bitset<6*N> _bs;
size_t len = 6 * N;
};
}
这里的数据要求40亿个不重复的无符号整数,使用位图用一个位来表示一个整数,将所有的数据映射到位图上,当进行查询时,只要位图的对应位置为1,则说明该数据在这40亿个数据中
方法1:使用特定的位图,每个映射的数有对应的两个bit位进行表示映射的状态 方法2:使用两个位图,同样的两个位图对应的映射的数的位置共同表示映射状态 注:没有映射00,一次映射01,一次以上映射10
方法1:将文件1的整数全部映射到位图中,接着从文件2中读取数据,并在位图中查询该数据,如果数据存在,则说明该数据是交集之一 方法2:使用两个位图,对两个文件进行分别遍历文件读取数据映射到位图上,然后对位图进行遍历求交集,同一个位置都为1,那么则为交集
方法1:使用特定的位图,每个映射的数有对应的两个bit位进行表示映射的状态 方法2:使用两个位图,同样的两个位图对应的映射的数的位置共同表示映射状态 注:没有映射00,一次映射01,两次映射10,三次以上映射11
注:query一般为URL中的查询字符串或者SQL中的查询语句,假设每个query30个字节,那么100亿个query也得300G的内存才能装下 近似算法:使用布隆过滤器来进行处理,对一个文件将数据全部进行哈希映射,再对另一个文件中的数据进行查询,但是可能存在哈希冲突,导致造成误判,所以当一个数据不存在于布隆过滤器中,则它必定不存在,但是如果一个数据存在于布隆过滤器中,它也不一定存在 精确算法:如果要精确的进行查找,那就必须得将数据放入内存中,但是由于数据过大我们可以将数据存入到服务器中,先使用布隆过滤器进行处理,如果对应映射不存在,那么久一定不是交集,如果对应映射存在那么就到服务器中进行二次查询 平均切割: 平均切割不是一个很好的方法,但是它确实是我们很容易就能思考到的方法,我们将两个文件中的数据平均切分为M份(能放入内存),分别存储到一个set中,然后以此将数据进行比较,这种方法就需要以此对所有的数据进行比对,效率会比较低 哈希切割: 创建多个临时文件,并进行标号,读取文件数据使用字符串哈希算法进行哈希映射,映射到对应的文件并将数据存进去,对两个文件的数据都采用这样的做法进行切分,由于我们使用的是同一种字符串哈希算法,所以相同的字符串必定会被映射到同一个编号下的文件中,所以我们只需要依次对编号相同的Ai和Bi文件中使用set寻找交集即可(如果有些文件切分之后依然过大,可以继续对其进行切分)
使用哈希切割的方式来解决文件分片的问题,相同的IP地址必定会被映射到同一个文件中,所以我们依次读取文件,使用Map进行次数统计即可之后再进行排序即可
Linux的命令:sort log_file | uniq -c | sort -nr | head -k
说明:首先使用sort log_file来将数据进行一个排序,使得相同的IP地址全部靠在一起。接着使用uniq - c进行去重,并将重复的次数显示在每列的旁边,通过这个次数来使用sort -nr进行降序排序,使得出现次数最的IP地址在前面,然后使用head -k 获取前k个IP地址即可
由于100w个数据并不算多,可以存放进内存中,所以可以考虑以下解法 方法1:采用快排中的partition划分思想,即单趟划分后,枢轴s前面的数据都比他大,后面的数据都比他小,此时我们选取其中较大的那一部分,继续划分。当划分后前端的数据刚好等于100后划分结束,对前端数据进行排序即可得到结果。如果前端数据不足100,则从后端数据进行排序后取出不足的那部分补上,再进行排序即可。O(100w*100) 方法2:局部淘汰法,使用插入排序来完成,首先取出前100个数据进行排序,然后依次遍历后面的数据,如果数据大于最小值,则将最小值删除,然后按照插入排序的思路将数据插入进去O(100w*100) 方法3:局部淘汰法,使用一个大小为100的小堆来完成,维护一个小堆,当数据比堆顶也就是最小值大的时候,用新数据替换掉堆顶,然后调整堆的结构。遍历完所有数据后就可以得到前100的数据。O(100w*lg100)
对于每一个电脑,都构建一个大小为10的堆(选大的构建小堆,选小的构建大堆),选出当前电脑的TOP10,接着将所有电脑的数据汇总起来,共1000个数据,继续用堆从其中选出TOP10
使用倒排索引来解决,即建立起单词——文件的映射,只需要遍历所有文章,如果文章中出现过查询词,则将文件号追加在对应词的倒排拉链中即可,如果100M的文件放不下内存中,就对数据进行切割后处理即可