使用哈希表和布隆过滤器优化搜索引擎中的URL去重与存储效率

import mmh3  # 使用mmh3库作为额外的哈希函数，因为Python内置的hash()可能不足以处理布隆过滤器  
import bitarray  
  
# 初始化布隆过滤器的参数  
FILTER_SIZE = 1000000  # 位数组的大小  
HASH_FUNCS = 3  # 使用的哈希函数的数量  
  
# 使用mmh3库提供的哈希函数  
def additional_hashes(url, seed):  
    hashes = []  
    for i in range(HASH_FUNCS - 1):  # 减去1，因为我们还使用Python内置的hash()函数  
        hashes.append(mmh3.hash(url, seed + i))  
    return hashes  
  
# 初始化布隆过滤器  
bloom_filter = bitarray.bitarray(FILTER_SIZE, endian='little')  
bloom_filter.setall(False)  
  
# 哈希表用于存储唯一的URL  
url_map = {}  
  
def add_url_to_filter(url):  
    # 使用Python内置的hash函数  
    hash_value = hash(url)  
    index = hash_value % FILTER_SIZE  
    bloom_filter[index] = True  
  
    # 使用额外的哈希函数  
    additional_hashes_values = additional_hashes(url, hash_value)  
    for hash_val in additional_hashes_values:  
        index = hash_val % FILTER_SIZE  
        bloom_filter[index] = True  
  
def might_contain(url):  
    # 使用Python内置的hash函数  
    hash_value = hash(url)  
    if not bloom_filter[hash_value % FILTER_SIZE]:  
        return False  
  
    # 使用额外的哈希函数  
    additional_hashes_values = additional_hashes(url, hash_value)  
    for hash_val in additional_hashes_values:  
        if not bloom_filter[hash_val % FILTER_SIZE]:  
            return False  
  
    return True  
  
def process_urls(urls):  
    for url in urls:  
        if url not in url_map:  
            url_map[url] = True  
            add_url_to_filter(url)  
  
# 示例用法  
urls = ['https://sanzhanggui.com', 'https://sanzhanggui.com/page1', 'https://sanzhanggui.com', 'https://another-sanzhanggui.com']  
process_urls(urls)  
  
# 检查URL是否可能存在于集合中（需要注意：布隆过滤器存在误报率）  
print(might_contain('https://sanzhanggui.com'))  # 应返回True或可能返回False（误报）  
print(might_contain('https://chenchen.com'))  # 应返回False