布隆过滤器（Bloom Filters）的原理及代码实现（Python + Java）

 1 import math
 2 import random
 3 import time
 4 
 5 
 6 def hash_function(a, b, c, item, tablelen):
 7     return (a * item ** 2 + b * item + c) % tablelen  #哈希函数
 8 
 9 
10 def construction_of_SBF(tablelen = 1000, set = []):
11     
12     k = int(math.log(2, math.e) * (tablelen / len(set)))
13     hash = []
14     random.seed(time.time())
15     for i in range(k):  #随机生成哈希函数的三个参数
16         a = random.randint(1, 1000)
17         b = random.randint(1, 1000)
18         c = random.randint(1, 1000)
19         hash.append((a, b, c))
20 
21     bitArray = [0] * tablelen
22 
23     for element in set:     #映射集合元素到位数组
24         for i in range(k):
25             hx = hash_function(hash[i][0], hash[i][1], hash[i][2], element, tablelen)
26             bitArray[hx] = 1
27 
28     filter = [bitArray, hash]
29     return filter
30     
31 # 测试
32 def test_bloom_filters(bloom_filter = None):
33     if bloom_filter == None:
34         return False
35     
36     testSet = [1, 3, 7, 111, 99, 54, 34, 67, 81, 121, 101, 100, 23, 0, 845, 3339, 44]
37     for item in testSet:
38         flag = True
39         for i in range(len(filter[1])):
40             hx = hash_function(filter[1][i][0], filter[1][i][1], filter[1][i][2], item, len(filter[0]))
41             if bloom_filter[0][hx] != 1:
42                 flag = False 
43                 break
44 
45         if flag is True:
46             print("%d is in filter\n" % item)
47         else:
48             print("%d is not in filter\n" % item)
49     
50     return True
51     
52 
53 if __name__ == "__main__":
54     filter = construction_of_SBF(set = list(range(10)))
55     test_bloom_filters(filter)

  1 import math
  2 import random
  3 import time
  4 
  5 """
  6 结构没有设置好，按下写：
  7 0. 封装函数
  8 1. 哈希函数：计算哈希值
  9 2. 生成哈希随机参数函数
 10 3. 插入函数：被调用
 11 4. 删除函数：被调用
 12 5. 查询函数：测试函数调用
 13 6. 测试函数：测试插入和删除
 14 
 15 """
 16 
 17 
 18 def hash_function(params, item, tlen):
 19     return (params[0] * item ** 2 + params[1] * item + params[2]) % tlen
 20 
 21 
 22 def deletion_counting_bloom_filter(cbfilter = None, item = None):
 23     if (cbfilter is None) or (item is None):
 24         return False
 25     for params in cbfilter[2]:
 26         cbfilter[0][hash_function(params, item, len(cbfilter[0]))] -= 1
 27     return True
 28 
 29 
 30 def insertion_counting_bloom_filter(item = None, cbfilter = None):
 31     if (item == None) or (cbfilter == None):
 32         return False 
 33     for params in cbfilter[2]:
 34         cbfilter[0][hash_function(params, item, len(cbfilter[0]))] += 1
 35     return True
 36 
 37 
 38 def query_counting_bloom_filter(item = None, cbfilter = None):
 39     for params in cbfilter[2]:
 40         if(cbfilter[0][hash_function(params, item, len(cbfilter[0]))]) is 0:
 41             return False
 42     return True
 43 
 44 
 45 def construction_counting_bloom_filter(filterSet = None, filterArray = None):
 46     if (filterSet is None) or (filterArray is None):
 47         return None
 48     # 最佳的哈希函数数量
 49     hashNum = int(math.log(2, math.e) * (len(filterArray) / len(filterSet)))
 50     hashParam = []
 51     random.seed(time.time())
 52     # 随机生成哈希参数
 53     for i in range(hashNum):
 54         a = random.randint(1, 9999)
 55         b = random.randint(1, 9999)
 56         c = random.randint(1, 9999)
 57         hashParam.append((a, b, c))
 58     
 59     # 将初始集合元素映射到过滤器数组中
 60     for item in filterSet:
 61         for params in hashParam:
 62             filterArray[hash_function(params, item, len(filterArray))] += 1
 63 
 64     # 返回过滤器数组、过滤器集合、过滤器哈希参数
 65     return (filterArray, filterSet, hashParam)
 66 
 67 
 68 def test_counting_bloom_filters(cbfilter = None):
 69     if cbfilter is None:
 70         return None
 71     testSet = cbfilter[1][10:20]
 72     
 73     # 先测试原有元素是否正常映射
 74     for item in testSet:
 75         if query_counting_bloom_filter(item, cbfilter) is True:
 76             print("%d is in filter\n" % item)
 77         else:
 78             print("%d is not in filter\n" % item)
 79 
 80     # 删除后再查询
 81     if deletion_counting_bloom_filter(cbfilter, testSet[0]) is True:
 82         print("delete successfully!\n")
 83     else :
 84         print("delete fails\n")
 85 
 86     if query_counting_bloom_filter(testSet[0], cbfilter) is True:
 87         print("%d is in filter\n" % testSet[0])
 88     else :
 89         print("%d is not in filter\n" % testSet[0])
 90 
 91     # 插入后再测试
 92     if insertion_counting_bloom_filter(testSet[0], cbfilter) is True:
 93         print("insert %d successfully\n" % testSet[0])
 94     else:
 95         print("insert %d fails\n")
 96     
 97     if query_counting_bloom_filter(testSet[0], cbfilter) is True:
 98         print("%d is in filter\n" % testSet[0])
 99     else :
100         print("%d is not in filter\n" % testSet[0])
101 
102 
103 # 封装后的函数
104 def counting_bloom_filters(filterSet = None, filterArray = None):
105     if (filterSet is None) or (filterArray is None):
106         return False
107     # 构造：初始集合元素的映射、哈希函数参数生成
108     cbfilter = construction_counting_bloom_filter(filterSet, filterArray)
109 
110     # 测试：测试插入、删除、查询
111     test_counting_bloom_filters(cbfilter)
112 
113 
114 if __name__ == "__main__":
115     filterSet = list(range(100))
116     filterArray = [0] * 10000
117     counting_bloom_filters(filterSet, filterArray)

  1 // package BloomFilters;
  2 
  3 import java.util.Arrays;
  4 import java.util.Random;
  5 import java.io.*;
  6 import java.math.BigInteger;
  7 import java.nio.*;
  8 import java.nio.charset.StandardCharsets;
  9 import java.nio.file.Path;
 10 import java.util.*;
 11 
 12 /**
 13  * 实现标准布隆过滤器的类
 14  */
 15 public class SBFilters {
 16     // 实例字段
 17     private boolean[] bitArray; //位数组
 18     private int[][] hashParams; //随机的哈希函数参数
 19 
 20     // 方法字段
 21     public SBFilters(int tLen, int[] iSet)
 22     {
 23         this.bitArray = new boolean[tLen];
 24         Arrays.fill(this.bitArray, Boolean.FALSE);
 25         this.construction_filter(iSet);
 26     }
 27 
 28     private boolean construction_filter(int[] iSet)
 29     {
 30         if(iSet == null || iSet.length == 0)
 31         {
 32             return false;
 33         }
 34         var hashNum = (int)(Math.log(2) * (this.bitArray.length / iSet.length));
 35         this.construction_hashParams(hashNum);
 36         for(var item: iSet)
 37         {
 38             for(var params: this.hashParams)
 39             {
 40                 this.bitArray[hash_function(params, item)] = true;
 41             }
 42         }
 43         return true;
 44     }
 45 
 46     private boolean construction_hashParams(int hashNum)
 47     {
 48         this.hashParams = new int[hashNum][3];
 49         var time = System.currentTimeMillis();
 50         var rd = new Random(time);
 51         for(int i = 0; i < hashNum; i++)
 52         {
 53             this.hashParams[i][0] = rd.nextInt(9999) + 1;
 54             this.hashParams[i][1] = rd.nextInt(9999) + 1;
 55             this.hashParams[i][2] = rd.nextInt(9999) + 1;
 56         }
 57         return true;
 58     }
 59 
 60     private int hash_function(int[] params, int item)
 61     {
 62         return (int)((params[0] * Math.pow(item, 2.0) + 
 63             params[1] * item + params[2]) % bitArray.length);
 64     }
 65 
 66     public boolean query_filter(int item)
 67     {
 68         for(var params: this.hashParams)
 69         {
 70             if(this.bitArray[hash_function(params, item)] == false)
 71             {
 72                 return false;
 73             }
 74         }
 75         return true;
 76     }
 77     
 78 }
 79 
 80 
 81 
 82 // package BloomFilters;
 83 
 84 
 85 
 86 
 87 /**
 88  * 用来测试实现的布隆过滤器是否正常工做
 89  */
 90 public class FiltersTest
 91 {  
 92     public static void main(final String[] args) 
 93     {
 94         test_counting_bloom_filters();
 95     }
 96 
 97 
 98     private static void test_counting_bloom_filters()
 99     {
100         var iSet = new int[10000];
101         for(int i = 0; i < 10000; iSet[i] = i++);
102         SBFilters sbFilter = new SBFilters(999999, iSet);
103        
104         for(var item: new int[]{1, 3, 5, 78, 99, 100, 101, 9999, 10000, 3534})
105         {
106             var isIn = sbFilter.query_filter(item);
107             if(isIn == false)
108             {
109                 System.out.printf("%d is not in the filter\n", item);
110             }
111             else
112             {
113                 System.out.printf("%d is in the filter\n", item);
114             }
115         }
116     }
117 
118     
119 }