DEV Community

drake
drake

Posted on

算法:bloom过滤器单机版

from bitarray import bitarray
import mmh3


class BloomFilter:
    def __init__(self, size: int = 100_000_000, hash_count: int = 7):
        self.size = size
        self.hash_count = hash_count
        self.bit_array = bitarray(size)
        self.bit_array.setall(0)


    def _get_hash_positions(self, url: str) -> list[int]:
        """
        ge
        Args:
            url: The URL to get the hash positions for.
        Returns:
            A list of hash positions.
        """
        positions = []
        for seed in range(self.hash_count):
            index = mmh3.hash(url, seed) % self.size
            positions.append(index)
        return positions

    def add(self, url: str) -> bool:
        for pos in self._get_hash_positions(url):
            if not self.bit_array[pos]:
                self.bit_array[pos] = 1
            else:
                return False
        return True

    def contains(self, url: str) -> bool:
        return all(self.bit_array[pos] for pos in self._get_hash_positions(url))




bloom_filter = BloomFilter(size=100_000_000, hash_count=7)
urls = [
    "https://example.com/page/1",
    "https://example.com/page/2",
    "https://example.com/page/1",
]
for url in urls:
    exists = bloom_filter.contains(url)
    if exists:
        print(f"URL {url} already exists in bloom filter")
        continue
    add_success = bloom_filter.add(url)
    if not add_success:
        print(f"URL {url} already exists in bloom filter")


Enter fullscreen mode Exit fullscreen mode

Top comments (0)