luminousmen · January 31, 2023 22:40 · Jan 31, 2023 · Jan 31, 2023 · Jan 31, 2023
diff --git a/bloom.py → bloom_1.py b/bloom.py → bloom_1.py
diff --git a/bloom_2.py b/bloom_2.py
@@ -0,0 +1,47 @@
+import hashlib
+
+class BloomFilter:
+    def __init__(self, size, num_hashes, salt=None):
+        self.size = size
+        self.num_hashes = num_hashes
+        self.salt = salt or ''
+        self.bit_array = [0] * size
+
+    def add(self, element):
+        for i in range(self.num_hashes):
+            digest = hashlib.sha1((self.salt + str(element) + str(i)).encode('utf-8')).hexdigest()
+            index = int(digest, 16) % self.size
+            self.bit_array[index] = 1
+
+    def __contains__(self, element):
+        for i in range(self.num_hashes):
+            digest = hashlib.sha1((self.salt + str(element) + str(i)).encode('utf-8')).hexdigest()
+            index = int(digest, 16) % self.size
+            if self.bit_array[index] == 0:
+                return False
+        return True
+        for h in self.calculate_hash(value):
+            if not self.bitmap[h]:
+                return False
+        return True
+
+
+if __name__ == "__main__":
+    coffees = [
+        "Iced Coffee",
+        "Iced Coffee with Milk",
+        "Espresso",
+        "Espresso Macchiato",
+        "Flat White",
+        "Latte Macchiato",
+        "Cappuccino",
+        "Mocha",
+    ]
+
+    bloom = BloomFilter(20, 2)
+    for drink in coffees:
+        bloom.add(drink)
+        print(bloom.bit_array)
+
+    print("Flat White" in bloom)
+    print("Americano" in bloom)
diff --git a/bloom.py b/bloom.py
@@ -0,0 +1,60 @@
+# Hash implementations from
+# http://www.partow.net/programming/hashfunctions/index.html
+# Author: @luminousmen
+
+class BloomFilter:
+    def __init__(self, size: int):
+        self.size = size
+        self.bitmap = size * [0]
+
+    def FNV(self, key: str):
+        fnv_prime = 0x811C9DC5
+        hash = 0
+        for i in range(len(key)):
+            hash *= fnv_prime
+            hash ^= ord(key[i])
+        return hash
+
+    def DJB(self, key: str):
+        hash = 5381
+        for i in range(len(key)):
+            hash = ((hash << 5) + hash) + ord(key[i])
+        return hash
+
+    def calculate_hash(self, value):
+        # FNV
+        hash1 = self.FNV(value) % self.size
+        # MurMur
+        hash2 = self.DJB(value) % self.size
+        return hash1, hash2
+
+    def add(self, value: str):
+        for h in self.calculate_hash(value):
+            self.bitmap[h] = 1
+
+    def check(self, value):
+        for h in self.calculate_hash(value):
+            if not self.bitmap[h]:
+                return False
+        return True
+
+
+if __name__ == "__main__":
+    coffees = [
+        "Iced Coffee",
+        "Iced Coffee with Milk",
+        "Espresso",
+        "Espresso Macchiato",
+        "Flat White",
+        "Latte Macchiato",
+        "Americano",
+        "Mocha",
+    ]
+
+    bloom = BloomFilter(20)
+    for drink in coffees:
+        bloom.add(drink)
+        print(bloom.bitmap)
+
+    print(bloom.check("Flat White"))
+    print(bloom.check("Cappuccino"))