Bloom Filter算法優化

1. 基于Redis的Bloom Filter去重，利用Redis的String資料結構，但Redis的String最大隻能512M，是以資料過大的時候，需要申請多個去重塊。
2. Bloom Filter對一個很長的字元串進行哈希映射時會出錯，常誤判為已經存在，是以我們進行一次壓縮(MD5\Sha1)。
3. 将去重隊列和種子隊列拆分到不同的機器上。

種子seed數量越少去重速度越快，但是漏失率越大。

Md5長度為128bit，SHA-1長度160bit。

from redis import StrictRedis
from hashlib import md5


class HashMap(object):

    def __init__(self, m, seed):
        self.m = m
        self.seed = seed

    def hash(self, value):
        ret = 0
        for i in range(len(value)):
            ret += self.seed * ret + ord(value[i])
        return (self.m - 1) & ret


class BloomFilter(object):

    def __init__(self, server, key, blockNum=1, bit=30, hash_number=6):
        self.m = 1 << bit
        self.seeds = range(hash_number)     # 種子
        self.blockNum = blockNum    # 去重塊的數量
        self.maps = [HashMap(self.m, seed) for seed in self.seeds]  # 多個哈希函數
        self.server = server    # Redis連接配接對象
        self.key = key  # 鍵名

    def exists(self, value):
        if not value:
            return False
        m5 = md5()
        m5.update(value.encode())
        value_md5 = m5.hexdigest()  # 将value進行md5加密
        ret = True
        key_name = self.key + \
            str(int(value_md5[0:2], 16) % self.blockNum)  # 存儲的block位置
        for map in self.maps:
            offset = map.hash(value_md5)  # hash md5加密後的資料
            ret = ret & self.server.getbit(
                key_name, offset)  # 修改每次hash過後，指定block塊的位置
        return ret

    def insert(self, value):
        m5 = md5()
        m5.update(value.encode())
        value_md5 = m5.hexdigest()  # 将vlaue進行md5加密
        key_name = self.key + \
            str(int(value_md5[0:2], 16) % self.blockNum)  # 存儲的block位置
        for map in self.maps:
            offset = map.hash(value_md5)  # hash md5加密後的資料
            self.server.setbit(key_name, offset, 1)

redis = StrictRedis(host='localhost', port=6379)
bf = BloomFilter(redis, 'hash_map', 3, 10, 1)
# bf.insert('asd')
print(bf.exists('asd'))
# bf.insert('Hellow')
# bf.insert('World')