import java.util.BitSet;
import java.util.Random;
public class BloomFilter {
??private BitSet bitSet; ??????????// 位集，用于存儲(chǔ)哈希值
??private int bitSetSize; ????????// 位集大小
??private int numHashFunctions; ??// 哈希函數(shù)數(shù)量
??private Random random; ?????????// 隨機(jī)數(shù)生成器
??// 構(gòu)造函數(shù)，根據(jù)期望元素?cái)?shù)量和錯(cuò)誤率計(jì)算位集大小和哈希函數(shù)數(shù)量
??public BloomFilter(int expectedNumItems, double falsePositiveRate) {
????this.bitSetSize = optimalBitSetSize(expectedNumItems, falsePositiveRate);
????this.numHashFunctions = optimalNumHashFunctions(expectedNumItems, bitSetSize);
????this.bitSet = new BitSet(bitSetSize);
????this.random = new Random();
??}
??// 根據(jù)期望元素?cái)?shù)量和錯(cuò)誤率計(jì)算最佳位集大小
??private int optimalBitSetSize(int expectedNumItems, double falsePositiveRate) {
????int bitSetSize = (int) Math.ceil(expectedNumItems * (-Math.log(falsePositiveRate) / Math.pow(Math.log(2), 2)));
????return bitSetSize;
??}
??// 根據(jù)期望元素?cái)?shù)量和位集大小計(jì)算最佳哈希函數(shù)數(shù)量
??private int optimalNumHashFunctions(int expectedNumItems, int bitSetSize) {
????int numHashFunctions = (int) Math.ceil((bitSetSize / expectedNumItems) * Math.log(2));
????return numHashFunctions;
??}
??// 添加元素到布隆過(guò)濾器中
??public void add(String item) {
????// 計(jì)算哈希值
????int[] hashes = createHashes(item.getBytes(), numHashFunctions);
????// 將哈希值對(duì)應(yīng)的位設(shè)置為 true
????for (int hash : hashes) {
??????bitSet.set(Math.abs(hash % bitSetSize), true);
????}
??}
??// 檢查元素是否存在于布隆過(guò)濾器中
??public boolean contains(String item) {
????// 計(jì)算哈希值
????int[] hashes = createHashes(item.getBytes(), numHashFunctions);
????// 檢查哈希值對(duì)應(yīng)的位是否都為 true
????for (int hash : hashes) {
??????if (!bitSet.get(Math.abs(hash % bitSetSize))) {
????????return false;
??????}
????}
????return true;
??}
??// 計(jì)算給定數(shù)據(jù)的哈希值
??private int[] createHashes(byte[] data, int numHashes) {
????int[] hashes = new int[numHashes];
????int hash1 = Math.abs(random.nextInt());
????int hash2 = Math.abs(random.nextInt());
????for (int i = 0; i < numHashes; i++) {
??????// 使用兩個(gè)隨機(jī)哈希函數(shù)計(jì)算哈希值
??????hashes[i] = Math.abs((hash1 * i) + (hash2 * i) + i) % data.length;
????}
????return hashes;
??}
}