自己搞个网站需要多少钱,7k7k游戏网页版入口,新材建设局网站,泰兴彩页设计海量数据如何判重#xff1f;
判断一个值是否存在#xff1f;解决方法#xff1a;
1.使用哈希表#xff1a; 可以将数据进行哈希操作#xff0c;将数据存储在相应的桶中。 查询时#xff0c;根据哈希值定位到对应的桶#xff0c;然后在桶内进行查找。这种方法的时间复…海量数据如何判重
判断一个值是否存在解决方法
1.使用哈希表 可以将数据进行哈希操作将数据存储在相应的桶中。 查询时根据哈希值定位到对应的桶然后在桶内进行查找。这种方法的时间复杂度为 O(1)但需要额外的存储空间来存储哈希表。如果桶中存在数据则说明此值已存在否则说明未存在。
2.使用布隆过滤器 布隆过滤器是一种概率型数据结构用于判断一个元素是否在集合中。它利用多个哈希函数映射数据到一个位数组并将对应位置置为 1。 查询时只需要对待查询的数据进行哈希并判断对应的位是否都为 1。如果都为 1则该数据可能存在如果有一个位不为 1则该数据一定不存在。布隆过滤器的查询时间复杂度为 O(k)其中 k 为哈希函数的个数。
相同点和不同点
相同点 它们都存在误判的情况。 例如使用哈希表时不同元素的哈希值可能相同所以这样就产生误判了 而布隆过滤器的特征是当布隆过滤器说某个数据存在时这个数据可能不存在当布隆过滤器说某个数据不存在时那么这个数据一定不存在
不同点 存储机制 哈希表使用一个数组来存储键值对通过哈希函数将键映射到数组的索引位置然后将值存储在对应的位置上。 布隆过滤器则使用一个位数组或位向量通过多个哈希函数将元素映射到位数组的多个位上。
查询操作 哈希表在进行查询时通过计算哈希值来定位键值对的存储位置然后直接获取对应的值。查询时间复杂度通常为 O(1)。 布隆过滤器在进行查询时也通过多个哈希函数计算多个位然后判断对应的位是否都为 1 来确定元素是否存在。查询时间复杂度为 O(k)其中 k 为哈希函数的个数。
内存占用 哈希表需要根据数据规模来动态调整数组的大小以保证存储效率。 布隆过滤器在预先设置位数组的大小后不会随数据规模的增加而增长。因此布隆过滤器更适用于海量数据。
结论 哈希表和布隆过滤器都能实现判重但它们都会存在误判的情况但布隆过滤器存储占用的空间更小更适合海量数据的判重。
布隆过滤器实现原理
布隆过滤器的实现主要依靠的是它数据结构中的一个位数组每次存储键值的时候不是直接把数据存储在数据结构中因为这样太占空间了它是利用几个不同的无偏哈希函数把此元素的 hash 值均匀的存储在位数组中也就是说每次添加时会通过几个无偏哈希函数算出它的位置把这些位置设置成 1 就完成了添加操作。 当进行元素判断时查询此元素的几个哈希位置上的值是否为 1如果全部为 1则表示此值存在如果有一个值为 0则表示不存在。因为此位置是通过 hash 计算得来的所以即使这个位置是 1并不能确定是那个元素把它标识为 1 的因此布隆过滤器查询此值存在时此值不一定存在但查询此值不存在时此值一定不存在。
并且当位数组存储值比较稀疏的时候查询的准确率越高而当位数组存储的值越来越多时误差也会增大。 位数组和 key 之间的关系如下图
如何实现布隆过滤器
1.通过程序实现内存级别方案使用 Google Guava 库实现布隆过滤器。 2.通过中间件实现支持数据持久化使用 Redis 4.0 之后提供的布隆过滤插件来实现它的好处是支持持久化数据不会丢失。
一、什么是Guava 1Guava库是一个适合很多Java项目的通用工具库 2Guava工具库中包含了集合Collection、并发Concurrency、原语Primitive、反射Reflection、比较Comparison、I/O操作、哈希Hash、网络Networking、字符串String、数学函数Math、缓存Caching、内存中的发布/订阅……以及各种级别的数据类型 3需要JDK 6以上版本
使用 Google Guava 库实现布隆过滤器总共分为以下两步
引入 Guava 依赖使用 Guava API 操作布隆过滤器 ① 引入 Guava 依赖
dependencygroupIdcom.google.guava/groupIdartifactIdguava/artifactId
/dependency
② 使用 Guava API
import com.google.common.hash.BloomFilter;
import com.google.common.hash.Funnels;public class BloomFilterExample {public static void main(String[] args) {// 创建一个布隆过滤器设置期望插入的数据量为10000期望的误判率为0.01BloomFilterString bloomFilter BloomFilter.create(Funnels.unencodedCharsFunnel(), 10000, 0.01);// 向布隆过滤器中插入数据bloomFilter.put(data1);bloomFilter.put(data2);bloomFilter.put(data3);// 查询元素是否存在于布隆过滤器中System.out.println(bloomFilter.mightContain(data1)); // trueSystem.out.println(bloomFilter.mightContain(data4)); // false}
}
在上述示例中我们通过 BloomFilter.create() 方法创建一个布隆过滤器指定了元素序列化方式、期望插入的数据量和期望的误判率。然后我们可以使用 put() 方法向布隆过滤器中插入数据使用 mightContain() 方法来判断元素是否存在于布隆过滤器中。
