Skip to content

Instantly share code, notes, and snippets.

@okabe-yuya
Created May 1, 2022 03:25
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save okabe-yuya/5dc511bcc7e257c8d839dffefa06f939 to your computer and use it in GitHub Desktop.
Save okabe-yuya/5dc511bcc7e257c8d839dffefa06f939 to your computer and use it in GitHub Desktop.
implement bloom filter by python3
import functools
class BloomFilter:
def __init__(self, filter_size):
self.filter_size = filter_size
self.bloom_filter = [0 for _ in range(filter_size)]
def exist_v(self, val):
indexes = self.n_hash(val)
for index in indexes:
if self.bloom_filter[index] == 0:
return False
return True
def set_v(self, val):
indexes = self.n_hash(val)
for index in indexes:
self.bloom_filter[index] = 1
def n_hash(self, val):
hashed = abs(hash(val))
d_list = [int(n) for n in str(hashed)]
return [
self._hash_common(lambda acc, d: acc + d, d_list),
self._hash_common(lambda acc, d: acc + 2 * d, d_list),
]
def _hash_common(self, func, d_lst):
execed = abs(functools.reduce(func, d_lst, 0))
while execed >= self.filter_size:
execed = execed / self.filter_size
return int(execed)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment