大米品牌推广方案,seo推广员是做什么的,爱站网长尾关键词挖掘工具,福建交通建设网站位图/布隆过滤器 位图位图概念位图的使用位图模拟实现 布隆过滤器布隆过滤器概念布隆过滤器的使用布隆过滤器模拟实现 位图/布隆过滤器应用#xff1a;海量数据处理哈希切分 位图
位图概念
计算机中通常以位bit为数据最小存储单位#xff0c;只有0、1两种二进制状态#x… 位图/布隆过滤器 位图位图概念位图的使用位图模拟实现 布隆过滤器布隆过滤器概念布隆过滤器的使用布隆过滤器模拟实现 位图/布隆过滤器应用海量数据处理哈希切分 位图
位图概念
计算机中通常以位bit为数据最小存储单位只有0、1两种二进制状态这决定了位可以用来保存某一项条件yes/no的信息且这种方式是占用系统内存最小的方式。因此C中标准库提供bitset类以位bit为最小单位存储数据主要用于提供位级别的操作。 位图就是用每一位来存放某种状态适用于海量数据数据无重复的场景。通常是用来判断某个数据存不存在的。 位图的使用
初始化bitset,初始化同时给定bit的个数n
bitset16 foo;
bitset16 bar(0xfa2);
bitset16 baz(0101111001); //从右往左读取如果字符串长度小于n位数补0
foo: 0000000000000000
bar: 0000111110100010
baz: 0000000101111001bitset操作汇总
位图模拟实现
templatesize_t N
class bitset {bitset(){_bt.resize(N / 8 1,0);}//将x位设位1void set(size_t x){size_t i x / 8;size_t j x % 8;_bt[i] | (1 j);}//将x位设位0void reset(size_t x){size_t i x / 8;size_t j x % 8;_bt[i] ~(1 j);}//查询x在不在bool test(size_t x){size_t i x / 8;size_t j x % 8;return _bt[i] (1 j);}
private:vectorchar _bt;
};//海量数据处理时
void BitSetTest()
{// 开出42亿9千万个比特位bitset-1 bs1; bitset0xffffffff bs2;
}布隆过滤器
布隆过滤器概念
布隆过滤器是由布隆Burton Howard Bloom在1970年提出的 一种紧凑型的、比较巧妙的概率型数据结构特点是高效地插入和查询可以用来告诉你 “某样东西一定不存在或者可能存在”它是用多个哈希函数将一个数据映射到位图结构中。此种方式不仅可以提升查询效率也可以节省大量的内存空间。 与位图的区别 布隆过滤器布隆过滤器主要用于快速地判断一个元素是否可能存在于数据集合中。可能存在一定的误判率 位图位图主要用于精确地判断一个整数是否存在于集合中。它可以不会出现误判。 布隆过滤器的使用
初始化 布隆过滤器使用一个长度为m的位图并初始化所有位为0。同时需要选择k个不同的哈希函数。
插入 当要将一个元素加入到布隆过滤器时对该元素进行k次哈希计算得到k个哈希值通常是整数。然后将位数组中对应的k个位置设置为1。
查询 布隆过滤器进行k次哈希计算得到k个哈希值。 若其中有任何一个位置为0则可以确定该元素一定不存在于布隆过滤器中否则可能存在这里存在着一定的误判率因不同的元素可能存在相同的哈希值导致位图中相同位置表示了不同的元素存在情况 删除 布隆过滤器不能直接支持删除工作因为在删除一个元素时可能会影响其他元素。 优化将布隆过滤器中的每个bit位扩展成一个小的计数器插入元素时哈希函数计算后为k个位置给该位置的计数器1删除元素时元素相应位置计数器-1通过多占用几倍存储空间的代价来增加删除操作。
注意事项 哈希函数的选择哈希函数应该能够均匀地分布哈希值以最大程度减少冲突的可能性。 位数组的大小位数组的长度m和哈希函数的个数k会直接影响布隆过滤器的误判率。通常情况下m的大小与预期存储元素数量和容忍的误判率有关。 误判率布隆过滤器存在一定的误判率即可能判断某个元素存在于布隆过滤器中但实际上并不存在。这是由于不同元素在位数组上可能发生冲突的原因。 布隆过滤器模拟实现
templatesize_t N,size_t X 5,class K string,
class HashFunc1 BKDRHash,
class HashFunc2 APHash,
class HashFunc3 DJBHash
class BloomFilter
{
public:void Set(const K key){size_t len X*N;size_t index1 HashFunc1()(key) % len;size_t index2 HashFunc2()(key) % len;size_t index3 HashFunc3()(key) % len;_bs.set(index1);_bs.set(index2);_bs.set(index3);}bool Test(const K key){size_t len X*N;size_t index1 HashFunc1()(key) % len;if (_bs.test(index1) false)return false; //准确的size_t index2 HashFunc2()(key) % len;if (_bs.test(index2) false)return false; //准确的size_t index3 HashFunc3()(key) % len;if (_bs.test(index3) false)return false; //准确的return true; // 存在误判的}// 不支持删除删除可能会影响其他值。void Reset(const K key);
-private:bitsetX*N _bs;位图/布隆过滤器应用海量数据处理
位图的应用 快速查找某个数据是否在一个集合中 1.给40亿个不重复的无符号整数没排过序。给一个无符号整数如何快速判断一个数是否在这40亿个数中。【腾讯】 解答 1G2^3010亿bytes 40亿个int160亿bytes16G 数据量非常大占用内存空间高用位图可以减少占用内存空间 数据是否在给定的整形数据中结果是在或者不在刚好是两种状态那么可以使用一个二进制比特位来代表数据是否存在的信息如果二进制比特位为1代表存在为0代表不存在。比如 2.给定100亿个整数设计算法找到只出现一次的整数 用两个位图表示可以表示的组合有
组合出现次数000011102113次以上
统计位图中存的是01的数即为所求 求两个集合的交集、并集 3.给两个文件分别有100亿个整数我们只有1G内存如何找到两个文件交集 初始思路一个文件所有值映射读取另一个文件判断在不在 问题文件中可能存在多个相同的元素得出的交集需要去重耗费时间。 优化两个文件两个位图对应位置运算结果为1的该位置代表的元素是交集 操作系统中磁盘块标记 布隆过滤器应用 给两个文件分别有100亿个query我们只有1G内存如何找到两个文件交集给出精确算法 精确算法 假设每个query占30个字节则上面每个文件有3000亿字节300G文件很大我们可以先将它们分成若干小文件每个小文件之间找交集。 我们使用哈希切割来分割文件。 这样相同的query一定进入标号相同的小文件。我们只需分别求两个标号相同小文件的交集。接下来用set找交集读出Ai放到set读Bi看在不在set不在则删去。
哈希切分
哈希切分在数据库和分布式系统中经常被使用。以下是一些常见的情况可以考虑使用哈希切分
1.数据库分片当数据库数据量巨大而单个数据库服务器无法承载时可以将数据划分成多个分片并使用哈希函数将数据分配到不同的分片中。这样可以提高数据库的可扩展性和性能。
2.负载均衡在分布式系统中使用哈希切分可以实现负载均衡。根据请求的特定属性如客户ID、请求URL等通过哈希函数计算得到一个标识符然后利用该标识符选择相应的服务器来处理请求从而使负载分布更加均匀。
3.分布式缓存在分布式缓存系统中使用哈希切分可以将数据分散存储到多个缓存节点中从而提高缓存容量和读取性能。通过哈希函数计算数据的键值然后将数据存储到相应的节点上。
需要注意的是在使用哈希切分时要确保哈希函数具有良好的均匀性和随机性以避免数据倾斜和热点问题。此外由于哈希切分可能引入数据迁移和一致性问题需要谨慎设计和实施。
