-
Notifications
You must be signed in to change notification settings - Fork 0
/
mybloomfilter.py
35 lines (29 loc) · 1.55 KB
/
mybloomfilter.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
# -*- coding: utf-8 -*-
import hashlib
"""
布隆过滤器简单实现
实际应用的难点在于hash函数的选择(算法和个数)以及保证误报率
***************************************************************
http://www.cnblogs.com/allensun/archive/2011/02/16/1956532.html
hash函数的个数 k=0.6185*m/n 时误报率最低(m: 数组长度, n: 元素个数)
---------------------------------------------------------------
@datetime: 2018/6/14 15:33
"""
class MyBloomFilter:
def __init__(self, size):
# 选取一些值生成不同hash函数
self.__seeds = [2, 3, 5, 7, 11, 13, 17, 19]
self.size = size
self.bf = [False]*size
def add(self, text):
for p in self.make_hashs(text):
# 将hash函数对应位置赋值为True
self.bf[p] = True
def __contains__(self, text):
# 判断是否所有hash函数都落在数组上,如果都落在数组上即该元素很可能在集合中。如不全落在数组上,那么该元素一定不在集合中
return all([self.bf[p] for p in self.make_hashs(text)])
def make_hashs(self, text):
# int(hashlib.md5((str(seed)+text).encode('utf-8')).hexdigest(), 16) % self.size
# 拼接seed和待处理字符串,获取其md5值并转换为10进制整型,用数组长度取余数,即获得该hash函数在数组上对应的位置
# !! md5的离散程度好像不够高,可以换用其他hash算法
return [int(hashlib.md5((str(seed)+text).encode('utf-8')).hexdigest(), 16) % self.size for seed in self.__seeds]