布隆过滤器与哈希 用Java手写一个简单的布隆过滤器

布隆过滤器时检查数据是否出现过的一种方法

核心是哈希

如果布隆过滤器返回 true 说明数据可能出现过

如果布隆过滤器返回 false 说明数据一定没出现过

import java.util.BitSet;
import java.util.Scanner;public class MyBloomFilter {/*** 位数组的大小*/private static final int DEFAULT_SIZE = 2 << 24;/*** 通过这个数组可以创建 6 个不同的哈希函数*/private static final int[] SEEDS = new int[]{3, 13, 46, 71, 91, 134};/*** 位数组。数组中的元素只能是 0 或者 1*/private BitSet bits = new BitSet(DEFAULT_SIZE);/*** 存放包含 hash 函数的类的数组*/private SimpleHash[] func = new SimpleHash[SEEDS.length];/*** 初始化多个包含 hash 函数的类的数组，每个类中的 hash 函数都不一样*/public MyBloomFilter() {// 初始化多个不同的 Hash 函数for (int i = 0; i < SEEDS.length; i++) {func[i] = new SimpleHash(DEFAULT_SIZE, SEEDS[i]);}}/*** 添加元素到位数组*/public void add(Object value) {for (SimpleHash f : func) {bits.set(f.hash(value), true);}}/*** 判断指定元素是否存在于位数组*/public boolean contains(Object value) {boolean ret = true;for (SimpleHash f : func) {ret = ret && bits.get(f.hash(value));}return ret;}/*** 静态内部类。用于 hash 操作！*/public static class SimpleHash {private int cap;private int seed;public SimpleHash(int cap, int seed) {this.cap = cap;this.seed = seed;}/*** 计算 hash 值*/public int hash(Object value) {int h;return (value == null) ? 0 : Math.abs((cap - 1) & seed * ((h = value.hashCode()) ^ (h >>> 16)));}}public static void main(String[] args) {// 布隆过滤器MyBloomFilter myBloomFilter=new MyBloomFilter();Scanner sc=new Scanner(System.in);System.out.println("请输入要进行的测试用例");int t=sc.nextInt();for (int i = 0; i < t; i++) {int num=sc.nextInt();if(myBloomFilter.contains(num)==true){System.out.println("数据可能已经出现过");}else{System.out.println("数据没有出现");}myBloomFilter.add(num);}}}