记一次面试被问到的布隆过滤器(能不能叫布罗姆过滤器...) 如何代码简单实现
程序员文章站
2022-04-15 17:56:32
先贴代码,注释挺全的,后续写一点解释,不过好像也解释不太出啥来。。package com.project.test;import java.util.BitSet;public class BloomFilter { //初始化位数组时的大小 private static int INITIAL_CAPACITY = 2 << 24; //构造哈希函数的种子数组 private static int[] seeds = {8,18,28,38};...
先贴代码,注释挺全的,后续写一点解释,不过好像也解释不太出啥来。。
package com.project.test;
import java.util.BitSet;
public class BloomFilter {
//初始化位数组时的大小
private static int INITIAL_CAPACITY = 2 << 24;
//构造哈希函数的种子数组
private static int[] seeds = {8,18,28,38};
//用默认大小初始化一个位数组
private BitSet bitSet = new BitSet(INITIAL_CAPACITY);
//私有一个哈希函数数组
private HashFunction[] hashFunctions = new HashFunction[seeds.length];
//构造函数时,填充哈希数组
public BloomFilter(){
for (int i = 0; i < seeds.length; i++) {
hashFunctions[i] = new HashFunction(seeds[i],INITIAL_CAPACITY);
}
}
/**
* 向位数组里添加某个字符串
* @param value 待添加的字符串
* @return true 如果添加成功 false 则添加失败
*/
public boolean add(String value){
//value为null,直接false
if (value == null){
return false;
}
try {
//遍历哈希函数数组,用每个函数映射一遍value得到位数组索引
for (int i = 0; i < hashFunctions.length; i++) {
int index = hashFunctions[i].hash(value);
//将位数组对应索引置为true/false
bitSet.set(index,true);
}
return true;
} catch (Exception e) {
e.printStackTrace();
return false;
}
}
/**
* 判断某个字符串是否在位数组里
* @param value 带判断的字符串
* @return true 字符串(可能!)已经存在位数组中 false 字符串一定不存在位数组中
*/
public boolean contains(String value){
//value为null,直接false
if (value == null){
return false;
}
for (int i = 0; i < hashFunctions.length; i++) {
int index = hashFunctions[i].hash(value);
//拿到对应索引true/false
boolean temp = bitSet.get(index);
//有一个false,直接返回,肯定不在
if (!temp){
return false;
}
}
return true;
}
/**
* 静态内部类
* 用于定义函数,计算哈希,压缩哈希,得到索引
*/
private static class HashFunction{
//种子
private int seed;
//位数组容量 INITIAL_CAPACITY
private int capacity;
//构造哈希函数
public HashFunction() {
}
public HashFunction(int seed, int capacity) {
this.seed = seed;
this.capacity = capacity;
}
/**
* 计算哈希值,压缩哈希值得到索引
* @param value 待计算的字符串
* @return
*/
private int hash(String value){
//遍历字符串每个字符,计算哈希值
int result = 0;
for (int i = 0; i < value.length(); i++) {
result = seed * result + value.charAt(i);
}
//压缩哈希值到索引
//result为长哈希值,压缩
//当N为2的整数次幂时,result对N取余 result % N 等价于 result & (N - 1)
result = result & (capacity - 1);
return result;
}
}
public static void main(String[] args) {
BloomFilter bf = new BloomFilter();
System.out.println(bf.contains("苹果"));
System.out.println(bf.contains("香蕉"));
System.out.println(bf.contains("橘子"));
System.out.println(bf.contains("蛋糕"));
System.out.println(bf.contains("巧克力"));
System.out.println("+++++++++++++++++++++++");
bf.add("苹果");
bf.add("香蕉");
bf.add("橘子");
bf.add("蛋糕");
bf.add("巧克力");
System.out.println(bf.contains("苹果"));
System.out.println(bf.contains("香蕉"));
System.out.println(bf.contains("橘子"));
System.out.println(bf.contains("蛋糕"));
System.out.println(bf.contains("巧克力"));
System.out.println("~~~~~~~~~~~~~~~~~~~~~~~~~~~");
System.out.println(bf.contains("车子"));
System.out.println(bf.contains("曼联"));
System.out.println(bf.contains("切尔西"));
System.out.println(bf.contains("渣团"));
System.out.println(bf.contains("拜仁"));
System.out.println("@@@@@@@@@@@@@@@@@@@@@@@@");
}
}
本文地址:https://blog.csdn.net/weixin_40821240/article/details/109819134
上一篇: Java数据结构算法,快速排序算法