1

サイズが一定でないブール配列がいくつかあります。ハッシュ衝突の可能性を最小限に抑えるには、強力で高速なハッシュアルゴリズムが必要です。

私自身の考えは、各ブール配列の整数値を計算することでしたが、たとえば、これらの 2 つの配列は 3 の同じハッシュを与えます:
[0 , 1, 1] および [1, 1]

整数値を計算した後に配列のサイズを乗算することを考えましたが、ハッシュ衝突の可能性が高いため、この考えも最悪です。

誰もが良い考えを持っていますか?

4

3 に答える 3

9

配列の先頭にセンチネルtrue要素を挿入してから、配列を 2 進数として解釈できます。これは、要素数が 32 未満の配列の完全なハッシュ(衝突なし) です。より大きな配列の場合、2 31未満の大きな素数を法として算術演算を行うことをお勧めします。

例:

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

これは、配列を 2 進数として解釈し、次にビットごとの OR をとることと同じ1 << 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 未満の配列でのみ適切に機能します。これは、より大きな配列の場合、計算がオーバーフローし ( int32 ビットと仮定)、最上位ビットが完全に破棄されるためです。これは、for ループの終わりの前に挿入することで修正できh = h % ((1 << 31) - 1);ます (式 "(1 << 31) - 1"は、素数である 2 31 - 1 を計算します)。

于 2013-07-01T07:17:37.703 に答える
3

私のアイデア:

アプローチ #1:

  1. 2n最初の素数を計算します。ここnで、 は配列の長さです。

  2. ハッシュ = 1 とします。

  3. i = 0 ～ n の場合: position のビットが 1 の場合、th とst の素数iを掛けます。0 の場合はth だけを掛けます。hash2i2i + 12i

アプローチ #2:

  1. 2 進配列を 3 進として扱います。ビットが 0 => 3 進数が 0; ビットが 1 => 3 進数が 1; ビットが存在しない => 3 進数が 2 (この前者は、配列に可能な最大長があるため機能します)。

  2. この置換を使用して 3 進数を計算します。結果は一意になります。

これらのアルゴリズムを C++ で実装したコードと、長さ 0 ～ 18 のブール配列ごとにハッシュを生成するテスト プログラムを次に示します。std::unordered_map各ハッシュが一意になるように、C++11 クラスを使用します。したがって、重複がない場合 (つまり、ハッシュ関数が完全である場合)、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 に答える