java - 我需要修改这些哈希函数，以便它给出 0<x<10^9 范围内的值

Question

我试图在 java 中实现布隆过滤器，但问题是散列函数返回的值在 -10^20 范围内

public long APHash(String str)
{
    long hash = 0xAAAAAAAA;
    for(int i = 0; i < str.length(); i++)
    {
        if ((i & 1) == 0)
        {
            hash ^= ((hash << 7) ^ str.charAt(i) * (hash >> 3));
        }
        else
             {
            hash ^= (~((hash << 11) + str.charAt(i) ^ (hash >> 5)));
        }
    }
    return hash;
}

Answer 1

补充一下 Cinnam 的评论，您不需要数组，因为那是占用大量内存的方式，正如您指出的那样，您达到了极限。一个 Map 是理想的，其中键是 bloom 函数的输出值。 Map 只会增长以满足其中的条目数量，而不会通过使用数组会导致的 10^20 bloom 输出来填充可能的条目数量。

最后一个问题是使用什么作为 key 。您可以使用 String、long 或 BigInteger。 Map 的值将是一个 boolean 值。

编辑:为了满足 O(1) 的要求，HashMap 比 TreeMap 更受欢迎，但如果您只有一个条目，这真的无关紧要。