两个十六进制数的相似度

我试图使用汉明和编辑距离找到类似的哈希值（十六进制哈希值）。假设两个哈希值相似，如果它们的汉明距离小于 10（不同位数）。

Hash 1= ffffff (base 16)
Hash 2= fffff0 (base 16)

两个哈希之间的汉明距离是4。它们是相似的。因为，

Hash 1= 11111111 11111111 11111111 (base 2)
Hash 2= 11111111 11111111 11110000 (base 2)

我有 800 万个这样的哈希值。我想知道存储 800 万个哈希值的合适数据结构是什么。我最初尝试了“Trie”，但考虑以下场景，

Hash 1 = 0fabde (00001111 10101011 11011110)
Hash 2 = adcbfe (10101010 11001011 11111110)

汉明距离是7。所以我无法进行前缀搜索。

我知道我可以使用 XOR 和 Integer.bitCount() 来获取不同位数，但我有一个目标哈希和 800 万个哈希来搜索，即给定一个哈希，我必须在 800 万个哈希中找到所有相似的哈希我们在存储库中拥有的。

有什么方法可以有效地存储哈希值，从而减少我的搜索库？

如果哈希值如图所示那么小，您可以“直接”对它们进行索引 - 也就是说，将它们放入一个大数组中，然后对索引进行一些数学计算。

仅生成可能对应于请求的汉明距离内的哈希值的索引非常简单d，只需将密钥与包含最多包含的所有掩码进行异或d设置位（见下文）。由于有 800 万个哈希值，但只能存在 1600 万个，因此预计大约一半的访问索引是“有用的”，即可以找到一些东西。

要生成掩码，您可以使用旧的下一个位排列 https://graphics.stanford.edu/~seander/bithacks.html#NextBitPermutation例如，该技巧之前已在 StackOverflow 上发布过多次here https://stackoverflow.com/q/8281951/555045。对于java，只需使用逻辑右移和替换__builtin_ctz by numberOfTrailingZeros得到（未测试）

int t = v | (v - 1);
int w = (t + 1) | (((~t & -~t) - 1) >>> (Integer.numberOfTrailingZeros(v) + 1));

Here w将是之后的位排列v.

全局结构类似于（未测试）

for (int k = 1; k <= d; k++) {
    int diff = (1 << k) - 1;
    while (diff <= 0xFFFFFF) {
        if (hashes[key ^ diff])
            // do something with it
        diff = nextBitPermutation(diff);
    }
}