public class BloomFilter {
private int[] table;
private int[] seeds = {1, 3};
public BloomFilter(int capacity) {
capacity = resizeCapacity(capacity);
this.table = new int[capacity];
}
private int resizeCapacity(int capacity) {
int n = 0;
Double result = 0d;
while (result < capacity) {
result = Math.pow(2, n++);
}
return result.intValue();
}
private boolean checkBitStatus(int index) {
int intIndex = index / 32;
int stepIndex = index % 32;
return ((table[intIndex] >> stepIndex) & 1) == 1;
}
private void setBitStatus(int index) {
int intIndex = index / 32;
int stepIndex = index % 32;
table[intIndex] = (1 << stepIndex | table[intIndex]);
}
public void addElement(String e) {
for(int seed: seeds) {
int index = hash(e, seed);
setBitStatus(index);
}
}
public boolean checkElement(String e) {
for(int seed: seeds) {
int index = hash(e, seed);
if (!checkBitStatus(index)) {
return false;
}
}
return true;
}
private int hash(String element, int speed) {
return element.hashCode() & (table.length * 32 - 1) & speed;
}
public static void main(String[] args) {
BloomFilter bloomFilter = new BloomFilter(5);
bloomFilter.addElement("ss");
System.out.println(bloomFilter.checkElement("ss"));
System.out.println(bloomFilter.checkElement("s"));
bloomFilter.addElement("s");
System.out.println(bloomFilter.checkElement("s"));
}
}
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)