一个简单的内存布隆过滤器

import hashlib
from bitarray import bitarray

class BloomFilter:
    def __init__(self, size, hash_count):
        self.size = size
        self.hash_count = hash_count
        self.bit_array = bitarray(size)
        self.bit_array.setall(0)
    
    def add(self, item):
        for i in range(self.hash_count):
            digest = hashlib.md5((str(item) + str(i)).encode()).hexdigest()
            index = int(digest, 16) % self.size
            self.bit_array[index] = 1
    
    def contains(self, item):
        for i in range(self.hash_count):
            digest = hashlib.md5((str(item) + str(i)).encode()).hexdigest()
            index = int(digest, 16) % self.size
            if not self.bit_array[index]:
                return False
        return True

def deduplicate_large_file(input_file, output_file):
    # 布隆过滤器参数：10亿位，7个哈希函数（误判率约0.008%）
    bloom = BloomFilter(size=1000000000, hash_count=7)
    
    with open(input_file, 'r', encoding='utf-8') as f_in, \
         open(output_file, 'w', encoding='utf-8') as f_out:
        
        for line in f_in:
            url = line.strip()
            if not bloom.contains(url):
                bloom.add(url)
                f_out.write(line)

# 使用
deduplicate_large_file('urls.txt', 'deduplicated_urls.txt')