java写布隆过滤器防止重复提交

布隆过滤器是一种空间效率很高的概率型数据结构，常用于判断一个元素是否在一个集合中。在防止重复提交的场景中，可以使用布隆过滤器来判断某个请求是否已经被处理过。

以下是一个简单的布隆过滤器的实现：

import java.util.BitSet;

public class BloomFilter {

    private BitSet bitSet;
    private int size;
    private int hashFuncNum;

    public BloomFilter(int size, int hashFuncNum) {
        this.size = size;
        this.hashFuncNum = hashFuncNum;
        bitSet = new BitSet(size);
    }

    public void add(String str) {
        for (int i = 0; i < hashFuncNum; i++) {
            int hash = hash(str, i);
            bitSet.set(hash, true);
        }
    }

    public boolean contains(String str) {
        for (int i = 0; i < hashFuncNum; i++) {
            int hash = hash(str, i);
            if (!bitSet.get(hash)) {
                return false;
            }
        }
        return true;
    }

    private int hash(String str, int i) {
        int hash = 0;
        for (int j = 0; j < str.length(); j++) {
            hash = hash * i + str.charAt(j);
        }
        return Math.abs(hash) % size;
    }
}

在使用布隆过滤器防止重复提交时，可以在处理请求之前使用布隆过滤器判断该请求是否已经处理过，如果已经处理过则直接返回结果，否则继续处理请求并将请求的关键信息添加到布隆过滤器中。

以下是一个使用布隆过滤器防止重复提交的示例：

public class RequestProcessor {

    private BloomFilter filter;

    public RequestProcessor(int size, int hashFuncNum) {
        filter = new BloomFilter(size, hashFuncNum);
    }

    public String process(Request request) {
        // 判断请求是否已经处理过
        if (filter.contains(request.getKey())) {
            return request.getPreviousResult();
        }

        // 处理请求
        String result = doProcess(request);

        // 将请求的关键信息添加到布隆过滤器中
        filter.add(request.getKey());

        return result;
    }

    private String doProcess(Request request) {
        // 实际的请求处理逻辑
        return "result";
    }
}

在上述示例中，使用布隆过滤器判断请求是否已经处理过的时间复杂度是 O(k)，其中 k 是 hashFuncNum，通常情况下 k 的值较小，因此布隆过滤器的时间复杂度非常低，适合在高并发场景下使用。