可变大小布尔数组的哈希算法

Question

我有一些布尔数组,它们的大小不是常数,而且我需要一个强大而快速的哈希算法来为它们提供最小的哈希冲突机会.

我自己的想法是计算每个布尔数组的整数值,但是例如这两个数组将给出3的相同散列:
[0,1,1]和[1,1]

我想在计算整数值后乘以数组的大小,但这个想法也很糟糕,因为哈希冲突的可能性很高.

有没有人有个好主意？

Answer 1

true在数组的开头插入一个sentinel 元素,然后将该数组解释为二进制数.对于少于32个元素的数组,这是一个完美的哈希(无冲突).对于较大的数组,我建议算术模数小于2 ³¹.

例子:

Array       | Binary | Decimal
------------+--------+---------
[ 0, 1, 1 ] |  01011 |      11
[ 1, 1 ]    |  00111 |       7

这与将数组解释为二进制数并按位OR进行相同1 << n,其中n是数组的大小.

执行:

int hash(int[] array)
{
    int h = (1 << array.length);
    for (int i = 0; i < array.length; i++)
    {
        h = h | (array[i] << (array.length - i - 1));
    }
    return h;
}