布谷鸟过滤器

import java.util.Random;

/**
 * 布谷鸟过滤器实现
 */
public class CuckooFilter {
    private static final int DEFAULT_CAPACITY = 1000000;
    private static final int BUCKET_SIZE = 4;
    private static final int MAX_KICKS = 500;
    private static final int FINGERPRINT_BITS = 8;

    private final byte[][] buckets;
    private final int capacity;
    private final Random random = new Random();

    /**
     * 使用默认容量构造过滤器
     */
    public CuckooFilter() {
        this(DEFAULT_CAPACITY);
    }

    /**
     * 指定初始容量构造过滤器
     * @param capacity 过滤器容量
     */
    public CuckooFilter(int capacity) {
        this.capacity = capacity;
        this.buckets = new byte[capacity][BUCKET_SIZE];
    }

    /**
     * 计算元素的指纹
     */
    private byte fingerprint(byte[] data) {
        // 使用简单哈希算法生成指纹（实际应使用更好的哈希函数）
        int hash = 0;
        for (byte b : data) {
            hash = (hash * 31) + b;
        }
        return (byte) (hash & ((1 << FINGERPRINT_BITS) - 1));
    }

    /**
     * 获取两个候选桶位置
     */
    private int[] getBuckets(byte[] data) {
        int h1 = Math.abs(data.hashCode()) % capacity;
        int h2 = (h1 ^ (fingerprint(data) & 0xFF)) % capacity;
        return new int[]{h1, h2};
    }

    /**
     * 插入元素
     * @return true表示插入成功，false表示插入失败
     */
    public boolean insert(byte[] data) {
        byte f = fingerprint(data);
        int[] indexes = getBuckets(data);

        // 尝试插入第一个候选桶
        if (insertToBucket(indexes[0], f)) {
            return true;
        }

        // 尝试插入第二个候选桶
        if (insertToBucket(indexes[1], f)) {
            return true;
        }

        // 需要执行踢出操作
        int index = random.nextBoolean() ? indexes[0] : indexes[1];
        for (int i = 0; i < MAX_KICKS; i++) {
            int pos = random.nextInt(BUCKET_SIZE);
            byte oldFingerprint = buckets[index][pos];
            buckets[index][pos] = f;
            f = oldFingerprint;

            // 计算新位置
            index = (index ^ (f & 0xFF)) % capacity;
            if (insertToBucket(index, f)) {
                return true;
            }
        }
        return false;
    }

    private boolean insertToBucket(int index, byte f) {
        for (int i = 0; i < BUCKET_SIZE; i++) {
            if (buckets[index][i] == 0) {
                buckets[index][i] = f;
                return true;
            }
        }
        return false;
    }

    /**
     * 检查元素是否存在
     */
    public boolean contains(byte[] data) {
        byte f = fingerprint(data);
        int[] indexes = getBuckets(data);
        return checkBucket(indexes[0], f) || checkBucket(indexes[1], f);
    }

    private boolean checkBucket(int index, byte f) {
        for (int i = 0; i < BUCKET_SIZE; i++) {
            if (buckets[index][i] == f) {
                return true;
            }
        }
        return false;
    }

    /**
     * 删除元素
     */
    public boolean delete(byte[] data) {
        byte f = fingerprint(data);
        int[] indexes = getBuckets(data);
        return removeFromBucket(indexes[0], f) || removeFromBucket(indexes[1], f);
    }

    private boolean removeFromBucket(int index, byte f) {
        for (int i = 0; i < BUCKET_SIZE; i++) {
            if (buckets[index][i] == f) {
                buckets[index][i] = 0;
                return true;
            }
        }
        return false;
    }

    public static void main(String[] args) {
        CuckooFilter filter = new CuckooFilter(1000);
        byte[] data1 = "test1".getBytes();
        byte[] data2 = "test2".getBytes();

        filter.insert(data1);
        System.out.println("Contains test1: " + filter.contains(data1));
        System.out.println("Contains test2: " + filter.contains(data2));

        filter.delete(data1);
        System.out.println("After delete, contains test1: " + filter.contains(data1));
    }
}