How to Build a Bloom Filter to Reduce Cache Misses in Python

import hashlib
import random

class BloomFilter:
    def __init__(self, size=100, num_hashes=3):
        self.size = size
        self.num_hashes = num_hashes
        self.bit_array = [0] * size

    def _hashes(self, item):
        result = []
        for i in range(self.num_hashes):
            hash_value = int(hashlib.md5(f"{i}:{item}".encode()).hexdigest(), 16)
            result.append(hash_value % self.size)
        return result

    def add(self, item):
        for index in self._hashes(item):
            self.bit_array[index] = 1

    def contains(self, item):
        return all(self.bit_array[index] == 1 for index in self._hashes(item))


class Cache:
    def __init__(self, capacity=5):
        self.capacity = capacity
        self.store = {}
        self.bloom = BloomFilter()


    def get(self, key):
        if key in self.store:
            print(f"CACHE HIT: {key}")
            return self.store[key]
        
        if self.bloom.contains(key):
            print(f"CACHE MISS + BLOOM POSITIVE: {key} (likely in cache but evicted)")
        else:
            print(f"CACHE MISS + BLOOM NEGATIVE: {key} (definitely not cached)")

        value = self._load_from_source(key)
        self._cache(key, value)
        return value

    def _load_from_source(self, key):
        return f"data_{key}"

    def _cache(self, key, value):
        self.store[key] = value
        self.bloom.add(key)
        if len(self.store) > self.capacity:
            evicted_key = next(iter(self.store))
            del self.store[evicted_key]
            print(f"EVICTED: {evicted_key}")


if __name__ == "__main__":
    cache = Cache(capacity=3)
    for key in ["a", "b", "c", "d", "a", "e"]:
        cache.get(key)