布隆过滤器简单实现代码,Java代码库,德仔网

代码语言

代码分类

【Java】布隆过滤器简单实现

作者:youngmk / 发布于2015/7/9/ 654

判断元素是否在某个集合中，原理和位图法相似，不存在漏判，只可能误判，常常用于检测某个元素是否是巨量数据集合中的成员


	package com.seefly.bigdata.basestruct;
	
	import java.util.List;
	/*
	* 判断元素是否在某个集合中，原理和位图法相似，不存在漏判，只可能误判，常常用于检测某个元素是否是巨量数据集合中的成员
	*/
	public class BloomFilter<E> {
	
	 //存储存储hash后的值
	 private byte[] bitGraph;
	
	 //hash函数的个数
	 private int hashNum;
	
	 //位图的长度
	 private int length;
	
	 //存放bloonHash
	 private List<BloomHash> bloomHash;
	
	 /*
	 * 这里测试，初始值比较随便，生产环境中根据元素的数量，有相应的经验公式
	 */
	 public BloomFilter(){
	 length = 512;
	 hashNum = 20;
	 // 使用改进型bloom过滤器，每4位表示一个元素, 最多能表示2^8 -1 次hash命中
	 bitGraph = new byte[length];
	 bloomHash = BloomHashCreator.produce(hashNum, length);
	 }
	
	 public boolean isExist(E element) {
	 return false;
	 }
	
	 public void insert(E element) {
	 if (element != null){
	 for ( BloomHash bh: bloomHash) {
	 int hash = bh.getBloomhash();
	 setHashBit(hash);
	 }
	 }
	 }
	
	 public void delete(E element){
	 if (element != null){
	 for ( BloomHash bh: bloomHash) {
	 int hash = bh.getBloomhash();
	 clearHashBit(hash);
	 }
	 }
	 }
	
	 public void insert(List<E> element) {
	 if (element != null) {
	 for (E e : element) {
	 this.insert(e);
	 }
	 }
	 }
	
	 private void setHashBit(int parm){
	 byte old = bitGraph[parm];
	 if(Byte.MAX_VALUE != old){
	 bitGraph[parm] = (byte) (old + 1);
	 }
	 }
	
	 private void clearHashBit(int parm){
	 byte old = bitGraph[parm];
	 if(old > 0){
	 bitGraph[parm] = (byte) (old - 1);
	 }
	 }
	}

	

	

	

	package com.seefly.bigdata.basestruct;
	
	import java.util.Random;
	
	public class BloomHash {
	
	 private int maxValue = 0 ;
	
	 private int minValue = 0;
	
	 public BloomHash(int start,int end){
	 this.maxValue = end;
	 this.minValue = start;
	 }
	
	 public int getBloomhash(){
	 return new Random().nextInt(maxValue) + minValue + 1;
	 }
	}

	

	

	package com.seefly.bigdata.basestruct;
	
	import java.util.ArrayList;
	import java.util.List;
	
	public class BloomHashCreator {
	
	
	 private BloomHashCreator(){
	
	 }
	
	 public static List<BloomHash> produce(int num,int maxValue){
	 List<BloomHash> ret = new ArrayList<BloomHash>();
	 int seg = maxValue/num;
	 int flag = maxValue%num;
	 if(flag == 0){
	 for(int i=0;i<num;i++){
	 ret.add(new BloomHash(i*seg,(i+1)*seg));
	 }
	 }else{
	 for(int i =0;i<num-1;i++){
	 ret.add(new BloomHash(i*seg,(i+1)*seg));
	 }
	 ret.add(new BloomHash((num-1)*seg,maxValue));
	 }
	 return ret;
	 }
	}

试试其它关键字

　布隆过滤器　

同语言下

可能有用的

youngmk贡献的其它代码(3)