今天就跟大家聊聊有關使用JAVA怎么實現一個布隆過濾器，可能很多人都不太了解，為了讓大家更加了解，小編給大家總結了以下內容，希望大家根據這篇文章可以有所收獲。
我們提供的服務有：做網站、成都做網站、微信公眾號開發(fā)、網站優(yōu)化、網站認證、五臺ssl等。為1000+企事業(yè)單位解決了網站和推廣的問題。提供周到的售前咨詢和貼心的售后服務，是有科學管理、有技術的五臺網站制作公司
布隆過濾器是可以用于判斷一個元素是不是在一個集合里，并且相比于其它的數據結構，布隆過濾器在空間和時間方面都有巨大的優(yōu)勢。布隆過濾器存儲空間和插入/查詢時間都是常數。但是它也是擁有一定的缺點：布隆過濾器是有一定的誤識別率以及刪除困難的。本文中給出的布隆過濾器的實現，基本滿足了日常使用所需要的功能。
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
先簡單來說一下布隆過濾器。其實現方法就是：利用內存中一個長度為M的位數組B并初始化里面的所有位都為0，如下面的表格所示：
然后我們根據H個不同的散列函數，對傳進來的字符串進行散列，并且每次的散列結果都不能大于位數組的長度。布隆過濾器的誤判率取決于你使用多少個不同的散列函數，下面給出的代碼中，給出了一些參考的誤判率（參考代碼中的枚舉類：MisjudgmentRate）。現在我們先假定有4個不同散列函數，傳入一個字符串并進行一次插入操作，這時會進行4次散列，假設到了4個不同的下標，這個時候我們就會去數組中，將這些下標的位置置為1，數組變更為：
| 0 | 1 | 0 | 1 | 1 | 0 | 0 | 0 | 0 | 1 |
如果接下來我們再傳入同一個字符串時，因為4次的散列結果都是跟上一次一樣的，所以會得出跟上面一樣的結果，所有應該置1的位都已經置1了，這個時候我們就可以認為這個字符串是已經存在的了。因此不難發(fā)現，這是會存在一定的誤判率的，具體由你采用的散列函數質量，以及散列函數的數量確定。
代碼如下：
重慶分公司
重慶分公司
import java.io.FileInputStream;
import java.io.FileOutputStream;
import java.io.ObjectInputStream;
import java.io.ObjectOutputStream;
import java.io.Serializable;
import java.util.BitSet;
import java.util.concurrent.atomic.AtomicInteger;
public class BloomFileter implements Serializable {
private static final long serialVersionUID = -5221305273707291280L;
private final int[] seeds;
private final int size;
private final BitSet notebook;
private final MisjudgmentRate rate;
private final AtomicInteger useCount = new AtomicInteger(0);
private final Double autoClearRate;
/**
* 默認中等程序的誤判率：MisjudgmentRate.MIDDLE 以及不自動清空數據（性能會有少許提升）
*
* @param dataCount
* 預期處理的數據規(guī)模，如預期用于處理1百萬數據的查重，這里則填寫1000000
*/
public BloomFileter(int dataCount) {
this(MisjudgmentRate.MIDDLE, dataCount, null);
}
/**
*
* @param rate
* 一個枚舉類型的誤判率
* @param dataCount
* 預期處理的數據規(guī)模，如預期用于處理1百萬數據的查重，這里則填寫1000000
* @param autoClearRate
* 自動清空過濾器內部信息的使用比率，傳null則表示不會自動清理，
* 當過濾器使用率達到100%時，則無論傳入什么數據，都會認為在數據已經存在了
* 當希望過濾器使用率達到80%時自動清空重新使用，則傳入0.8
*/
public BloomFileter(MisjudgmentRate rate, int dataCount, Double autoClearRate) {
long bitSize = rate.seeds.length * dataCount;
if (bitSize < 0 || bitSize > Integer.MAX_VALUE) {
throw new RuntimeException("位數太大溢出了，請降低誤判率或者降低數據大小");
}
this.rate = rate;
seeds = rate.seeds;
size = (int) bitSize;
notebook = new BitSet(size);
this.autoClearRate = autoClearRate;
}
public void add(String data) {
checkNeedClear();
for (int i = 0; i < seeds.length; i++) {
int index = hash(data, seeds[i]);
setTrue(index);
}
}
public boolean check(String data) {
for (int i = 0; i < seeds.length; i++) {
int index = hash(data, seeds[i]);
if (!notebook.get(index)) {
return false;
}
}
return true;
}
/**
* 如果不存在就進行記錄并返回false，如果存在了就返回true
*
* @param data
* @return
*/
public boolean addIfNotExist(String data) {
checkNeedClear();
int[] indexs = new int[seeds.length];
// 先假定存在
boolean exist = true;
int index;
for (int i = 0; i < seeds.length; i++) {
indexs[i] = index = hash(data, seeds[i]);
if (exist) {
if (!notebook.get(index)) {
// 只要有一個不存在，就可以認為整個字符串都是第一次出現的
exist = false;
// 補充之前的信息
for (int j = 0; j <= i; j++) {
setTrue(indexs[j]);
}
}
} else {
setTrue(index);
}
}
return exist;
}
private void checkNeedClear() {
if (autoClearRate != null) {
if (getUseRate() >= autoClearRate) {
synchronized (this) {
if (getUseRate() >= autoClearRate) {
notebook.clear();
useCount.set(0);
}
}
}
}
}
public void setTrue(int index) {
useCount.incrementAndGet();
notebook.set(index, true);
}
private int hash(String data, int seeds) {
char[] value = data.toCharArray();
int hash = 0;
if (value.length > 0) {
for (int i = 0; i < value.length; i++) {
hash = i * hash + value[i];
}
}
hash = hash * seeds % size;
// 防止溢出變成負數
return Math.abs(hash);
}
public double getUseRate() {
return (double) useCount.intValue() / (double) size;
}
public void saveFilterToFile(String path) {
try (ObjectOutputStream oos = new ObjectOutputStream(new FileOutputStream(path))) {
oos.writeObject(this);
} catch (Exception e) {
throw new RuntimeException(e);
}
}
public static BloomFileter readFilterFromFile(String path) {
try (ObjectInputStream ois = new ObjectInputStream(new FileInputStream(path))) {
return (BloomFileter) ois.readObject();
} catch (Exception e) {
throw new RuntimeException(e);
}
}
/**
* 清空過濾器中的記錄信息
*/
public void clear() {
useCount.set(0);
notebook.clear();
}
public MisjudgmentRate getRate() {
return rate;
}
/**
* 分配的位數越多，誤判率越低但是越占內存
*
* 4個位誤判率大概是0.14689159766308
*
* 8個位誤判率大概是0.02157714146322
*
* 16個位誤判率大概是0.00046557303372
*
* 32個位誤判率大概是0.00000021167340
*
* @author lianghaohui
*
*/
public enum MisjudgmentRate {
// 這里要選取質數，能很好的降低錯誤率
/**
* 每個字符串分配4個位
*/
VERY_SMALL(new int[] { 2, 3, 5, 7 }),
/**
* 每個字符串分配8個位
*/
SMALL(new int[] { 2, 3, 5, 7, 11, 13, 17, 19 }), //
/**
* 每個字符串分配16個位
*/
MIDDLE(new int[] { 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53 }), //
/**
* 每個字符串分配32個位
*/
HIGH(new int[] { 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97,
101, 103, 107, 109, 113, 127, 131 });
private int[] seeds;
private MisjudgmentRate(int[] seeds) {
this.seeds = seeds;
}
public int[] getSeeds() {
return seeds;
}
public void setSeeds(int[] seeds) {
this.seeds = seeds;
}
}
public static void main(String[] args) {
BloomFileter fileter = new BloomFileter(7);
System.out.println(fileter.addIfNotExist("1111111111111"));
System.out.println(fileter.addIfNotExist("2222222222222222"));
System.out.println(fileter.addIfNotExist("3333333333333333"));
System.out.println(fileter.addIfNotExist("444444444444444"));
System.out.println(fileter.addIfNotExist("5555555555555"));
System.out.println(fileter.addIfNotExist("6666666666666"));
System.out.println(fileter.addIfNotExist("1111111111111"));
fileter.saveFilterToFile("C:\\Users\\john\\Desktop\\1111\\11.obj");
fileter = readFilterFromFile("C:\\Users\\john\\Desktop\\111\\11.obj");
System.out.println(fileter.getUseRate());
System.out.println(fileter.addIfNotExist("1111111111111"));
}
}看完上述內容，你們對使用JAVA怎么實現一個布隆過濾器有進一步的了解嗎？如果還想了解更多知識或者相關內容，請關注創(chuàng)新互聯行業(yè)資訊頻道，感謝大家的支持。
