建网站公司专业,做网站联系电话,烟台网站营销,公司网站建设一年多少钱目录
一. 位图
1.题目#xff1a;
给40亿个不重复的无符号整数#xff0c;没排过序。给一个无符号整数#xff0c;如何快速判断一个数是否在这40亿个数中#xff1f;
2.解析题目#xff1a;
3.位图
4.代码以及测试
5.其他题目
二.布隆过滤器
1.介绍
2.实现
…目录
一. 位图
1.题目
给40亿个不重复的无符号整数没排过序。给一个无符号整数如何快速判断一个数是否在这40亿个数中
2.解析题目
3.位图
4.代码以及测试
5.其他题目
二.布隆过滤器
1.介绍
2.实现
3.应用 这两个数据结构都是由哈希思想实现的。
一. 位图
1.题目
给40亿个不重复的无符号整数没排过序。给一个无符号整数如何快速判断一个数是否在 这40亿个数中
2.解析题目
40亿整数需要16G空间但内存只有4G所以需要节省空间。
由于题目只需要知道这个数在不在我们只需要分配1bit的空间判断在不在即可。0表示不在1表示在
这种方法就是位图。
3.位图 4.代码以及测试
#pragma once
//N代表你要多少位比特位
//判断某个数在不在这40亿个数里实际上我们可能要开42亿比特位long long能表示42亿不同整数
templatesize_t N
class bit_set
{
public:bit_set(){_bits.resize(N / 32 1, 0);}void set(size_t x)//将比特位置为1{size_t i x / 32;size_t j x % 32;_bits[i] | (1 j);}void reset(size_t x)//将比特位置为1{size_t i x / 32;size_t j x % 32;_bits[i] ~(1 j);}bool test(size_t x)//判断整数x在不在{size_t i x / 32;size_t j x % 32;return (_bits[i] (1 j));}
private:vectorint _bits;
};
int main()
{bitset100 bs;bs.set(40);bs.set(41);bs.set(39);bs.set(38);bs.set(40);cout bs.test(40) endl;return 0;
}
5.其他题目
题目给定100亿整数设计算法找到只出现一次的整数。 二.布隆过滤器
1.介绍
位图的缺点在于只能处理整形。
布隆过滤器通过位图加哈希函数实现其他类型也能映射到相映比特位上。 2.实现
#pragma once
#includebitset.hstruct BKDRHash
{size_t operator()(const string key){// BKDRsize_t hash 0;for (auto e : key){hash * 31;hash e;}return hash;}
};struct APHash
{size_t operator()(const string key){size_t hash 0;for (size_t i 0; i key.size(); i){char ch key[i];if ((i 1) 0){hash ^ ((hash 7) ^ ch ^ (hash 3));}else{hash ^ (~((hash 11) ^ ch ^ (hash 5)));}}return hash;}
};struct DJBHash
{size_t operator()(const string key){size_t hash 5381;for (auto ch : key){hash (hash 5) ch;}return hash;}
};templatesize_t N,class K string,class HashFunc1 BKDRHash,class HashFunc2 APHash,class HashFunc3 DJBHash
class BloomFilter
{
public:void Set(const K key){size_t hash1 HashFunc1()(key) % N;size_t hash2 HashFunc2()(key) % N;size_t hash3 HashFunc3()(key) % N;_bs.set(hash1);_bs.set(hash2);_bs.set(hash3);/*cout hash1 endl;cout hash2 endl;cout hash3 endl endl;*/}// 一般不支持删除删除一个值可能会影响其他值// 非要支持删除也是可以的用多个位标记一个值存引用计数// 但是这样话空间消耗的就变大了void Reset(const K key);//解决引用计数多一些空间用来计数bool Test(const K key){// 判断不存在是准确的size_t hash1 HashFunc1()(key) % N;if (_bs.test(hash1) false)return false;size_t hash2 HashFunc2()(key) % N;if (_bs.test(hash2) false)return false;size_t hash3 HashFunc3()(key) % N;if (_bs.test(hash3) false)return false;// 存在误判的return true;}private:bit::bitsetN _bs;
};3.应用
a.我们玩游戏注册名称时有时会看到名称已被使用的情况。
这里可以通过布隆过滤器记录已存在的名称
如果发现此名称不存在则真的不存在
如果发现此名称在映射位置被占用可能误判名称存在我们可以再去服务器比对看看名称是否真的存在。
b.给两个文件分别有100亿字符串我们只有1G内存如何找到两个文件交集
