前言

当涉及海量数据去重时，Hash、Bloom Filter和Bitmap都是常用的技术。

Hash方法

Hash方法使用哈希函数将数据映射到一个固定大小的散列值，然后将这些散列值存储在一个散列表中，以检查是否已经存在相同的值。

class HashDeduplication:
    def __init__(self):
        self.hash_set = set()

    def add(self, value):
        hash_value = hash(value)
        self.hash_set.add(hash_value)

    def contains(self, value):
        hash_value = hash(value)
        return hash_value in self.hash_set

# 使用示例
hash_dedup = HashDeduplication()
data = [1, 2, 3, 4, 5, 1, 6, 7, 8, 2]

for item in data:
    if not hash_dedup.contains(item):
        hash_dedup.add(item)
        print(f"Added: {item}")
    else:
        print(f"Duplicate: {item}")

Bloom Filter方法

Bloom Filter是一种概率性的数据结构，它使用多个哈希函数将数据映射到一个位数组中，用于快速检测元素是否存在。由于存在一定的误报率，它适用于数据量较大的情况。

import hashlib
import mmh3
import bitarray

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

    def add(self, value):
        for seed in range(self.hash_count):
            index = mmh3.hash(value, seed) % self.size
            self.bit_array[index] = 1

    def contains(self, value):
        for seed in range(self.hash_count):
            index = mmh3.hash(value, seed) % self.size
            if not self.bit_array[index]:
                return False
        return True

# 使用示例
bloom_filter = BloomFilter(size=100, hash_count=3)
data = [1, 2, 3, 4, 5, 1, 6, 7, 8, 2]

for item in data:
    if not bloom_filter.contains(item):
        bloom_filter.add(item)
        print(f"Added: {item}")
    else:
        print(f"Duplicate (or potential false positive): {item}")

Bitmap方法

Bitmap使用固定数量的位来表示数据的存在与否，适用于数据集合有限且范围可知的情况。

class BitmapDeduplication:
    def __init__(self, max_value):
        self.bitmap = [0] * (max_value + 1)

    def add(self, value):
        self.bitmap[value] = 1

    def contains(self, value):
        return self.bitmap[value] == 1

# 使用示例
bitmap_dedup = BitmapDeduplication(max_value=10)
data = [1, 2, 3, 4, 5, 1, 6, 7, 8, 2]

for item in data:
    if not bitmap_dedup.contains(item):
        bitmap_dedup.add(item)
        print(f"Added: {item}")
    else:
        print(f"Duplicate: {item}")