做装修网站卖钱,做网站流量怎么赚钱吗,什么网站做电气自动化兼职,上海营销网站制作什么是布隆过滤器#xff1f;
原理
布隆过滤器是一种基于位数组#xff08;bit array#xff09;和多个哈希函数的数据结构。其核心原理是#xff1a;
初始化一个长度为m的位数组#xff0c;所有位初始化为0。使用k个不同的哈希函数将元素映射到位数组中的k个位置。当插…什么是布隆过滤器
原理
布隆过滤器是一种基于位数组bit array和多个哈希函数的数据结构。其核心原理是
初始化一个长度为m的位数组所有位初始化为0。使用k个不同的哈希函数将元素映射到位数组中的k个位置。当插入一个元素时使用k个哈希函数计算该元素的k个哈希值并将位数组中对应位置的值设为1。当查询一个元素是否存在时使用同样的k个哈希函数计算该元素的k个哈希值并检查位数组中对应位置的值是否都为1。如果有一个位置的值为0则该元素肯定不在集合中如果所有位置的值都为1则该元素可能在集合中。 优点 空间效率高布隆过滤器通过使用位数组和哈希函数可以在相对较小的空间内表示一个大型集合。这使得它特别适合内存受限的应用场景。 插入和查询速度快插入和查询操作都只需要O(k)的时间复杂度k为哈希函数的数量非常高效。哈希函数的计算和位数组的访问都可以在常数时间内完成。 无需存储实际元素布隆过滤器只需要存储哈希值并不需要存储实际的元素数据因此它能有效地节省存储空间。 适用于分布式系统布隆过滤器可以轻松地分布在多个节点上通过分布式哈希算法进行管理适用于大规模分布式系统。 扩展性好一些扩展版本的布隆过滤器如可扩展布隆过滤器Scalable Bloom Filter可以动态调整大小适应不断增长的数据集。
缺点 存在误判率布隆过滤器有一定的误判率即可能会误判一个不在集合中的元素为存在。误判率取决于位数组的大小、哈希函数的数量和存储的元素数量。这是由于哈希冲突产生的。 无法删除元素基本布隆过滤器不支持删除操作因为无法确定一个位置上的1是由哪个元素设置的。虽然计数布隆过滤器Counting Bloom Filter可以支持删除操作但代价是需要更多的空间。 初始化参数选择复杂选择合适的位数组大小和哈希函数数量是一个复杂的问题。位数组太小或哈希函数数量太少会增加误判率而位数组太大或哈希函数数量太多则会浪费空间和时间。 不适用于动态集基本布隆过滤器在初始化时需要确定位数组的大小这对于元素数量动态变化的场景并不友好。可扩展布隆过滤器虽然可以动态调整大小但实现较为复杂。 不支持元素的完整存储和检索布隆过滤器只能判断元素是否存在于集合中无法存储和检索元素的实际内容。
应用场景
布隆过滤器在很多应用场景中都有广泛的应用 缓存系统在缓存系统中布隆过滤器可以用来快速判断一个请求是否命中缓存避免不必要的数据库查询解决缓存穿透问题。 垃圾邮件过滤邮件系统可以使用布隆过滤器来快速判断一封邮件是否是垃圾邮件。 网络爬虫在网络爬虫中布隆过滤器可以用来记录已经访问过的URL避免重复抓取。 数据库去重在大规模数据处理中布隆过滤器可以用来快速判断一个记录是否已经存在避免重复存储。 分布式系统在分布式系统中布隆过滤器可以用来快速判断一个数据是否存在于某个节点上提高查询效率。
布隆过滤器的实现
常用的几种有单体项目下使用Guava包下的BloomFilter分布式下使用Redission的RBloomFilter这些都是写好的布隆过滤器接下来将基于redis和jedis实现一个手写的分布式布隆过滤器
分布式布隆过滤器的实现
分布式布隆过滤器在大规模分布式系统中应用广泛它的实现主要涉及以下几个方面
位数组的分布将位数组分布在多个节点上每个节点存储部分位数组。哈希函数使用多个哈希函数来保证均匀分布。一致性哈希用来管理节点和数据之间的映射关系保证负载均衡和容错。
分布式哈希算法
一致性哈希是一种用于分布式系统的哈希算法能够有效地应对节点动态加入和退出的情况。它通过将所有节点和数据哈希到一个环上来实现数据的分布。主要包含以下步骤
哈希环将整个哈希空间组织成一个环环的大小通常是哈希函数的输出范围。节点哈希将每个节点通过哈希函数映射到环上的一个点。数据哈希将每个数据通过相同的哈希函数映射到环上的一个点。数据存储数据存储在顺时针方向遇到的第一个节点上。节点变动处理 节点加入重新分配一部分数据给新节点。节点退出将其数据重新分配给其他节点。
分布式布隆过滤器的实现
下面是用Java和Jedis实现的分布式布隆过滤器示例。我们使用一致性哈希来分配数据并用Redis存储位数组。
1. 一致性哈希实现
import java.util.SortedMap;
import java.util.TreeMap;public class ConsistentHashing {private final SortedMapInteger, String circle new TreeMap();private final int replicas;public ConsistentHashing(int replicas) {this.replicas replicas;}public void addNode(String node) {for (int i 0; i replicas; i) {circle.put((node i).hashCode(), node);}}public void removeNode(String node) {for (int i 0; i replicas; i) {circle.remove((node i).hashCode());}}public String getNode(String key) {if (circle.isEmpty()) {return null;}int hash key.hashCode();if (!circle.containsKey(hash)) {SortedMapInteger, String tailMap circle.tailMap(hash);hash tailMap.isEmpty() ? circle.firstKey() : tailMap.firstKey();}return circle.get(hash);}
}2. 分布式布隆过滤器实现
import redis.clients.jedis.Jedis;
import java.nio.charset.StandardCharsets;
import com.google.common.hash.Hashing;public class DistributedBloomFilter {private ConsistentHashing consistentHashing;private int size;private int numHashFunctions;public DistributedBloomFilter(int replicas, int size, int numHashFunctions) {this.consistentHashing new ConsistentHashing(replicas);this.size size;this.numHashFunctions numHashFunctions;}public void addNode(String host, int port) {consistentHashing.addNode(host : port);}public void removeNode(String host, int port) {consistentHashing.removeNode(host : port);}private static int[] getHashes(String value, int numHashes, int maxSize) {int[] hashes new int[numHashes];for (int i 0; i numHashes; i) {hashes[i] Math.abs(Hashing.murmur3_128(i).hashString(value, StandardCharsets.UTF_8).asInt() % maxSize);}return hashes;}private Jedis getJedisClient(String value) {// 使用一致性哈希算法找到合适的节点String node consistentHashing.getNode(value);// 解析节点信息并创建Jedis客户端实例String[] parts node.split(:);return new Jedis(parts[0], Integer.parseInt(parts[1]));}public void add(String value) {// 计算哈希值int[] hashes getHashes(value, numHashFunctions, size);try (Jedis jedis getJedisClient(value)) {// 设置位数组的对应位置for (int hash : hashes) {jedis.setbit(bloom_filter, hash, true);}}}public boolean contains(String value) {// 计算哈希值int[] hashes getHashes(value, numHashFunctions, size);try (Jedis jedis getJedisClient(value)) {// 查询位数组的对应位置for (int hash : hashes) {if (!jedis.getbit(bloom_filter, hash)) {return false;}}}return true;}public static void main(String[] args) {// 创建布隆过滤器实例DistributedBloomFilter bloomFilter new DistributedBloomFilter(3, 1000, 5);// 添加Redis节点bloomFilter.addNode(localhost, 6379);bloomFilter.addNode(localhost, 6380);bloomFilter.addNode(localhost, 6381);// 插入元素bloomFilter.add(apple);bloomFilter.add(banana);// 查询元素System.out.println(bloomFilter.contains(apple)); // 输出: trueSystem.out.println(bloomFilter.contains(banana)); // 输出: trueSystem.out.println(bloomFilter.contains(cherry)); // 输出: false}
}
