博文参考
问题背景
面试官：10亿URL + 100M内存空间 + 实现一个高效的过滤器。
我：这是一个典型的位图法处理海量数据的问题，具体可使用布隆过滤器求解。
具体介绍
布隆过滤器（英语：Bloom Filter）是1970年由
布隆提出的。原理：实际上是一个很长的
二进制矢量和一系列随机映射函数。作用：可以用于
检索一个元素是否在一个集合中。优点：
空间效率和查询时间都远远超过一般的算法。缺点：有一定的
误识别率和删除困难。基本思想：当一个元素被加入集合时，通过K个散列函数将这个元素映射成一个
位数组中的K个点，把它们置为1。检索时，我们只要看看这些点是不是都是1就（大约）知道集合中有没有它了；如果这些点有任何一个0，则被检元素一定不在；如果都是1，则被检元素很可能在。
解决方法
第一步，利用一个整型数组构建一个位数组；
private BitSet bits = new BitSet(DEFAULT_SIZE);
第二步，将数据元素（可能是字符串URL、垃圾邮件发送者的Email等）经过K个哈希函数处理，得到K个哈希值；
for (int i = 0; i < seeds.length; i++) {
func[i] = new SimpleHash(DEFAULT_SIZE, seeds[i]);
}
第三步，根据哈希值进行位数组的置位，其中哈希值表示位数组的索引；
for (SimpleHash f : func) {
bits.set(f.hash(value), true);
}
第四步，根据哈希值的置位情况判断元素是够重复出现。
public boolean contains(String value) {
if (value == null) {
return false;
}
boolean ret = true;
for (SimpleHash f : func) {
ret = ret && bits.get(f.hash(value));
}
return ret;
}
相似案例
海量的电话号码，要求统计不同电话号码的个数。
垃圾邮件黑名单。
BitSet源码
/**
* Sets the bit at the specified index to the specified value.
*
* @param bitIndex a bit index
* @param value a boolean value to set
* @throws IndexOutOfBoundsException if the specified index is negative
* @since 1.4
*/
public void set(int bitIndex, boolean value) {
if (value)
set(bitIndex);
else
clear(bitIndex);
}
/**
* Sets the bit at the specified index to {@code true}.
*
* @param bitIndex a bit index
* @throws IndexOutOfBoundsException if the specified index is negative
* @since JDK1.0
*/
public void set(int bitIndex) {
if (bitIndex < 0)
throw new IndexOutOfBoundsException("bitIndex < 0: " + bitIndex);
...
words[wordIndex] |= (1L << bitIndex); // Restores invariants
...
}
/**
* Sets the bit specified by the index to {@code false}.
*
* @param bitIndex the index of the bit to be cleared
* @throws IndexOutOfBoundsException if the specified index is negative
* @since JDK1.0
*/
public void clear(int bitIndex) {
if (bitIndex < 0)
throw new IndexOutOfBoundsException("bitIndex < 0: " + bitIndex);
...
words[wordIndex] &= ~(1L << bitIndex);
...
}
/**
* Returns the value of the bit with the specified index. The value
* is {@code true} if the bit with the index {@code bitIndex}
* is currently set in this {@code BitSet}; otherwise, the result
* is {@code false}.
*
* @param bitIndex the bit index
* @return the value of the bit with the specified index
* @throws IndexOutOfBoundsException if the specified index is negative
*/
public boolean get(int bitIndex) {
if (bitIndex < 0)
throw new IndexOutOfBoundsException("bitIndex < 0: " + bitIndex);
...
int wordIndex = wordIndex(bitIndex);
return (wordIndex < wordsInUse)
&& ((words[wordIndex] & (1L << bitIndex)) != 0);
}