使用布隆过滤器，我们将获得空间优化。cassandra 框架也有一个布隆过滤器的实现。但具体来说，这个空间优化是如何实现的呢？
问问题
17395 次
6 回答
18
您可以使用此示例了解它如何节省空间：假设我在 Chrome 团队中为 Google 工作，我想向浏览器添加一个功能，如果他输入的 URL 是恶意 URL，它会通知用户。所以我有一个包含大约 100 万个恶意 URL 的数据集，这个文件的大小约为 25MB。由于大小相当大（与浏览器本身的大小相比很大），我将这些数据存储在远程服务器上。
案例 1：我使用带有哈希表的哈希函数。我决定使用一个高效的散列函数，并通过散列函数运行所有 100 万个 url 以获取散列键。然后，我制作了一个哈希表（一个数组），其中哈希键将为我提供放置该 URL 的索引。所以现在一旦我散列并填充了散列表，我检查它的大小。我已将所有 100 万个 URL 连同它们的键一起存储在哈希表中。所以大小至少为 25 MB。这个哈希表，由于它的大小，将存储在远程服务器上。当用户出现并在地址栏中输入网址时，我需要检查它是否是恶意的。因此，我通过哈希函数运行 url（浏览器本身可以执行此操作）并获得该 URL 的哈希键。我现在必须使用该哈希键向我的远程服务器发出请求，检查我的哈希表中的特定 URL 是否与用户输入的相同。如果是，那么它是恶意的，如果不是，那么它不是恶意的。因此，每次用户输入 URL 时，都必须向远程服务器发出请求以检查它是否是恶意 URL。这将花费大量时间，从而使我的浏览器变慢。
案例 2：我使用布隆过滤器。100 万个 URL 的整个列表使用多个哈希函数通过布隆过滤器运行，并且各自的位置标记为 1，在一个巨大的 0 数组中。假设我们想要 1% 的误报率，使用布隆过滤器计算器 ( http://hur.st/bloomfilter?n=1000000&p=0.01) ，我们得到所需的布隆过滤器大小仅为 1.13 MB。这个小尺寸是预期的，因为即使数组的大小很大，我们也只存储 1 或 0，而不像哈希表那样存储 URL。这个数组可以被视为一个位数组。也就是说，由于我们只有两个值 1 和 0，我们可以设置单个位而不是字节。这将使占用的空间减少 8 倍。这个 1.13 MB 的布隆过滤器，由于其体积小，可以存储在网络浏览器本身！因此，当用户出现并输入 URL 时，我们只需应用所需的哈希函数（在浏览器本身中），并检查布隆过滤器（存储在浏览器中）中的所有位置。任何位置的值 0 都告诉我们此 URL 绝对不在恶意 URL 列表中，用户可以自由继续。因此，我们没有调用服务器，从而节省了时间。值 1 告诉我们该 url 可能在恶意 URL 列表中。在这些情况下，我们调用远程服务器，在那里我们可以像第一种情况一样使用带有哈希表的其他哈希函数来检索并检查 url 是否实际存在。由于大多数情况下，一个 url 不太可能是恶意的，浏览器中的小型布隆过滤器会发现这一点，从而通过避免调用远程服务器来节省时间。只有在某些情况下，如果布隆过滤器告诉我们 url 可能是恶意的，只有在这些情况下，我们才会调用服务器。这个“可能”是 99% 正确的。在这些情况下，我们调用远程服务器，在那里我们可以像第一种情况一样使用带有哈希表的其他哈希函数来检索并检查 url 是否实际存在。由于大多数情况下，一个 url 不太可能是恶意的，浏览器中的小型布隆过滤器会发现这一点，从而通过避免调用远程服务器来节省时间。只有在某些情况下，如果布隆过滤器告诉我们 url 可能是恶意的，只有在这些情况下，我们才会调用服务器。这个“可能”是 99% 正确的。在这些情况下，我们调用远程服务器，在那里我们可以像第一种情况一样使用带有哈希表的其他哈希函数来检索并检查 url 是否实际存在。由于大多数情况下，一个 url 不太可能是恶意的，浏览器中的小型布隆过滤器会发现这一点，从而通过避免调用远程服务器来节省时间。只有在某些情况下，如果布隆过滤器告诉我们 url 可能是恶意的，只有在这些情况下，我们才会调用服务器。这个“可能”是 99% 正确的。浏览器中的小布隆过滤器可以解决这个问题，因此通过避免调用远程服务器来节省时间。只有在某些情况下，如果布隆过滤器告诉我们 url 可能是恶意的，只有在这些情况下，我们才会调用服务器。这个“可能”是 99% 正确的。浏览器中的小布隆过滤器可以解决这个问题，因此通过避免调用远程服务器来节省时间。只有在某些情况下，如果布隆过滤器告诉我们 url 可能是恶意的，只有在这些情况下，我们才会调用服务器。这个“可能”是 99% 正确的。
因此，通过在浏览器中使用小型布隆过滤器，我们节省了大量时间，因为我们不需要为输入的每个 url 进行服务器调用。
于 2015-05-15T11:20:36.163 回答
5
所以我以前见过这个问题，我使用了上面的建议，结果证明这对我来说是一种放慢速度的方式。所以我自己写了。它不是完全通用的，但我敢肯定，如果有人像我一样迫切需要性能，他们会自己使它更通用:)
我使用了你可以在这里下载的 Murmur 哈希实现：http: //d3s.mff.cuni.cz/~holub/sw/javamurmurhash/
代码：包uk.ac.cam.cl.ss958.SpringBoardSimulation；
import ie.ucd.murmur.MurmurHash;
import java.util.BitSet;
import java.util.Random;
public class FastBloomFilter {
private final BitSet bs;
final int [] hashSeeds;
final int capacity;
public FastBloomFilter(int slots, int hashFunctions) {
bs = new BitSet(slots);
Random r = new Random(System.currentTimeMillis());
hashSeeds = new int[hashFunctions];
for (int i=0; i<hashFunctions; ++i) {
hashSeeds[i] = r.nextInt();
}
capacity = slots;
}
public void add(int value) {
byte [] b = new byte[] {
(byte)(value >>> 24),
(byte)(value >>> 16),
(byte)(value >>> 8),
(byte)value};
for (int i=0; i<hashSeeds.length; ++i) {
int h = MurmurHash.hash32(b, 4, hashSeeds[i]);
bs.set(Math.abs(h)%capacity, true);
}
}
public void clear() {
bs.clear();
}
public boolean mightContain(int value) {
byte [] b = new byte[] {
(byte)(value >>> 24),
(byte)(value >>> 16),
(byte)(value >>> 8),
(byte)value};
for (int i=0; i<hashSeeds.length; ++i) {
int h = MurmurHash.hash32(b, 4, hashSeeds[i]);
if(!bs.get(Math.abs(h)%capacity)) {
return false;
}
return true;
}
public static void main(String [] args) {
FastBloomFilter bf = new FastBloomFilter(1000, 10);
System.out.println("Query for 2000: " + bf.mightContain(2000));
System.out.println("Adding 2000");
bf.add(2000);
System.out.println("Query for 2000: " + bf.mightContain(2000));
}
}
于 2013-05-09T15:14:14.737 回答
3
布隆过滤器不是“框架”。它真的更像是一个简单的算法。实施时间不会很长。
这是我尝试过的 Java 中的一个（.jar、源代码和 JavaDoc 都可用）：
“Cuckoo Hashing 和 Bloom Filters 的独立 Java 实现”（如果以下链接不再有效，您可能需要谷歌搜索）：
于 2010-12-28T13:44:09.483 回答
1
您可以将基于Redis服务器的 Bloom 过滤器与Redisson库一起使用。基于 128 位HighwayHash。这是一个例子：
RBloomFilter<SomeObject> bloomFilter = redisson.getBloomFilter("sample");
// initialize bloom filter once with
// expectedInsertions = 55000000
// falseProbability = 0.03
bloomFilter.tryInit(55000000L, 0.03);
bloomFilter.add(new SomeObject(someStateHere1));
bloomFilter.add(new SomeObject(someStateHere2));
// does it contain object?
bloomFilter.contains(new SomeObject(someStateHere3));
于 2016-01-22T14:34:58.023 回答
1
我写了一篇关于使用 Java 8 特性实现布隆过滤器的短文，我希望它与节省空间的问题有关。当一些信息检索系统会这样做时，我进一步讨论了如何对一组布隆过滤器进行位切片，当您拥有大量布隆过滤器时，这与效率相关。
于 2017-11-06T02:29:19.357 回答
0
布隆过滤器是概率数据结构，可以在 O(1) 时间内告诉您数据库中是否存在条目。但是，它可能会给出一些误报。但是，通过正确选择散列函数和位阵列的大小，正确的结果的百分比可以高达99.99％。每当数据库中有条目时，您还可以通过将哈希函数返回的那些索引上的位设置为 1 来填充布隆。散列函数返回位数组的开始和结束索引之间的值。无论哈希函数返回什么值，位数组中的这些位都设置为 1。在查找期间，查询参数再次通过相同的哈希函数传递。如果所有位都设置为 1，则数据有可能存在于数据库中。如果任何位为 0，则该条目肯定不存在于数据库中。下面是简单布隆过滤器的代码
import java.util.HashSet;
import java.util.Random;
public class Bloom {
static int bloom[]= new int[10000];
static HashSet<Integer> set=new HashSet<Integer>();
static int result[]= new int[4];
// truepositive,truenegative,falsepositive,falsenegative
public static void main(String[] args) {
populate();
getLookUpResult();
for(int i : result){
System.out.println(i);
}
}
static void populate(){
for(int i=0;i<1000;i++){
int numb=getRandom(0,2000);
set.add(numb);
int h1=(numb*numb*3)%2000;
bloom[h1]=1;
int h2=(numb*19)%2000;
bloom[h2]=1;
int h3=(numb*numb)%2000;
bloom[h3]=1;
}
}
public static int getRandom(int l,int h){
Random r = new Random();
int low = l;
int high = h;
int result = r.nextInt(high-low) + low;
return result;
}
public static void getLookUpResult(){
for(int i=0;i<2000;i++){
if(isPresent(i)){
if(set.contains(i)){ // true positive
result[0]++;
}
else{ // false positive
result[2]++;
}
}else{
if(set.contains(i)){ // falsenegative
result[3]++;
}
else{
result[1]++; //true negative
}
}
}
}
public static boolean isPresent(int number){
int h1=(number*number*number)%2000;
int h2=(number*19)%2000;
int h3=(number*number)%2000;
return (bloom[h1]==1 && bloom[h2]==1 && bloom[h3]==1);
}
} `
于 2021-03-15T07:15:44.077 回答