1

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

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

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

有人有好主意吗？

4

3 回答 3

9

您可以true在数组的开头插入一个标记元素，然后将该数组解释为二进制数。对于少于 32 个元素的数组，这是一个完美的散列（无冲突）。对于较大的数组，我建议对小于 2 31的大素数进行算术模运算。

例子：

Array       | Binary | Decimal
------------+--------+---------
[ 0, 1, 1 ] |   1011 |      11
[ 1, 1 ]    |    111 |       7

这与将数组解释为二进制数，然后对数组的大小进行按位 OR1 << n相同n。

执行：

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

注意：这个实现只适用于少于 32 个元素的数组，因为对于较大的数组，计算会溢出（假设int是 32 位）并且最高有效位将被完全丢弃。这可以通过h = h % ((1 << 31) - 1);在 for 循环结束之前插入来解决（表达式“(1 << 31) - 1”计算 2 31 - 1，即prime）。

于 2013-07-01T07:17:37.703 回答
3

我的想法：

方法#1：

  1. 计算第一个2n素数，其中n是数组的长度。

  2. 设哈希 = 1。

  3. 对于 i = 0 到 n：如果位置的位i为 1，则乘以hashth2i和2i + 1st 素数。如果为 0，则仅乘以2i第 1 个。

方法#2：

  1. 将二进制数组视为三进制。位为 0 => 三进制数为 0；位为 1 => 三进制数为 1；位不存在 => 三进制数字为 2（前者有效，因为数组具有最大可能长度）。

  2. 使用此替换计算三进制数 - 结果将是唯一的。

下面是一些代码，展示了这些算法在 C++ 中的实现，以及一个为每个长度为 0...18 的布尔数组生成哈希的测试程序。我使用 C++11 类std::unordered_map，以便每个哈希都是唯一的。因此，如果我们没有任何重复项（即，如果散列函数是完美的），我们应该得到2 ^ 19 - 1集合中的元素，我们这样做（我必须unsigned long long在 IDEone 上将整数更改为，否则散列不完美 -我怀疑这与 32 位和 64 位架构有关）：

#include <unordered_set>
#include <iostream>

#define MAX_LEN 18

unsigned long prime_hash(const unsigned int *arr, size_t len)
{
    /* first 2 * MAX_LEN primes */
    static const unsigned long p[2 * MAX_LEN] = { 
          2,   3,   5,   7,  11,  13,  17,  19,  23,
         29,  31,  37,  41,  43,  47,  53,  59,  61,
         67,  71,  73,  79,  83,  89,  97, 101, 103,
        107, 109, 113, 127, 131, 137, 139, 149, 151
    };

    unsigned long h = 1;
    for (size_t i = 0; i < len; i++)
        h *= p[2 * i] * (arr[i] ? p[2 * i + 1] : 1);

    return h;
}

unsigned long ternary_hash(const unsigned int *arr, size_t len)
{
    static const unsigned long p3[MAX_LEN] = {
               1,            3,            9,           27,
              81,          243,          729,         2187,         
            6561,        19683,        59049,       177147,
          531441,      1594323,      4782969,     14348907,
        43046721,    129140163
    };

    unsigned long h = 0;
    for (size_t i = 0; i < len; i++)
        if (arr[i])
            h += p3[i];

    for (size_t i = len; i < MAX_LEN; i++)
        h += 2 * p3[i];

    return h;
}

void int2barr(unsigned int *dst, unsigned long n, size_t len)
{
    for (size_t i = 0; i < len; i++) {
        dst[i] = n & 1;
        n >>= 1;
    }
}

int main()
{
    std::unordered_set<unsigned long> phashes, thashes;


    /* generate all possible bool-arrays from length 0 to length 18 */

    /* first, we checksum the only 0-element array */
    phashes.insert(prime_hash(NULL, 0));
    thashes.insert(ternary_hash(NULL, 0));

    /* then we checksum the arrays of length 1...18 */
    for (size_t len = 1; len <= MAX_LEN; len++) {
        unsigned int bits[len];
        for (unsigned long i = 0; i < (1 << len); i++) {
            int2barr(bits, i, len);

            phashes.insert(prime_hash(bits, len));
            thashes.insert(ternary_hash(bits, len));
        }
    }

    std::cout << "prime hashes: " << phashes.size() << std::endl;
    std::cout << "ternary hashes: " << thashes.size() << std::endl;

    return 0;
}
于 2013-07-01T06:43:19.023 回答
2

一个简单有效的哈希码是用素数替换 0 和 1 并执行通常的移位累加器循环：

hash=0
for (bits in list):
    hash = hash*31 + 2*bit + 3
return hash

这里 0 被视为 3 而 1 被视为 5，因此前导零不会被忽略。乘以 31 确保顺序很重要。不过，这在密码学上并不强大：给定一个短序列的哈希码，可以通过简单的算术来反转它。

于 2013-07-01T06:41:30.337 回答